假设是均匀散列，期望探查次数变化随负载因子变化的规律
负载因子(%)	期望探查次数
<50	<1/(1-0.50)=2
80	1/(1-0.80)=5
90	1/(1-0.90)=10
95	1/(1-0.95)=20

哈希索引

千次阅读 2019-05-22 17:09:45

哈希索引（hash index）基于哈希表实现，只有精确匹配索引所有列的查询才有效。对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码（hash code），哈希码是一个较小的值，并且不同键值的行计算出来的哈希码...

哈希索引（hash index）基于哈希表实现，只有精确匹配索引所有列的查询才有效。对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码（hash code），哈希码是一个较小的值，并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。

哈希索引可细分为静态哈希和动态哈希这两大类，先介绍静态哈希，然后再介绍动态哈希。

静态哈希

基于散列技术的文件组织使我们能够避免访问索引结构，同时也提供了一种构造索引的方法。在对散列的描述中，使用桶(bucket)来表示能存储一条或多条记录的一个存储单位。通常一个桶就是一个磁盘块，但也可能大于或者小于一个磁盘块。

散列索引将散列函数作用于搜索码以确定对应的桶，然后将此搜索码以及对应的指针存入此桶(或溢出桶)中。

静态哈希.png

【散列函数（hash function）】：令 K 表示所有的搜索码值的集合, 令 B 表示所有桶地址的集合,，散列函数 h 是一个从 K 到 B 的函数.。

插入操作：计算 h(Ki)，从而获得存放该记录的桶的地址，并将记录存储到该桶中；
查找：计算 h(Ki)，然后搜索具有该地址的桶；
删除：计算 h(Ki)，然后在相应的桶中查找此记录并从中删除它。

【散列函数的特点】：

理想的散列函数把存储的码均匀地分布到所有的桶中，使每个桶含有相同数目的记录。
分布是均匀的：即散列函数从所有可能的搜索码值集合中为每个桶分配同样数量的搜索码值。
分布是随机的：即在一般情况下, 不管搜索码值实际怎样分布, 每个桶应分配到的搜索码值数目几乎相同. 更确切地说, 散列值不应与搜索码的任何外部可见的排序相关, 例如按字母的顺序或按搜索码长度的顺序. 散列函数应该表现为随机的.

桶溢出

到目前为止，我们一直假设插入记录时，记录映射到的桶有存储记录的空间。若此时桶已经没有足够的空间，就会发生桶溢出现象。

【产生原因】：

桶不足：通数目（用 Nb 表示）的选择必须使 Nb > Nr/fr，其中 Nr 表示将要存储的记录总数，fr 表示一个桶能存放的记录数目。需要注意的是，这种表示是以记录总数已知为前提选择散列函数。
偏斜：某些桶分配到的记录比其他桶多，所以即使其他桶仍有空间，某个桶也仍可能溢出，这种情况称为桶偏斜。偏斜发生的原因有两个：
- 多条记录可能有相同的搜索码；
- 所选的散列函数可能会造成搜索码的分布不均。

【处理方案】：溢出链。

桶的数目选为 (Nr / fr) * (1 + d)，其中 d 为避让因子，取值一般约为 0.2。相当于增加了桶的数目（若桶的数目不为整数，则向上取整），虽然有一些空间会浪费，但在一定程度上减少了溢出的可能性。

需要明确的是：尽管分配的桶比所需的桶多一些，但是桶溢出还是可能发生。我们用溢出桶（多出来的那些桶）来处理桶溢出问题。具体过程如下：如果一条记录必须插入桶 b，而桶 b 此时已满，系统会提供另一个溢出桶来存储该记录。如果溢出桶也满了，再提供另一个溢出桶，如此循环。

一个给定桶的所有溢出桶用一个链表链接在一起，使用这种链表的溢出处理称为溢出链。

溢出链.png

为了处理溢出链, 我们需要将查找算法做轻微的改动。和前面一样，系统使用搜索码上的散列函数来确定一个桶 b，系统必须检查桶 b 中所有的记录，看是否有匹配的搜索码。此外，如果桶 b 有溢出桶，则系统还要检查桶 b 的所有溢出桶中的记录。

静态哈希的缺点

静态散列最大的缺点在于必须在实现系统时选择确定的散列函数。此后若被索引的文件变大或缩小，要想再改变散列函数就不容易了。因为散列函数 h 将搜索码值映射到桶地址的固定集合 B 上：

根据当前文件大小选择散列函数，这样的选择会使得性能随着数据库的增大而下降。换言之，初始时集合 B 太小，一个桶就会包含许多不同的搜索码值的记录，从而可能发生桶溢出。当文件变大时，性能就会受到影响。
根据将来某个时刻文件的预计大小选择散列函数。尽管这样可以避免性能下降，但是初始时会造成相当大的空间浪费。

虽然我们可以随着文件增大，周期性地对散列结构进行重组。这种重组涉及一系列问题：

包括新散列函数的选择；
在文件中每条记录上重新计算散列函数；
分配新的桶。

重组是一个规模大、耗时的操作，而且重组期间必须禁止对文件的访问。所以我们需要解决的问题就是如何动态地改变桶的数目和散列函数。

动态哈希

针对静态散列技术出现的问题，动态散列（dynamic hashing）技术允许散列函数动态改变，以适应数据库增大或缩小的需要，下面介绍可扩充散列（extendable hashing）。

可扩充散列

当数据库增大或缩小时，可扩充散列可以通过桶的分裂或合并来适应数据库大小的变化，这样可以保持空间的使用效率。此外，由于重组每次仅作用于一个桶，因此所带来的性能开销较低。

【做法】：

选择一个具有均匀性和随机性特性的散列函数 h。此散列函数产生的值范围相对较大，是 b 位二进制整数，一个典型的 b 值是 32。
把记录插入文件时按需建桶，用小于等于 b 的 i 个位用作附加桶地址表中的偏移量，i 的值会随着数据库大小的变化而增大或者减少。

可扩充散列.png

查询操作

【过程】：查找包含搜索关键字 k 的存储桶。

计算 h(k) = X；
使用 X 的前 i 个高位作为存储区地址表的偏移量，并按指针指向相应的存储区。

插入操作

【过程】：插入具有搜索关键字 k 的记录。

