数据结构 – 稀疏哈希表背后的主要实现思想是什么?

栏目: 数据库 · 发布时间: 6年前

内容简介:为什么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


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Web之困:现代Web应用安全指南

Web之困:现代Web应用安全指南

(美)Michal Zalewski / 朱筱丹 / 机械工业出版社 / 2013-10 / 69

《web之困:现代web应用安全指南》在web安全领域有“圣经”的美誉,在世界范围内被安全工作者和web从业人员广为称道,由来自google chrome浏览器团队的世界顶级黑客、国际一流安全专家撰写,是目前唯一深度探索现代web浏览器安全技术的专著。本书从浏览器设计的角度切入,以探讨浏览器的各主要特性和由此衍生出来的各种安全相关问题为主线,深入剖析了现代web浏览器的技术原理、安全机制和设计上的......一起来看看 《Web之困:现代Web应用安全指南》 这本书的介绍吧!

MD5 加密
MD5 加密

MD5 加密工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具