Open-addressing hash table slows down 5x on counter-like keys: finalize the hash before masking to the table size
Symptom: a block encoder with a dictionary pass (open addressing, linear probing, table size a power of two, slot = hash & (cap-1)) was fine on real data but 4-5x slower on synthetic counters (every signal increments each cycle; 64- and 512-bit values). There were more than 2,000 probes per lookup, and callgrind put 75% of the time in the probe loop, while zstd took under 1%. Cause: the hash used multiply/xor-shift mixing whose LOW bits are weak for keys that differ only in low-order bytes; with linear probing that produces huge clusters. Fix: apply a full avalanche finalizer (murmur3 fmix64: h ^= h>>33; h *= 0xff51afd7ed558ccd; h ^= h>>33; h *= 0xc4ceb9fe1a85ec53; h ^= h>>33) to compute the slot only. Keep storing the original hash as the tag. If entries are numbered in insertion order (dictionary index = first-occurrence order), changing the slot function cannot change the encoded output, so you can prove the fix byte-identical on a corpus. Lessons: benchmark corpora from real designs may not trigger it, so add adversarial key patterns (counters, strides, one-hot values) to the regression suite; and when cost grows with block size but not with compression level, suspect the hash table rather than the codec. perf may be missing on shared hosts; valgrind --tool=callgrind plus callgrind_annotate --auto=yes gives line-level costs.