Best hash table for insertion and lookup only
I want to make a hash table that allows insertion and lookup only. Once something is in the table, it is in for good, unless you make a new hash table and refill the contents. Is there any algorithms/dat开发者_StackOverflow社区a structures that are more suited for this (over say B-tree/RB-tree/LLRB-tree)? Better would be like - faster insertion and lookup times, or can be sharded easier, or smaller overhead. Thanks
If you know (roughly) how many times each item will be looked up (and these frequencies are not uniform) then you could use Knuth's algorithm (free pdf) for finding an optimal tree that will make the more frequently-accessed items closer to the top (and so are faster to access). Each node in this tree would be a hash code (used for navigating the tree) and a pointer to the actual item. I don't know of any implementations of this algorithm, though...
精彩评论