[pdata/xpdata/xhash]: MapHash takes quadratic time in the number of map entries

Component(s)

pdata/xpdata/xhash

What happened?

Describe the bug

writeMapHash in pdata/xpdata/xhash/hash.go collects the keys of a map, sorts them, and then looks up the value of each key again with Map.Get:

for k := range m.All() {
	hw.keysBuf = append(hw.keysBuf, k)
}
...
sort.Strings(workingKeySet)
for _, k := range workingKeySet {
	v, _ := m.Get(k)
	...
}

pcommon.Map.Get scans the entries one by one (pdata/pcommon/map.go), so this loop costs O(n²) for a map with n entries. The value is already available in the first loop.

This matters for the log deduplication processor in contrib. It calls xhash.Hash64(xhash.WithMap(...)) for the resource attributes, the scope attributes and the log attributes of every log record, so log records with many attributes are expensive to hash.

Steps to reproduce

Add a benchmark that hashes a map with 256 scalar entries next to the existing MapHash benchmarks. On main, on an Apple M2:

• 8 entries (BenchmarkMapHashEightItems): about 330 ns
• 256 entries: about 68 µs

That is 32 times the entries for about 200 times the time.

Expected behavior

The time to hash a map grows roughly with n log n (the sort), not with n².

Collector version

main at 9637d3e9a (after #15943 moved the code into core). The same code is in contrib pkg/pdatautil in v0.161.0 and was reported there as open-telemetry/opentelemetry-collector-contrib#50851 (the issue is still open, but the package was removed from contrib in open-telemetry/opentelemetry-collector-contrib#51108).

Environment information

Apple M2, macOS, go1.26.5.

OpenTelemetry Collector configuration

Not applicable.

Log output

Not applicable.

Additional context

The fix is small: collect each key together with its value in the same pass, sort the entries, and hash them in order. The bytes that are hashed do not change, so the hash values are identical. In my measurements the 256-entry case gets about 10 times faster and the smaller benchmarks do not get slower.

Would a PR for this be welcome?