按照查询操作找到存储桶，假设定位到桶编号为 j。如果该存储桶仍然有空间，则在该存储桶中插入记录，否则必须拆分存储桶，并将该桶中现有记录和新记录一起进行重新分配。为了拆分该存储桶，系统必须先根据散列值确定是否需要增加所使用的位数。
然后根据 i（global depth）和 ij（local depth）的大小关系进行相应的操作。
- 如果 i = ij，那么在桶地址表中只有一个指向桶 j 的指针，所以系统需要增加桶地址表的大小。以容纳由于桶 j 分裂而产生的两个桶指针。为了达到这个目的，系统可以将 i 的值加 1，从而使桶地址表的大小加倍。这样，原表中每个表项都被两个表项替代，两个表项都包含和原表项一样的指针。现在桶地址表中有两个表项指向桶 j。系统重新分配一个桶(桶z)，并让第二个表项指向此新桶。桶 j 中的各条记录重新散列，根据前 i 位（i 已经加1）来确定该记录是放在桶 j 中还是放在新创建的桶中。
- 如果 i > ij，那么就有多个表项（指针）指向桶 j。因此，不需要扩大桶地址表就可以分裂桶 j。指向桶 j 的所有表项的索引前缀的最左 ij 位相同。系统分配一个新桶(桶 z)，将 ij 和 iz 置为原 ij 加 1 后得到的值。然后系统需要调整桶地址表中原来指向桶 j 的表项。系统让这些表项的前一半保持原样(指向桶 j)，而后一半指向新创建的桶 (桶 z)。然后桶 j 中的各条记录重新被散列，分配到桶 j 或者桶 z 中。

【示例】：假设现在有如下三条搜索码值，h(k1) = 100100，h(k2) = 000110，h(k3) = 110110。先假设桶的大小为 1，并插入前两项 k1 和 k2，可以通过最左边的位值进行区分，得到如下图所示的结果。

可扩充散列插入操作图示1.png

接着，插入第三项，此时左边第一位已经无法区分了，所以将 i 增加 1，此时刚好可以将三个搜索码进行区分，见下图。

可扩充散列插入操作图示2.png

k1 和 k3 可通过 10 和 11 进行区分，以 0 作为第一位的不需要进行比较，所以 00 和 01 都是指向 k2。

现在需要插入一条新的搜索码值 h(k4) = 011110。前两位为 01 指向了桶 A，但桶 A 已满，所以需要进行分裂。因为没有更多的搜索码指向桶 A，所以 i 不需要增加，属于 i > ij 的情况，仅需要将桶 A 进行分裂，令 ij + 1，并重新进行分配。

可扩充散列插入操作图示3.png

如果，h(k2) = 010110，也就是说 k2 和 k4 都指向桶 D，并且桶 D 已满，更多的搜索码指向桶 D，属于 i = ij 的情况，所以需要将 i 加 1，用左边的三位来作为桶地址。现在将桶 D 分裂，变成 D’ 和 E，并重新进行散列操作，将 k2 放到 D’ 桶中，k4 放到 E 桶中。

可扩充散列插入操作图示4.png

删除操作

【过程】：删除一条搜索码值为 k 的记录。

系统先查找到对应的桶，设为桶 j。系统不仅要把搜索码从桶中删除，还要把记录从文件中删除。如果这时桶为空了，那么也要将桶删除掉。

需要注意的是，此时某些桶可能合并（就是与具有相同 ij 值和相同 ij -1 前缀的桶合并），桶地址表的大小也可以减半。

通过上述分析可总结出动态散列的优缺点。

【优点】：

随着记录的增加, 动态散列的性能并不会下降；
动态散列有着最小的空间开销。

【缺点】：

会增加一次额外的查询定位, 因为在查询桶本身之前还需要查找目录来定位桶；
存储区地址表本身可能变得很大；
更改存储区地址表的大小是一项代价昂贵的操作。

比较分析

顺序索引和散列索引的比较分析

【散列索引】：

在数据库中查找一个值的效率更高；
没有办法利用索引完成排序；
在有大量重复值的时候，散列索引的效率也是极低的，因为存在哈希碰撞的情况。

【顺序索引】：在指出了一个值范围的查询中比散列索引更可取。

如果存储的数据重复度很低（也就是说基数很大），对该列数据以等值查询为主，没有范围查询、没有排序的时候，特别适合采用散列索引；大多数情况下，会有范围查询，排序、分组等查询特征，就用顺序索引。

B+ 树索引和哈希索引的比较分析

【B+ 树】：

所有的值都是按照顺序存储的，并且每一个叶子页到根的距离相同；
适用于全键值、键值范围或者键前缀查找。顺序索引技术在指出了一个值范围的查询中比散列索引更可取。

【哈希索引】：基于哈希表实现，只有精确匹配索引所有列的查询才有效。

索引自身只需要存储对应的哈希值，所以索引的结构十分紧凑，这也让哈希索引查找的速度非常快。
缺点：
- Hash索引能使用范围查询；
- 数据库无法利用Hash索引的数据来避免任何排序运算；
- Hash索引任何时候都不能避免表扫描。

Q&A

问：顺序索引与散列索引的适用场景？

这两种索引结构都有其优缺点，如果是 select * from a where b=c 这样的定值查询，散列比顺序索引跟适合，顺序索引会随着记录数的增加而性能降低，散列则相对稳定。而对于 where b > c and b < d 这样的范围搜索，则顺序索引更适合，散列的随机特性使得无法定位搜索的桶。所以散列只适合根据搜索码搜索且不是范围查询的场合。

问：可扩充散列为什么需要局部深度和全局深度？

可扩展散列允许目录的大小增加或减少，具体取决于插入和删除的数量和种类。

目录大小更改后，应用于搜索键值的哈希函数也应更改。因此索引中应该有一些关于要应用哪个哈希函数的信息。此信息由全局深度提供。

目录大小的增加不会导致为每个新目录条目创建新存储桶。每当要拆分由两个或多个目录条目共享的存储桶时，目录大小不需要加倍。这意味着对于每个存储桶，我们需要知道它是由两个或多个目录条目共享。此信息由存储桶的局部深度提供。（目录：桶地址表）

总结

哈希索引思维导图.png

参考

数据库中的索引技术——哈希索引：https://blog.csdn.net/olizxq/article/details/82313489
MySQL BTree索引和hash索引的区别：https://blog.csdn.net/oChangWen/article/details/54024063
hash索引和B+tree索引区别：https://www.cnblogs.com/zhidongjian/p/10414129.html

