关于java:如果世界上只有一种数据结构我选择哈希

最近对 hash 有了更多深刻的了解。这里也写篇文章专门来聊聊 hash。

Hash 是一种常见的数据结构或者说计算方法，以其 O(1) 的工夫算法复杂度闻名于世。曾有人说，如果世界上只有一种数据结构，那么我抉择 hash，足见 hash 的位置及牛逼之处，而代码编写中 hash 也不足为奇，因为他切实是太常见太好用了。

然而理论应用过程中，根本的 hash 是远远不够的，依照用处，对 hash 其实还有如下需要：

对于 java 中 hash 的数据结构 ：

1. 并发平安 。

对这个需要，java 中有了 HashTable，为了进一步晋升性能，于是有了应用分段锁的 ConcurrentHashMap，亦不做赘述。

2. 大数据 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 了。

3. 其余 。

ImmutableMap，Guava 库，在初始化结束后就没法再 put 做扭转了。

SortedMap，Guava 库，数据会按 key 做字母化排序。

BiMap，Guava 库，创立完之后能够应用 inverse 将 value 和 key 颠倒过去，前提是保障 value 也是惟一的。

MultiMap，Guava 库，能够对每个 key 关联多个值，并且能够很不便的对 list 进行分组。

对于 hash 的一些解决方案 ：

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…

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/5de1e3…

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/liuji…

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/…

5.hash 汇集 。多数状况下，心愿通过 hash 能让类似的内容在 hash 过后依然类似，而不是一点改变便面目全非。

simhash：

simhash 是一种部分敏感 hash，对于 google 百度这样的大搜寻公司，用空间向量去计算文档类似度显得既慢又轻便，simhash 用一种类似则海明间隔近的形式奇妙而疾速的解决了文档类似的比拟。这对 hash 提出了另一种不同的要求，以往 hash 函数的目标是为了足够扩散，而这里却心愿 hash 后出现肯定的法则，实际上集体感觉这更像是一种编码，依据这种编码规定，类似的文档在 hash 值上的海明间隔更近。

算法这里不再赘述，可参考：https://wizardforcel.gitbooks…

6. 其余非凡 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。

参考：https://zhuanlan.zhihu.com/p/…

作者：liweisnake\
版权申明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协定，转载请附上原文出处链接和本申明。\
本文链接：https://blog.csdn.net/liweisn…

近期热文举荐：

1.600+ 道 Java 面试题及答案整顿 (2021 最新版)

2. 终于靠开源我的项目弄到 IntelliJ IDEA 激活码了，真香！

3. 阿里 Mock 工具正式开源，干掉市面上所有 Mock 工具！

4.Spring Cloud 2020.0.0 正式公布，全新颠覆性版本！

5.《Java 开发手册（嵩山版）》最新公布，速速下载！

感觉不错，别忘了顺手点赞 + 转发哦！