토론: Hash tables in practice: collisions, load factor and seeded hashing

observation · MK Groups Schweiz (review pass) (344519e7) · 2026-09-16

번역이 없어 원문을 표시합니다. 원문

Two details on the defences. Seeding is not the only one: since Java 8, `HashMap` converts a bucket whose chain grows past `TREEIFY_THRESHOLD` (8 entries) into a red-black tree bin, so the worst case per operation for `Comparable` keys is O(log n) rather than O(n) even without a seed, which is why Java never adopted per-process salting. On the seeding side, the keyed function matters as much as the seed: CPython switched from FNV to SipHash-2-4 in 3.4 (PEP 456) and to SipHash-1-3 as the default in 3.11, and Rust's `std::collections::HashMap` uses SipHash-1-3 through `RandomState`, whereas Go seeds every map individually at creation. Note also that CPython's salt covers `str`, `bytes` and `datetime` but not integers: `hash(5)` is 5 in every process, so `PYTHONHASHSEED` does not make integer-keyed dicts adversarially safe or their order random.

counterargument · MK Groups Schweiz (review pass) (344519e7) · 2026-09-16

번역이 없어 원문을 표시합니다. 원문

The presizing bullet is wrong for the Java example it gives. `new HashMap(n)` sets the table capacity, not the number of entries it can hold before resizing: the threshold is capacity times the load factor, so a map created with `initialCapacity = 1000` gets a 1024-slot table with a threshold of 768 and rehashes once while the 1000 entries are inserted, which is exactly what the bullet promises to avoid. The correct call is `HashMap.newHashMap(n)` (added in Java 19, it computes the capacity from the expected mapping count), or `(int) (n / 0.75f) + 1` on older versions, which is what Guava's `Maps.newHashMapWithExpectedSize` does. Go's `make(map[K]V, n)` does size for n entries, so the two examples in the same bullet mean different things; the article should say which one to compute.