收起

展开全文

【哈希】关于哈希表和哈希函数的理解与应用

2020-08-05 13:09:08

本文暂且不表这些基础知识，更多的重点在于哈希的一些应用和题目，对于哈希表、哈希函数从来没有学习过或者已经遗忘大部分的同学，建议先去阅读相关内容，否则本文不会成为一篇值得阅读的内容。 1.哈希的函数的定义...

0.概述

哈希，或者说散列，在教科书上写的都比较详细，通常包括的内容有散列的方法，散列冲突的解决等。本文暂且不表这些基础知识，更多的重点在于哈希的一些应用和题目，对于哈希表、哈希函数从来没有学习过或者已经遗忘大部分的同学，建议先去阅读相关内容，否则本文不会成为一篇值得阅读的内容。

1.哈希的函数的定义以及性质

之所以要介绍这一小节，主要是几乎所有的哈希函数的应用都离不开定义和性质，也正是因为哈希函数拥有这些性质才在各种场景发挥着优秀的性能。

定义：

$out = f(in)$ ，其中输入域为无穷，值域为有限域。

哈希函数的定义就是这么简单，就是一个函数，将无限域的输入值映射到有限域的一个函数，具体的这个函数是什么，其实并不是固定的，但是也不是随意的，但是只要能够符合以下的几个性质，并且能够有效地运用到具体的实际当中就可以称作哈希函数，比较著名的哈希函数有MD5，SHA1等密码领域的算法。

性质：

输入域有限，输出域无限；
无随机性，同一输入一定有相同的输出，但是不同的输入也可能有相同的输出；
强离散性，相似的输入经过散列函数后得到的结果大相径庭；
均匀性，对于输入经过散列函数后得到的结果等概率分布在输出域上；

简单的理解一下这几个性质，所谓的无随机性是很好理解的，因为根据定义我们知道输入域是大于输出域的，所以不同的输入是可能散列到同一结果的。关于离散性和均匀性其实说的是同一个事儿，原输入可以被均匀的充分的打乱，也就是散列结果的疏密是比较均匀的，这样的好处也是显而易见的，我们肯定不希望申请的存放输出的空间得到浪费，另外即使第二条说不同输入可能映射到相同的输出，我们也不希望结果密集的存放在相同的几个索引上吧，否则哈希表的数据结构查起来是相当没有效率的。

2.哈希表的扩容和复杂度

同样的，这里也不会详细解释什么是哈希表，关于哈希表的数据结构还是很重要的，目前在java工程师面试中，HashMap几乎是人人都会的知识点了，关于HashMap的介绍博主本人写了两篇相关的长篇幅：深入理解HashMap(一)、深入理解HashMap(二)。感兴趣的读者可以研读，其中比较详细的介绍了java中哈希表的使用和数据结构的实现。

如果你了解哈希表，一定知道出现哈希冲突的时候，是在相同的索引向后挂节点的（比如链表）。但是由于随着数据的变多，链表节点越挂越多，性能变低，所以关于哈希表有一套扩容机制，但是这个扩容机制各个语言有着不同的实现，比如我写的深入理解HashMap(一)中就介绍了hashmap的扩容机制。我们这里把问题简单化，我们就用最简单的扩容方法，就是将哈希表*2，比如原本申请的key值数组长度为8，下表索引为0~7，扩容后索引变为0~15，由于哈希表长度变化，所以要重新计算哈希值，这样链表长度也就能减少一半（散列性、均匀性）。教科书上一般都写的是哈希表的CRUD时间复杂度为 $O(1)$ ，在不扩容的情况下，确实如此，因为哈希表数据结构的物理存储结构只有两种：顺序存储结构和链式存储结构（像栈，队列，树，图等是从逻辑结构去抽象的，映射到内存中，也这两种物理组织形式），在数组中根据下标查找某个元素，一次定位就可以达到，哈希表利用了这种特性，哈希表的主干就是数组。比如我们要新增或查找某个元素，我们通过把当前元素的关键字，通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。但是扩容就需要重新计算哈希值，导致总时间复杂度变为多少呢，是 $O(N*logN)$ ，单次时间复杂度就变成 $\frac{O(N*logN)}{N}$ 。这很好理解，扩容的次数几乎就是 $logN$ ，比如说32个数，初始哈希表为2，扩容次数就是 $log_{2}^{32}$ ，每一次扩容重新计算哈希值得代价都是全量N，所以得到总时间复杂度为 $O(N*logN)$ ，对于N个数均摊下来单次的时间复杂度就是 $\frac{O(N*logN)}{N}$ 了。

那么对于使用C++的朋友呢，就是以上默认结果了，但是这是可以优化的，优化成 $O(1)$ ，这个 $O(1)$ 指的是对于用户来说的，比如说java语言，扩容的时间是被jvm托管的，这个过程是离线完成的，对于用户来说调用的结构一直是一个构建好的哈希表。

在具体语言中，对于哈希表的实现还是不尽相同的，所以对于刷算法题，通常建议使用java和C++，因为这两种语言纯粹的语法也可以，封装好的api也有。但是对于主流语言中的Python，用过Python的都知道，Python的数组几乎可以干所有的事情，这对于刷题人来说可解释性就没有那么强了。

3.哈希算法的应用--大文件统计高频数字

题目：

有一个大文件，其中存放着40亿个无符号的整数数字，统计出来出现次数最多的数，内存限制1G。

解析：

无符号的整数数字取值范围为0~ $2^{32}-1$ ,故是有可能40亿个数完全不同的。这是最坏的情况，我们假设这种最坏情况，我们定义哈希表为table<int key, int value>，key-value指的是某个数（key）出现的次数（value），也就是一条记录占了8个Byte(字节)的空间，40亿个不同的数字需要8 * 40亿个Byte（字节）空间，也就是32个G，另外哈希表本身的一些信息数据占据了一部分，我们这里就大约认为是32G的空间，但是题目只提供1G的内存，所以创建传统的哈希表肯定是不可取的。这个问题主要是由于数字太多，而且是不同的数字。。

优化：

