4 ms·
Most real-world hash table implementations are not "theoretical" but depends on "real" parameters like L2 cache, assembly instruction sizes, etc
by oulipo 2y ago
Most real-world hash table implementations are not "theoretical" but depends on "real" parameters like L2 cache, assembly instruction sizes, etc
- kazinator 2y agoReal world hash table can either be resized to avoid worst-case degradation or else be provisioned to have a good amount of slack when the worst expected case occurs. (E.g. a hash table used a cache will apply pressure to evacuate old entries before it gets foo full.) Bucket hashing obviously has no problem finding a free spot. I didn't say chained on purpose because chains can be resizable vectors, so we load at most one pointer when going from table to bucket.
- xxs 2y agoBucket can evolve to red/black tree, if there are too many entries given O(logK) (collisions) for lookups. Still bucket based ones tend to be outclasses (both latency and memory footprint) by the dumbest linear probe.
- kazinator 2y agoSome hash tables promote updated entries to the front of the chain for faster access next time. It occurs to me that a good old splay tree would do that. The thing is, you're not supposed to have buckets so large that you need a fancy data structure. If the table is not resizeable, it might not be avoidable.
- slt2021 2y agoits more like real-world hash tables are tailored to the specific pattern of querying and inserting data. if you know empirically that 80% of your requests come to a tiny subset of hot keys - you make a specific hashset just for these hot keys with constant access time, while keeping the rest of the table cold. your L2 cache is an example of such optimization - a high bandwidth and low latency memory on the CPU die, that is orders of magnitude faster than random DRAM access - a tiered memory model
- deleted 2y ago[deleted]