3 ms·
I lack experience to tell - does anybody use chaining in production?
by RicoElectrico 4y ago
I 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.