为什么Google sparsehashash开源库有两个实现:密集的哈希表和稀疏的哈希表?
最佳答案
密集哈希表是您的普通教科书哈希表实现。
稀疏哈希表仅存储实际设置的元素,并划分为多个数组。要在稀疏表的实现中引用comments:
// 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 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.
因此每个元素仅产生1位的开销(在限制内)。
关于data-structures - 稀疏哈希表的主要实现思想是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5289241/