解决方式就是把大文件分成小文件，由于40亿个数是K种数（K最小为一种，最大为40亿种），我们令每个数字经过哈希函数得到的输出再对100取模，这样得到的结果必然是0~99。即： $temp = f(in)$ ， $out = temp$ %100。
经过这样的计算，我们就将大文件切分为了100个小文件，把40亿个数字均匀的分到了100个文件中，而且得到的每个文件种数字的种类大致是一样的，这是由哈希函数的均匀性决定的，之所以开篇用了不少篇幅介绍了哈希函数相关的内容，就是为了更好的去理解具体应用，之后还是有很多这样的情况。那么现在我们这40亿个数最差情况是都不相同，也就是有40亿种数字，则每个小文件中大概有4000w个数，1G内存肯定是足够的（其实分成几个文件是由给定内存决定的，这里假设100个是可以的，其实还可以更小一些）。根据哈希函数的性质，同一种数不可能被散列到不同的小文件上，也就是说同一种数一定会落到同一个小文件内。我们用1G内存去统计0号文件中出现次数最多的数，然后释放，再去统计1号文件中的出现次数最多的数字，直到99号文件，最终100个数字词频最高的则返回，就是结果。

4.设计RandomPool结构

题目描述：

insert(key)；不重复插入，即相同的key值只记录一次。
delete(key)；
getRandom()；等概率随机返回任一key。

要求时间复杂度为O(1)；

解析：

本题还是比较简单的，不重复插入就不介绍了，用图的形式把建好插入的结构展现出来，然后去分析。我们需要建立两张hash表一张是正常的key-value存放，另一张是把第一张表的value当做key，key当做value存，这样做的目的是为了实现getRandom()函数，数据就用26个字母作为操作数据，另外需要一个size变量，初始值为0。

key	value	size = 0	key	value
"A"	0	size = 1	0	"A"
"B"	1	size = 2	"B"	1
.......	.......	.......	.......	.......
"Z"	25	size = 26	25	"Z"

getRandom()函数实现使用Math函数库就可以，size值记录了记录条数，所以随机返回0~25中的一个值可以写：

int index = Math.random(size)；
int reskey = table2.get(index); //table2(HashMap<int, String>)为哈希表2
String resValue = table1.get(reskey); //table1(HashMap<String, int>)为哈希表1

本题的坑位出现在delete(key)函数的实现上，因为删除后，索引就不再连续，之后再次调用getRandom()函数的时候，就需要进行进一步的判断，因为哈希表随着插入和删除，不会出现大量的空白索引，Math.random(size)也无法产生等概率的随机数了（准确说是不一定存在），时间复杂度不再是O(1)了，因为当出现不存在的索引，就会再次获取随机数，这样最差情况就是O(N)级别的了，因为最差就是仅剩下一条记录，而且每次获得随机的index都没取到，直到第N次。

优化：

删除的时候不是简单的删除，而是从哈希表的索引值末值去取值，用它去覆盖要删除的记录，然后size--。比如要删除"A"-0这条记录，我们去获取"Z"-25，然后覆盖掉"A"-0，变成：

key	value	size = 0	key	value
"Z"	0	size = 1	0	"Z"
"B"	1	size = 2	"B"	1
.......	.......	.......	.......	.......
"Y"	24	size = 25	24	"Y"

5.布隆过滤器

布隆过滤器是一个只支持从一个集合中检验某个记录是否出现过的过滤器。

5.1位图

定义：

位图就是bit类型的数组，就是以一个位的0-1表示信息。

示例：

int[] arr = new int[10];//该整型数组占40个Byte，也就是320bit

/*比如arr[0]表示0~31位置上的状态
 *    arr[1]表示32~63位置上状态
 *依次类推
 */

//取178位的状态
int numIndex = 178 / 32;  // 178/32得到在数组arr上位于0~10的哪个位置，这里答案是5
int bitIndex = 178 % 32; // 178%32得到在arr[5]上的160~191比特位置的哪个位置,得到18
int s = (arr[numIndex] >> bitIndex) & 1; //得到第178位的状态

//把178位的信息改为1
arr[numIndex] = arr[numIndex] | (1 << bitIndex)

//把178位的信息改为0
arr[numIndex] = arr[numIndex] & (~(1 << bitIndex))

5.2黑名单URL问题

题目描述：

现在有一个大文件中存放着100亿条URL，每条URL大小为64Byte，如何判断一条URL是否在此文件中出现过。

分析：

如果把100亿条URL全部放入HashSet里，100亿*64 = 640G，这需要640G的内存，几乎是不现实的选择，如果存到硬盘中，读取又花费相当长的时间，如何将这100亿条URL记录放到内存当中呢？

应用：

布隆过滤器是有常见应用场景的，比如说日常我们使用搜索引擎，如何避免用户搜寻到敏感不健康的链接，如何筛选URL黑名单等。

解答：

首先实现一个长度为m的位图，另外我们还需要K个独立的哈希函数，对每一个URL都进行K个哈希函数的计算，得到K个哈希值，这K个哈细值对m进行取模运算，得到需要改变为1状态的bit位置。然后换下一个URL，知道把100亿个URL全部操作完成，布隆过滤器就完成了。下面是个伪代码的实现过程。

int[] bitArr = new int[m];
int i = 0;
//把每一个URL的信息写进布隆过滤器中
while(url){

    //每个URL都进行K个独立的哈希函数的运算，对应K个位置的信息
    while(i < K){

        //求该URL在第i个哈希函数下求得需要改变位图位置
        int temp = hashFunction_i(url);
        int res_bit_position = temp % m;

        //把在该哈希函数求的的bit位置信息状态改为1
        int numIndex = res_bit_position / 32;
        int bitIndex = res_bit_position % 32;
        bitArr[numIndex] = arr[numIndex] | (1 << bitIndex);

        i++;
    }

    url++;
}

那么现在我们有了布隆过滤器，已经将URL都填进了黑名单中，那么接下来就是如何检测某一个URL是否出现在黑名单当中。依旧是伪代码实现过程如下：

i = 0；
int res = 1;
while(i < K) {

    //求url_x在第i个哈希函数下求得需要获取的位图位置
    int temp = hashFunction_i(url_x);
    int res_bit_position = temp % m;

    //取url_x在该哈希函数下求得的位置的状态
    int numIndex = res_bit_position / 32;  
    int bitIndex = res_bit_position % 32; 
    s = (arr[numIndex] >> bitIndex) & 1;
 
    //将K次位置的信息进行与操作
    res = s & res;
}

