稀疏哈希表背后的主要实现思路是什么？

Question

为什么Google sparsehash开源库有两个实现:密集哈希表和稀疏哈希表？

Answer 1

密集哈希表是您的普通教科书哈希表实现.

稀疏哈希表仅存储实际已设置的元素,并分布在多个数组中.引用稀疏表的实现中的注释:

// 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比特的开销(在极限中).