自： CSDN作者： liweisnake
blog.csdn.net/Liwei snake/article/details/104779497
我最近对hash有了更深入的了解。 在这里也写文章谈谈hash。
Hash是一种常用的数据结构或计算方法，以其o(1)的时间算法复杂性闻名于世。 据说如果世界上只有一个数据结构的话，我会选择hash，充分看到hash的地位和牛逼之处，但是在代码编写中hash也并不少见。 因为它太普通了，太好用了。
但是，在实际使用中，基本的散列还不够，根据用途，散列有以下需求。
关于java散列的数据结构：
1 .同时安全。
为了满足这一需求，java有一个HashTable，为了进一步提高性能，使用了分段锁的ConcurrentHashMap，但在此省略说明。
2 .大数据hash。
在以往的HashMap中，除了key、value之外，各entry中还存储有指向16个字节的类头、4字节的hash值以及8字节的以下要素的指针，因此在这样的结构中，大数据量中有
从对象的头太大可以看出，如果有消除这个额外的entry对象的结构，这里可以大大减少内存的消耗。
一种可能的方法是采用Short2ShortMap中保存short为key、short为value的Map结构体的二次索引保存方式。 二级索引是将消失的名为value的对象分解为基本类型，以多个数组保存，由以一级索引的value保存的value构成的变换，消除了多余的entry对象，大幅减少了内存。 需要注意的是，此方法适用于使用大量HashMap，但每个Map中的数据量很小的情况。 (受短整型限制，只有3瓦多的索引) )如果Map中的数据量也很大，可以考虑使用Int2IntMap。 当然，这样减少存储器占有量的效果不如短2短图。
3 .其他。
初始化完成后，ImmutableMap、Guava库将无法通过put进行更改。
SortedMap、Guava库和数据按字母顺序按密钥排序。
创建BiMap、Guava库之后，可以使用inverse将值和密钥反转。 前提是value也是唯一的。
MultiMap、Guava库可以按每个密钥关联多个值，并可以很容易地对list进行分组。
关于hash的几个解决方案：
Hash碰撞。
众所周知，解决混列冲突的最佳方法当然是提高混列表的总数，即n的大小。 当储存的元素数量k远远小于n时，混列后占用空闲槽的概率会增加，碰撞越少性能越好。 本质上，这是在空间里改变时间的方式。 但是在现实中，存储空间也很宝贵，任何企业都很难接受浪费大量的空间。 于是，出现了尽可能增加占有空间，但性能不会降低太多的混列。
摇摆不定的气氛。
振动的气氛是解决冲突的方法。 与线性探测、开放场地等常规方法不同，振动的香味借鉴了布谷鸟占领人窝生孩子的意义。 其算法比较简单，采用两个(或多个) hash函数F1和F2，put操作时用F1或F2计算hashcode进行定位，如果任意位置为空则插入。 否则，占领任一位置，取出被占领的元素重复这个过程； get操作很困惑，用哪个函数获取get值呢？ 实际上振动的气氛需要在value中存储key的值，这样，对于来自两个函数get的值，只要判断中间的key是否正确，就可以确认对应的hash函数。 振动的气氛为二维，空间利用率高，约为80%-90%。 下图显示了put操作。
布龙过滤器。
光晕滤波器占用很小的空间，是一种高效的算法，经常用于解决垃圾邮件识别、缓存崩溃、日活计算等场景。 bloomfilter只能判断一个元素是否在其中，或者一个元素是否一定在其中。 他的算法也采用了多个散列函数。 在以下示例中，一个数据a可以通过x函数映射到4、9两个位置，通过z函数映射到9、14两个位置，通过y函数映射到14、19两个位置。 因此，在基本增加操作中，这些对应位置的值可以为1； 在基本的检索操作中，在对a进行混列后，找出其所有对应位置，如果其所有对应位置都是1，则表示a存在的可能性较高，但为什么不能确定，因为这些位置不是对a进行混列后的对应位置
了A的所有位置而导致的，所以发现全1仅仅能判断其可能存在；但是一旦有任意对应位置为0，则表示A一定不存在。对于基本的删除和更新操作，布隆过滤器是不支持的，本质原因是位置是多数据共享的，任何对数据的逆向操作都会导致其他数据的不准。布隆过滤器在Guava中有现成的实现。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来记录访问频率。
4.hash分散。
大多数情况下，希望hash之后的结果越分散越无规律越好。
Murmur hash。Murmuryxdzt是一种比大多数算法更为分散更无规律的算法。
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);
5.hash聚集。
少数情况下，希望通过hash能让相似的内容在hash过后仍然相似，而不是一点改动便面目全非。
simhash。simhash是一种局部敏感hash，对于google百度这样的大搜索公司，用空间向量去计算文档相似度显得既慢又笨重，simhash用一种相似则海明距离近的方式巧妙而快速的解决了文档相似的比较。这对hash提出了另一种不同的要求，以往hash函数的目的是为了足够分散，而这里却希望hash后呈现一定的规律，实际上个人觉得这更像是一种编码，根据这种编码规则，相似的文档在hash值上的海明距离更近。
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。