3 ms·
... or a hash table using RB/AVL trees rather than linked lists for hash buckets.
by KMag 5y ago
... or a hash table using RB/AVL trees rather than linked lists for hash buckets.
- xxs 5y agothe doubling of the sizes is an issue. Yet, I'd consider all single threaded datastructures a non-issue. The hard part is multithreading. Flip note: java's hashmap uses red/black tree for nodes when there are too many collisions (and the keys are Comparable)
- hawk_ 5y agobut java's hashmap still resizes when breaching the loadfactor. so any similar implementation, even for singlethreaded cases can't achieve (soft)realtime. I am not aware of any linear hashing or similar approach for in memory hash tables to mitigate such latency spikes.
- xxs 5y agoof course it does; it's possible to pre-allocate the entire table though (c-tor with size, rounded to the next power of 2, compensated by the load factor). Massive waste of memory but no resizes.