稀疏哈希表背后的主要实现思想是什么? [英] What is the main implementation idea behind sparse hash table?
本文介绍了稀疏哈希表背后的主要实现思想是什么?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
为什么Google sparsehash开源库有两个实现:一个密集的哈希表和一个稀疏的
Why does Google sparsehash open-source library has two implementations: a dense hashtable and a sparse one?
推荐答案
密集哈希表是您普通的教科书散列表实现。
The dense hashtable is your ordinary textbook hashtable implementation.
稀疏哈希表仅存储实际设置的元素,并分割数组。引用稀疏执行中的评论表:
The sparse hashtable stores only the elements that have actually been set, divided over a number of arrays. To quote from the comments in the implementation of sparse tables:
// The idea is that a table with (logically) t buckets is divided
// into t/M *groups* of M buckets each. (M is a constant set in
// GROUP_SIZE for efficiency.) Each group is stored sparsely.
// Thus, inserting into the table causes some array to grow, which is
// slow but still constant time. Lookup involves doing a
// logical-position-to-sparse-position lookup, which is also slow but
// constant time. The larger M is, the slower these operations are
// but the less overhead (slightly).
要知道数组的哪些元素被设置,一个稀疏表包含一个位图:
To know which elements of the arrays are set, a sparse table includes a bitmap:
// To store the sparse array, we store a bitmap B, where B[i] = 1 iff
// bucket i is non-empty. Then to look up bucket i we really look up
// array[# of 1s before i in B]. This is constant time for fixed M.
的固定时间,以便每个元素只产生一个开销(在限制)。
so that each element incurs an overhead of only 1 bit (in the limit).
这篇关于稀疏哈希表背后的主要实现思想是什么?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文