//如果res为1也就是，每次求得的位置都为1，可以认为该URL在黑名单中，返回true
return res?true:false;

以上就是整个布隆过滤器的实现和检测过程，但是读者可能会疑惑，还有两个未知量没有讨论，位图的大小m和K个独立的哈希函数，这两个参数呢放到下一小结5.3中讨论。

单记录的大小是不影响布隆过滤器的大小的，也就是布隆过滤器大小不跟单样本大小有关，只和样本个数有关。

5.3失误率

由于哈希函数的性质，不同的输入也有可能获得相同的结果，所以布隆过滤器是有一定失误率的，但是这个失误类型的判错是不会判错必为已存在信息的，通俗说就是宁可错杀一千，绝不放过一个。只可能将好人误判为坏人，不会将坏人判成好人的。

失误率是和上一小节末要讨论的两个参数，位图大小m和哈希函数个数K有关系的。这个很好理解，位图越短，那么位图状态为1的比例就越高，失误率越高；位图太长又很浪费。那么究竟多少合适呢，科学家们已经帮我们算好了，具体推导过程非常复杂，完全没有必要去浪费时间研读，直接记住公式就好了：

$m = -\frac{N*ln^{P}}{(ln^{2})^2}$ ， $K = ln^{2} * \frac{M}{N}$

P是失误率，还是以URL的例题来说，假设100亿个URL，也就是公式中的N，我们的预期失误率为0.0001，万分之一，那么计算的结果为m的大小为26G，K为13，二者都为向上去整。理论值就是这样的，但是在实际应用中m可以根据实际情况大一点点，这样求得的m，K都要略大于理论值。如此一来，实际失误率也会比预期的失误率更小，我们也可以反推求得实际的失误率为：

$P_{real} = (1-e^{-\frac{n*K}{m} })^K$

下面两张坐标图简单直观地表明了P m K之间的关系。

6.在分布式存储中运用的一致性哈希原理

当下大数据的火热使得HDFS应用广泛，而分布式数据存储中就用了哈希算法，这里重点说为何要使用一致性哈希。

最原始的分布式数据库大概长下面这个样子：

底层的数据服务器实际含有三台，逻辑服务器统一封装，对外表现为一个数据库入口，当新来一条record的时候，该record进行哈希运算，结果对3取模，得到的结果就是要存入哪台物理数据服务器的编号。这样做不仅分担了数据库的压力，而且由于哈希函数的离散性的性质，三台数据库服务器都将负载均衡。在工程上，hashkey的选择是有讲究的，是专门用来计算哈希值的输入，种类最好是多一些，这样对于操作频率存在差异的数据，就可以做到负载均衡。比如对比姓名和国家，姓名就很适合作为hash key，而国家就不合适，因为姓名种类很多，重名很小，但是对于国家，种类较少，能够经常上热搜榜的，用来被搜索和查询的国家数量就更少了，这样就很容易对某一台或某几台数据服务器造成很大的负担，而对冷门的国家名称所在的服务器来说，又是性能过剩的。

以上是最传统最原始的分布式数据存储，那么它有什么缺点呢？缺点就是，一旦数据服务器需要扩增，则原来计比如说上图三台变成四台，那么最初计算的服务器编号选择就失效了，此时应该是对4进行求模，这样一来，扩增数据服务器的代价就很高了，数据迁移将耗费大量的时间，毕竟要全部重新计算哈希值，重新选择存放的数据库服务器。那么如何解决呢，就是本节要讨论的一致性哈希原理。

我们考虑把三台服务器在逻辑上看作在一个环上，具体的操作呢，我们可以把每台机器的hostname作为hash key，计算出来哈希值，然后将这个哈希值再次进行哈希，得到环上对应的位置。

现在我们尝试插入一条记录record：（zhangsan，25），张三25岁这个记录，我们假设以姓名作为hash key计算此条记录的哈希值value，将此条记录存在value在环的顺时针方向上最近的机器上。那么为何这样可以避免前面提到的传统分布式数据库的数据迁移代价呢？我们来看看扩增一台数据服务器是什么样的，假设m4计算之后位于m2和m3之间：

回顾刚提到的插入一条记录的过程，是不是扩增后m3的数据就其实不一定是存在m3上了，加入数据条目计算的value位于m2和m4之间，那么就应该保存在m4上，但是m1和m2呢，并不会被影响，所以也就是原本由m3负责的数据，部分需要迁移到m4上，而与m1，m2完全无关，这样就不需要全量迁移了，大大提高了效率。

用户面对的是逻辑服务器层，并不知道真实的物理服务器的情况，那么如何顺时针找到是哪台物理数据库服务器呢？其实就是让machine hash code进行排序，这个就是服务器计算应该在环的那个位置的那个值，把所有的值进行排序，这个序列就是顺时针机器的排列顺序，我们让所有的逻辑服务器都备份一份这个序列，也就可以让数据顺时针对应找到应该在的位置了。

缺点：

机器数量很少时，哈希环不一定平分；
即便初始哈希环上的机器状态为平分哈希环，扩充后也就不再平衡了；

解决：

使用虚拟节点技术，还是三台物理数据服务器的例子，我们给每个机器分配1000个字符串，看作是1000个虚拟节点。

我们让虚拟节点去枪环，3000个值很交错的分布在哈希环上，这样当一条record插入时，顺时针找到最近的虚拟节点进行插入，但是实际选择的是该虚拟节点对应的物理服务器，比如我们在换上选择了b666这个虚拟节点，实际上这条记录是存在了m2中、这样做的好处不仅在增减服务器时不会出现刚才提到的物理机在哈希环上分布不均匀的情况，而且这样负载也比较均衡。进一步地，通过虚拟节点技术还可以做负载管理得工作，比如m1机器性能好一些，那么我们就给m1多分配一些字符串，如此一来哈希环上属于m1的虚拟节点就占了更多的位置，m1自然也就分担了更多的负载，可以充分发挥m1性能好的优势。

总结

哈希函数和哈希表其实原理容易懂，但是还是挺难得，希望本篇文章能让你觉得和详细介绍哈希的基础知识的文章收获不同，个人水平有限，如有错误欢迎指正。

收起

展开全文

数据结构算法

哈希算法

2020-08-17 15:01:34

