内容简介：为什么Google sparsehash的开源库有两个实现：一个密集的哈希表和一个稀疏的代码日志版权声明：翻译自：http://stackoverflow.com/questions/5289241/what-is-the-main-implementation-idea-behind-sparse-hash-table
为什么Google sparsehash的开源库有两个实现：一个密集的哈希表和一个稀疏的
密集哈希表是您普通教科书的哈希表实现.
稀疏哈希表仅存储实际设置的元素,并分割数组.引用从 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位的开销(限制).
代码日志版权声明：
翻译自：http://stackoverflow.com/questions/5289241/what-is-the-main-implementation-idea-behind-sparse-hash-table
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
