4 ms·
> Back in the day, open-addressing approaches were not regarded as sufficiently mature, so closed addressing was taken as the safe implementation of choice. I
by kccqzy 4y ago
> Back in the day, open-addressing approaches were not regarded as sufficiently mature, so closed addressing was taken as the safe implementation of choice.
I always chuckle when I read statements like this because it didn't match my own experience as a learner. When I learned computer science, I was taught hash tables right after arrays, but before linked lists or even pointers. So open addressing had always been the default for hash tables for me. I'm curious to hear what other people's learning journeys are like.
- RicoElectrico 4y agoI lack experience to tell - does anybody use chaining in production?
- zeroonetwothree 4y agounordered_map uses chaining
- masklinn 4y agoIIRC php and go use separate chaining (unless php switched while I wasn’t looking).
- ghusbands 4y agoIt is conceptually simpler, especially once deletion is involved, and is the more common implementation.
- adgjlsfhk1 4y agoI think it was a while ago, but at this point, the cost of pointer chasing and memory overhead of separate chaining mean that is is being phased out.
- dlp211 4y agoI thought Java's Hashmap used chaining.
- utopcell 4y agoWhy would any, when absl::flat_hash_map<> and absl::node_hash_map<> is available ?
- colinmhayes 4y agostd uses chaining because deletion isn't allowed to invalidate iterators.
- imron 4y agoI guess what we need now then is std::open_unordered_map ;-)
- jlokier 4y agoThe Linux kernel uses chained hash tables in many places. https://github.com/torvalds/linux/blob/master/include/linux/hashtable.h https://github.com/torvalds/linux/blob/master/include/linux/...
- gjulianm 4y agoIt's a tradeoff. Open addressing is faster due to cache locality, but needs a good hash function. If the hash function tends to cluster values and generate collisions you might (key word here "might", as usual you need to do profiling to check each case) end up with way more operations per query. But for 90% of cases, you don't really care that much about performance and whether it's open or closed addressing, as long as the mapping works.