3 ms·

It's intersting to see that some people add randomness to fight this, for example with maps in Go. It seems like it's the right choice.

• MaulingMonkey 5y ago
  Inserting randomness can help prevent denial of service attacks as well, by making it harder to manufacture pathological hash collisions (which can turn ~O(1) operations into O(N) operations).
• ncmncm 5y ago
  Right, like every release of any component should vary some detail that the spec doesn't guarantee. Especially, all hash functions should change on every release -- at least when building in debug mode.
  • vlovich123 5y ago
    Hash functions should use a random seed on every new container instance (or at least once per launch). Those hash tables that need specific properties of the hash should inject it in that way (cryptographic, deterministic, DOS-resistant, etc).
• jeffbee 5y ago
  Another place to insert randomness that could have uncovered this would be in the allocator size classes. In non-optimized builds, if your allocator has size classes, just pick them randomly. In my experience this uncovered a lot of bugs in programs linked against tcmalloc.
• yxhuvud 5y ago
  Other people fight it by adding a defined iteration order. That works just as well and don't introduce randomness.
  • wizzwizz4 5y ago
    But prevents optimisation, if that optimisation would lose the iteration order. If you need defined ordering in your type, use it. Otherwise, don't specify it.
    • yxhuvud 5y ago
      Sure, but the overhead to iterate in insertion order is very small. Sorting by key is way more expensive.