哈希算法的目的就是为了验证原始数据是否被篡改。 Java字符串的hashCode()就是一个哈希算法，它的输入是任意字符串，输出是固定的4字节int整数: "hello".hashCode(); //0x5e918d2 "hello, java".hashCode(); //...

哈希算法(Hash)又称摘要算法(Digest),它的作用是:对任意一组输入数据进行计算，得到一个对固定长度额输出摘要。

哈希算法最重要的特点就是:

相同的输入一定得到相同的输出；
	不同的输入大概率得到不同的输出。
哈希算法的目的就是为了验证原始数据是否被篡改。

Java字符串的hashCode()就是一个哈希算法，它的输入是任意字符串，输出是固定的4字节int整数:


"hello".hashCode(); //0x5e918d2

"hello, java".hashCode(); //0x7a9d88e8

"hello, bob".hashCode(); //0xa0dbae2f


两个相同的字符串永远会计算出相同的hashCode，否则基于hashCode定位的HashMap就无法正常工作。这也是为什么当我们自定义一个class时，覆写equals()方法时我们必须正确覆写hashCode()方法。

哈希碰撞

哈希碰撞是指，两个不同的输入得到了相同的输出:


"AaAaAa".hashCode();  //0x7460e8c0

"BBAaBB".hashCode(); //0x7460e8c0


有童鞋会问：碰撞能不能避免？答案是不能。碰撞是一定会出现的，因为输出的字节长度是固定的，String的hashCode()输出是4字节整数，最多只有4294967296种输出，但输入的数据长度是不固定的，有无数种输入。所以，哈希算法是把一个无线的输入集合映射到一个有限的输出集合，必然会产生碰撞。

碰撞不可怕，我们担心的不是碰撞，而是碰撞的概率，因为碰撞概率的高低关系到哈希算法的安全性。一个安全的哈希算法必须满足:

碰撞概率低;
	不能猜测输出。
不能猜测输出是指，输入的任意一个bit的变化会造成输出完全不同，这样就很难从输出反推输入(只能依靠暴力穷举)。假设一种哈希算法有如下规律:


hashA("java001") = "123456"

hashA("java002") = "123457"

hashA("java003") = "123458"


那么很容易从输出123459反推输入，这种哈希算法就不安全。安全的哈希算法从输出是看不出任何规律的:


hashB("java001") = "123456"

hashB("java002") = "580271"

hashB("java003") = ???


常用的哈希算法有:

算法
			输出长度（位）
			输出长度（字节）
		
MD5
			128 bits
			16 bytes
		
SHA-1
			160 bits
			20 bytes
		
RipeMD-160
			160 bits
			20 bytes
		
SHA-256
			256 bits
			32 bytes
		
SHA-512
			512 bits
			
			64 bytes
			
		
根据碰撞概率，哈希算法的输出长度越长，就越难产生碰撞，也就越安全。

Java标准库提供了常用的哈希算法，并且有一套统一的接口。我们以MD5算法为例，看看如何对输入计算哈希:

import java.math.BigInteger;
import java.security.MessageDigest;

public class Main {
    public static void main(String[] args) throws Exception {
        // 创建一个MessageDigest实例:
        MessageDigest md = MessageDigest.getInstance("MD5");
        // 反复调用update输入数据:
        md.update("Hello".getBytes("UTF-8"));
        md.update("World".getBytes("UTF-8"));
        byte[] result = md.digest(); //16 bytes:68e109f0f40ca72a15e05cc22786f8e6
        System.out.println(new BigInteger(1, result).toString(16));
    }
}


 

使用MessageDigest时，我们首先根据哈希算法获取一个MessageDigest实例，然后，反复调用update(byte[])输入数据。当输入结束后，调用digest()方法获得byte[]数组表示的摘要，最后，把它转换为十六进制的字符串。

运行上述代码，可以得到输入HelloWorld的MD5是68e109f0f40ca72a15e05cc22786f8e6。

哈希算法的用途

因为相同的输入永远会得到相同的输出，因此，如果输入被修改了，得到的输出就会不同。

我们在网站上下载软件的时候，经常看到下载页显示的哈希：



如何判断下载到本地的软件是最原始的、未经篡改的文件?我们只需要自己计算一下本地文件的哈希值，再与官网公开的哈希值对比，如果相同，说明文件下载正确，否则，说明文件已被篡改。

哈希算法的另一个重要用途是存储用户口令。如果直接将用户的原始口令存放到数据库中，会产生极大的安全风险:

数据库管理员能够看到用户明文口令;
	数据库数据一旦泄露，黑客即可获取用户明文口令。
不存储用户的原始口令，那么如何对用户进行认证?

方法是存储用户口令的哈希，例如，MD5.

在用户输入原始口令后，系统计算用户输入的原始口令的MD5并与数据库存储的MD5对比，如果一致，说明口令正确，否则，口令错误。

因此，数据库存储用户名和口令的表内容应该像下面这样:

username
			password
		
bob
			f30aa7a662c728b7407c54ae6bfd27d1
		
alice
			25d55ad283aa400af464c76d713c07ad
		
tim
			bed128365216c019988915ed3add75fb
		
这样一来，数据库管理员看不到用户的原始口令。即使数据库泄露，黑客也无法拿到用户的原始口令。想要拿到用户的原始口令。想要拿到用户的原始口令，必须用暴力穷举的方法，一个口令一个口令地试，直到某个口令计算的MD5恰好等于指定值。

使用哈希口令时，还要注意防止彩虹表攻击。

什么是彩虹表呢?上面讲到了，如果只拿到MD5,从MD5反推明文口令，只能使用暴力穷举的方法。

然而黑客并不笨，暴力穷举会消耗大量的算力和时间。但是，如果有一个预先计算好的常用口令和它们的MD5的对照表:

常用口令
			MD5
		
hello123
			f30aa7a662c728b7407c54ae6bfd27d1
		
12345678
			25d55ad283aa400af464c76d713c07ad
		
passw0rd
			bed128365216c019988915ed3add75fb
		
19700101
			570da6d5277a646f6552b8832012f5dc
		
…
			…
		
20201231
			6879c0ae9117b50074ce0a0d4c843060
		
 

这个表就是彩虹表。如果用户使用了常用口令，黑客从MD5一下就能反差到原始口令:

