开发者

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...

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