本文由 简悦 SimpRead 转码， 原文地址 www.iocoder.cn
摘要: 原创出处 blog.csdn.net/liweisnake/article/details/104779497 「liweisnake」欢迎转载，保留摘要，谢谢！ 关于 java 中 hash 的数据……
扫码关注公众号： 芋道源码
发送： 百事可乐
获取永久解锁本站全部文章的链接
摘要: 原创出处 blog.csdn.net/liweisnake/article/details/104779497 「liweisnake」欢迎转载，保留摘要，谢谢！
最近对 hash 有了更多深入的理解。这里也写篇文章专门来聊聊 hash。
Hash 是一种常见的数据结构或者说计算方法，以其 O(1) 的时间算法复杂度闻名于世。曾有人说，如果世界上只有一种数据结构，那么我选择 hash，足见 hash 的地位及牛逼之处，而代码编写中 hash 也屡见不鲜，因为他实在是太常见太好用了。
但是实际使用过程中，基本的 hash 是远远不够的，按照用途，对 hash 其实还有如下需求：
- 并发安全。
对这个需求，java 中有了 HashTable，为了进一步提升性能，于是有了使用分段锁的 ConcurrentHashMap，亦不做赘述。
- 大数据 hash。
传统的 HashMap 中除了 key, value 外，每个 entry 还要存 16 个 byte 的 class header，4byte 的 hash 值，以及 8byte 的指向下一个元素的指针，这样的结构在遇到大数据量时就会更加耗内存，更容易导致 GC。
由对象头过大可以看出来，只要能够有一种结构消灭这个额外的 entry 对象，则此处将大大减少内存的消耗。
一种可行的方式是：采用二级索引保存的方式，第一级索引由 Short2ShortMap 保存一个 short 为 key 且 short 为 value 的 Map 结构，第二级索引则由许多数组构成，这些数组负责将被消灭 value 这个 Object 拆解为基本类型并用多个数组保存，而一级索引的 value 保存的 value 正是二级数组的 index。通过这种变换，消灭了额外的 entry 对象从而大幅减少内存。需要注意的是，这种方式适用于使用了大量 HashMap，但是每个 Map 内数据量较小的情况（受 short 的限制只有 3w 多 index），如果每个 Map 内数据量也比较大，可以考虑 Int2IntMap，当然，这样减少内存占用的效果就不如 Short2ShortMap 了。
- 其他。
ImmutableMap，Guava 库，在初始化完毕后就没法再 put 做改变了。
SortedMap，Guava 库，数据会按 key 做字母化排序。
BiMap，Guava 库，创建完之后可以使用 inverse 将 value 和 key 颠倒过来，前提是保证 value 也是唯一的。
MultiMap，Guava 库，可以对每个 key 关联多个值，并且可以很方便的对 list 进行分组。
Hash 冲突。众所周知，解决 hash 冲突最好的办法自然是提升 hash table 的总数量（即 N 的大小），如果待存放元素的数量 k 远小于 N，则 hash 后有更大概率占据空槽，而冲突越少则性能越好，本质上，这是一种以空间换时间的方式。然而现实中，存储空间也很宝贵，任何公司都很难接受让大量空间浪费。于是，便出现了尽可能增加空间占用但不过分降低性能的 hash。
布谷 hash。布谷 hash 是一种解决冲突的方法。不同于线性探测，开放定址这样的常规方法，布谷 hash 借鉴了布谷鸟占人巢穴生子的寓意。其算法比较简单，采用两个（或多个）hash 函数 F1 和 F2，put 操作时用 F1 或 F2 计算 hashcode 并定位，如果任意位置为空，则插入；否则挤占其中一个位置，并将被挤占的元素拿出并重复该过程；而 get 操作则让人比较困惑，到底采用哪个函数来 get 值呢？实际上布谷 hash 需要在 value 中存放 key 值，这样对于两个函数 get 到的值只要判断中间 key 是否正确就可以确认其对应的 hash 函数。布谷 hash 在二维时空间利用率较高，约为 80%-90%。下图是对 put 操作的一个表示。
参考 https://coolshell.cn/articles/17225.html
bloomfilter。布隆过滤器是一种占小空间且效率很高的算法，通常用来解决垃圾邮件识别，缓存击穿及日活计算等场景。bloomfilter 只能判断一个元素可能在其中或者一个元素一定不在其中。他的算法也采用多个 hash 函数，如下例，某数据 A 经过 x 函数可以映射到 4,9 两个位置，经过 z 函数可以映射到 9,14 两个位置，经过 y 函数可以映射到 14,19 两个位置。于是基本的增加操作便可以将这几个对应位置的值置为 1；对于基本的查找操作，则对 A 进行 hash 后找到其所有对应位置，发现其所有对应位置都是 1，则表示 A 很可能存在，为什么不能确定呢，因为有可能这些位置并不是对 A 进行 hash 后对应的位置，有可能是插入了 BCDE 等数据而这些数据刚好覆盖了 A 的所有位置而导致的，所以发现全 1 仅仅能判断其可能存在；但是一旦有任意对应位置为 0，则表示 A 一定不存在。对于基本的删除和更新操作，布隆过滤器是不支持的，本质原因是位置是多数据共享的，任何对数据的逆向操作都会导致其他数据的不准。布隆过滤器在 Guava 中有现成的实现。
参考 https://juejin.im/post/5de1e37c5188256e8e43adfc
__Count–min sketch**。Count-min sketch 旨在解决流式大数据下做计数统计时间空间复杂度过高的问题。设想这样一个场景，线上数据源源不断的进来，现在我们需要去统计 cache 中每个 ip 请求的大致数量，从而确定哪个 ip 来的请求是 hot 的。碰到这个问题，可能本能的会想用 HashMap，用 ip 作为 key，用总 count 当做 value。但实际上当数据量足够大时，各种噩梦就来了，比如每台机器内存非常高（对应上面说到的大数据 hash 带来的问题），hash 冲突也变高，rehash 成本也会迅速增加，并且在实时响应的要求下，时间上就很可能无法满足需求，Count-min sketch 算法就是为此而生的。
count-min sketch 算法思想比较简单，采用 n 个数组以及 n 个 hash 函数，对同一个数据用不同的 hash 函数做 hash，分配到这 n 个数组不同的位置，存值时这个位置所在的 value 加 1，取值时取这 n 个位置最小值，则此最小值大致接近实际总 count 数，且总是大于等于实际的总 count 数。为啥要取最小值，并且为啥结果总是大于等于实际总 count 数呢，原因其实与 bloomfilter 比较像，有可能有其他的 hash 也落到了该位置并加了 count。参考下图。在 java 中，著名的 caffeine 缓存框架中的 W-TinyLFU 就用的 Count-min sketch 来记录访问频率
参考 https://www.cnblogs.com/liujinhua306/p/9808500.html
4.hash 分散。大多数情况下，希望 hash 之后的结果越分散越无规律越好。
Murmur hash。Murmur 哈希是一种比大多数算法更为分散更无规律的算法。
java 中的 hash 算法称为 Horner，简单表示就是
for (int i = 0; i < str.length(); i++) { hash = 31*hash + str.charAt[i]; }
实际计算时经常使用移位操作。
Murmur 的意思是 multiply and rotate，主要优点是速度快且 hash 值足够分散，目前已经在各大框架广泛使用，比如 redis，memcache，cassandra，lucene，如下是其简单表示。
x *= m; x = rotate_left(x,r);
具体算法可参考 https://zh.wikipedia.org/zh-cn/Murmur%E5%93%88%E5%B8%8C
关于 Murmur hash 的科普参考这里 http://calvin1978.blogcn.com/articles/murmur.html
5.hash 聚集。少数情况下，希望通过 hash 能让相似的内容在 hash 过后仍然相似，而不是一点改动便面目全非。
simhash。simhash 是一种局部敏感 hash，对于 google 百度这样的大搜索公司，用空间向量去计算文档相似度显得既慢又笨重，simhash 用一种相似则海明距离近的方式巧妙而快速的解决了文档相似的比较。这对 hash 提出了另一种不同的要求，以往 hash 函数的目的是为了足够分散，而这里却希望 hash 后呈现一定的规律，实际上个人觉得这更像是一种编码，根据这种编码规则，相似的文档在 hash 值上的海明距离更近。
算法这里不再赘述，可参考 https://wizardforcel.gitbooks.io/the-art-of-programming-by-july/content/06.03.html
- 其他特殊 hash。
一致性 hash。一致性 hash 主要是为了解决传统的取模为主的 hash 将数据分配到 n 台服务器之后，服务器再扩容或缩容所带来的所有数据需要重新计算 hash 的问题。这种情况对于线上某些重要的服务往往是不可接受的。于是一致性 hash 出现了，它通过将 hash 值空间预先分配到一个超级大的虚拟节点上，再通过实体节点就近接管虚拟节点来解决映射问题。如图，这个超级大的虚拟节点即是 2^32 个，真正的的实体节点只有 4 个，由于顺时针就近映射，每个实体节点都将接管落入前面一个实体节点以后的所有虚拟节点的值，这样每次扩容时只会影响最多一个节点。一致性 hash 基本人尽皆知，这里就不列举资料了。
Perfect hash。perfect hash 目的是为了实现完全无冲突的 hash。perfect hash 分为两种，一种是静态 hash，一种是动态 hash；对于静态 hash 而言，一个最好的例子就是数组，比如总的值有 10 个，取 hash 值后分别映射到 3，8，13，18，22，44，53，63，78，92 这 10 个位置，则我们用一个长度为 100 的数组可以实现该值域的静态 perfect hash。但是你可能会发现有多余的位置并没有被用上，如果能实现长度 10 的数组完美映射这 10 个数字，则称之为最小完美 hash。动态 perfect hash 一般比较麻烦，需要做二次 hash 映射并要第二次映射不会冲突，有兴趣可以查阅相关资料。
GeoHash。GeoHash 是比较特殊的 hash 应用，主要是用来快速定位。其原理相对简单（实现起来有不少细节）。主要就是将每一级的地图划分为 32 块，即每一级用 5bit 来标识（为啥是 5bit，因为最后用 base32 的编码方式，每个字母或数字 5bit），每次缩放一级则用另一个字母或数字标识，最终能得到一串字符串 wx4gjk32kfrx，从而一级一级定位直到最小那一级。如划分 10 级，则最后字符串长度为 4，范围到 20km，如划分 20 级，则最后字符串长度为 8，范围可以精确到 19m。