bob的MD5: f30aa7a662c728b7407c54ae6bfd27d1，原始口令：hello123；

alice的MD5：25d55ad283aa400af464c76d713c07ad，原始口令：12345678；

tim的MD5：bed128365216c019988915ed3add75fb，原始口令：passw0rd。

这就是为什么不要使用常用密码，以及不要使用生日作为密码的原因。

即使用户使用了常用口令，我们也可以采取措施来抵御彩虹表攻击，方法是对每个口令额外添加随机数，这个方法称之为加盐(salt):

digest = md5(salt +inputPassword)

经过加盐处理的数据库表，内容如下:

username
			salt
			password
		
bob
			H1r0a
			a5022319ff4c56955e22a74abcc2c210
		
alice
			7$p2w
			e5de688c99e961ed6e560b972dab8b6a
		
tim
			z5Sk9
			1eee304b92dc0d105904e7ab58fd2f64
		
 

加盐的目的在于使黑客的彩虹表失效，即使用户使用常用口令，也无法从MD5反推原始口令。

SHA-1

SHA-1也是一种哈希算法，

它的输出是160 bits，即20字节。SHA-1是由美国国家安全局开发的，SHA算法实际上是一个系列，包括SHA-0（已废弃）、SHA-1、SHA-256、SHA-512等。

在Java中使用SHA-1，和MD5完全一样，只需要把算法名称改为"SHA-1"：

import java.math.BigInteger;
import java.security.MessageDigest;

public class Main {
    public static void main(String[] args) throws Exception {
        // 创建一个MessageDigest实例:
        MessageDigest md = MessageDigest.getInstance("SHA-1");
        // 反复调用update输入数据:
        md.update("Hello".getBytes("UTF-8"));
        md.update("World".getBytes("UTF-8"));
        byte[] result = md.digest(); // 20 bytes: db8ac1c259eb89d4a131b253bacfca5f319d54f2
        System.out.println(new BigInteger(1, result).toString(16));
    }
}

 

类似的，计算SHA-256，我们需要传入名称"SHA-256"，计算SHA-512，我们需要传入名称"SHA-512"。Java标准库支持的所有哈希算法可以在这里查到。

 注意：MD5因为输出长度较短，短时间内破解是可能的，目前已经不推荐使用。

小结

哈希算法可用于验证数据完整性，具有防篡改检测的功能；

常用的哈希算法有MD5、SHA-1等；

用哈希存储口令时要考虑彩虹表攻击。

算法	输出长度（位）	输出长度（字节）
MD5	128 bits	16 bytes
SHA-1	160 bits	20 bytes
RipeMD-160	160 bits	20 bytes
SHA-256	256 bits	32 bytes
SHA-512	512 bits	64 bytes

username	password
bob	f30aa7a662c728b7407c54ae6bfd27d1
alice	25d55ad283aa400af464c76d713c07ad
tim	bed128365216c019988915ed3add75fb

常用口令	MD5
hello123	f30aa7a662c728b7407c54ae6bfd27d1
12345678	25d55ad283aa400af464c76d713c07ad
passw0rd	bed128365216c019988915ed3add75fb
19700101	570da6d5277a646f6552b8832012f5dc
…	…
20201231	6879c0ae9117b50074ce0a0d4c843060

username	salt	password
bob	H1r0a	a5022319ff4c56955e22a74abcc2c210
alice	7$p2w	e5de688c99e961ed6e560b972dab8b6a
tim	z5Sk9	1eee304b92dc0d105904e7ab58fd2f64

收起

展开全文

