最近对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开发手册（嵩山版）》最新公布，速速下载！

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