哈希表(Hash Table)-哈希概述
2019-03-28 11:11:16
哈希表支持一种最有效的检索方法：散列。从根来上说，一个哈希表包含一个数组，通过特殊的索引值（键）来访问数组中...计算哈希值和在数组中进行索引都只消耗固定的时间，因此哈希表的最大亮点在于它是一种运行时...
收起
一致性哈希表分布式哈希表_哈希表和哈希表的无代码指南
2020-08-18 12:18:09
一致性哈希表分布式哈希表If you have programmed before, you are sure to have come across hashing and hash tables. Many developers have used hash tables in one form or another, and beginner developers ...
收起
数据结构 python java 机器学习算法
哈希表概述
千次阅读 2018-05-22 21:46:50
一、什么是哈希表？        哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键...
收起
哈希相关
2012-09-16 20:58:05
google搜索到的头条：散列表（也叫哈希表），是根据关键码值直接进行访问的数据结构，也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散...
收起
数据结构算法 hashmap 存储 byte
哈希表与哈希函数简介
2017-06-01 20:52:42
哈希表通过查找关键字不需要比较就可获得需要的记录的存储位置。即存储位置=f(关键字) 这就是一种新的存储技术---散列技术（哈希技术）散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每...
收起
哈希表大总结
2020-11-26 18:32:09
哈希表总结哈希表记录的存储位置和它的关键字之间建立一确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。因而查找时，只需根据这个对应关系f找到给定值K的像f(K）。若结构中存在关键字和K相等...
收起
算法数据结构 java
数据结构哈希表(Hash Table)_哈希概述
2017-12-07 06:30:00
哈希表支持一种最有效的检索方法：散列。从根来上说，一个哈希表包含一个数组，通过特殊的索引值（键）来访问数组中...计算哈希值和在数组中进行索引都只消耗固定的时间，因此哈希表的最大亮点在于它是一种运行时...
收起
哈希函数简介
2013-08-18 12:28:54
这里把这种对应关系f称为散列函数，又称为哈希（Hash）函数。按这个思想，采用散列技术将记录存在在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表。那么，关键字对应的记录存储位置称为散列地址。散列...
收起
C HASH 技术
局部敏感哈希
千次阅读 2016-01-21 22:47:10
局部敏感哈希在检索技术中，索引一直需要研究的核心技术。当下，索引技术主要分为三类：基于树的索引技术（tree-based index）、基于哈希的索引技术（hashing-based index）与基于词的倒排索引（visual words ...
收起
算法
加盐哈希
2016-03-15 13:33:23
最好的办法就是对密码进行加盐哈希，这篇文章将介绍它是如何做到这点。在对密码进行哈希加密的问题上，人们有许多争论和误解，这大概是由于网络上广泛的误传吧。密码哈希是一件非常简单的事情，但是依然有很多人...
收起
整数哈希介绍
千次阅读 2016-06-07 11:45:22
为什么要整数哈希 http://www.cnblogs.com/napoleon_liu/archive/2010/12/29/1920839.html 很多时候，可以直接用整数作为键，比如QQ号码，手机号码，但这些号码的分布性不是均匀的（比如高位的变化更少，低位...
收起
算法
“分布式哈希”和“一致性哈希”的概念与算法实现
千次阅读 2011-07-26 17:37:23
分布式哈希和一致性哈希是分布式存储和p2p网络中说的比较多的两个概念了。介绍的论文很多，这里做一个入门性质的介绍。　分布式哈希(DHT) 　两个key point：每个节点只维护一部分路由；每个节点只存储一部分数据...
收起
算法网络分布式存储存储 cassandra
数据结构之哈希
2019-04-09 13:59:34
什么是哈希表哈希表就是一种以键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其对应的值。哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：...
收起
什么是哈希算法
千次阅读 2018-05-07 18:27:19
哈希函数，又称哈希算法，它通过一个函数，把任意长度的数据转换为一个长度固定的数据串（通常用16进制的字符串表示）。 Hash算法特别的地方在于它是一种单向算法，用户可以通过Hash算法对目标信息生成一段特定长度...
收起
Hash
基于哈希函数的签名
千次阅读 2019-05-13 18:28:28
（这里当然存在许多例外，但最棒的部分在于，不论 X 属于什么分布，找到 X 的时间成本和暴力搜寻相同。）抗-次原像攻击：这和前者有些微的差别。给定输入 X，对于攻击者来说，要找到另一个 X' 使得 H(X)=H(X') ...
收起
哈希的基本操作
2018-08-30 13:27:54
哈希哈希冲突闭散列开散列头文件定义代码各个功能解析初始化插入查找删除完整代码前言理想的搜索方式：可以不经过任何比较，一次直接从表中得到要搜索的元素，构造一种结构，通过某种函数使...
收起
哈希表&一致性哈希&超有爱的并查集
2019-05-11 22:14:07
哈希函数，哈希表与布隆过滤器2. 设计RandomPool结构3. 一致性哈希4. 并查集结构5. 并查集结构应用【岛问题】 1. 哈希函数，哈希表与布隆过滤器链接： ...
收起
算法
“分布式哈希”和“一致性哈希”
2015-02-08 10:57:42
分布式哈希(DHT) 　两个key point：每个节点只维护一部分路由；每个节点只存储一部分数据。从而实现整个网络中的寻址和存储。 DHT只是一个概念，提出了这样一种网络模型。并且说明它是对分布式存储很有好处的。但...
收起
哈希猫很牛吗
2021-06-16 16:52:14
哈希猫(Hashcat)是一款在渗透人员、系统管理员，甚至是网络罪犯和网络...它的优点在于瞬间加密，但如果想暴力破解将函数逆向出来，以目前的计算机算力而言，在我们有生之年几乎是不可能的。（数世咨询：王小云教授的破
收起
perl学习笔记——哈希
2015-07-22 16:58:00
哈希是一种数据结构，它和数组的相似之处在于可以容难任意多的值并能按需取用，而他和数组的不同在于索引的方式，数组是以数字为索引而哈希则是以名字为索引。哈希的键是唯一的，哈希的值可以重复。哈希的应用...
收起
什么是哈希表？为什么要使用哈希表？哈希表的实现原理？哈希冲突怎么解决？
千次阅读 2019-09-06 16:50:39
　所以，本方法的关键在于选择合适的p，若是p选择的不好，就可能产生同义词；根据前人经验，若散列表的表长为m，通常p为小于或等于表长（最好接近m）的最小质数或不包含小于20质因子的合数。　　⑥、随机数法 ...
收起
hash表 hash结构数据结构
加密与安全——哈希算法
2021-03-15 21:02:44
哈希算法（Hash）又称摘要算法（Digest），它的作用是：对任意一...哈希算法的目的就是为了验证原始数据是否被篡改。 Java字符串的hashCode()就是一个哈希算法，它的输入是任意字符串，输出是固定的4字节int整数： ...
收起
分布式哈希和一致性哈希的概念与算法实现
2012-04-09 16:56:51
“分布式哈希”和“一致性哈希”的概念与算法实现 (2011-1-24 04:01:50) 标签：分类：搜索技术　分布式哈希和一致性哈希是分布式存储和p2p网络中说的比较多的两个概念了。介绍的论文很多，这里做一个入门...
收起
算法网络分布式存储存储 cassandra

哈希表

哈希索引

静态哈希

桶溢出

静态哈希的缺点

动态哈希

可扩充散列

查询操作

插入操作

删除操作

比较分析

顺序索引和散列索引的比较分析

B+ 树索引和哈希索引的比较分析

Q&A

问：顺序索引与散列索引的适用场景？

问：可扩充散列为什么需要局部深度和全局深度？

总结

参考

【哈希】关于哈希表和哈希函数的理解与应用

0.概述

1.哈希的函数的定义以及性质

2.哈希表的扩容和复杂度

3.哈希算法的应用--大文件统计高频数字

4.设计RandomPool结构

5.布隆过滤器

5.1位图

5.2黑名单URL问题

5.3失误率

6.在分布式存储中运用的一致性哈希原理

总结

哈希算法

哈希碰撞

哈希算法的用途

SHA-1

小结

哈希表(Hash Table)-哈希概述

一致性哈希表 分布式哈希表_哈希表和哈希表的无代码指南

哈希表概述

哈希相关

哈希表与哈希函数简介

哈希表大总结

数据结构 哈希表(Hash Table)_哈希概述

哈希函数简介

局部敏感哈希

加盐哈希

整数哈希介绍

“分布式哈希”和“一致性哈希”的概念与算法实现

数据结构之哈希

什么是哈希算法

基于哈希函数的签名

哈希的基本操作

哈希表&一致性哈希&超有爱的并查集

“分布式哈希”和“一致性哈希”

哈希猫很牛吗

perl学习笔记——哈希

什么是哈希表？为什么要使用哈希表？哈希表的实现原理？哈希冲突怎么解决？

加密与安全——哈希算法

分布式哈希和一致性哈希的概念与算法实现

哈希的目的在于

一致性哈希表分布式哈希表_哈希表和哈希表的无代码指南

数据结构哈希表(Hash Table)_哈希概述