常用算法之哈希算法

前言

程序员对哈希算法应该都不陌生，比如业界著名的MD5、SHA、CRC等等;在日常开发中我们经常用一个Map来装载一些具有(key,value)结构的数据，利用哈希算法O(1)的时间复杂度提高程序处理效率，除此之外，你还知道哈希算法的其他应用场景吗？

1. 什么是哈希算法？

了解哈希算法的应用场景前，我们先看下散列（哈希）思想，散列就是把任意长度的输入通过散列算法变换成固定长度的输出，输入称为Key(键)，输出为Hash值，即散列值hash(key)，散列算法即hash()函数（散列与哈希是对hash的不同翻译）；实际上存储这些散列值的是一个数组，称为散列表，散列表用的是数组支持按照下标随机访问数据的特性，把数据值与数组下标按散列函数做的一一映射，从而实现O(1)的时间复杂度查询；

1.1 散列冲突

目前的哈希算法MD5、SHA、CRC等都无法做到一个不同的key对应的散列值都不一样的散列函数，即无法避免出现不同的key映射到同一个值的情况，即出现了散列冲突，而且，因为数组的存储空间有限，也会加大散列冲突的概率。如何解决散列冲突？我们常用的散列冲突解决方法有两类：开放寻址法(open addressing) 和 链表法(chaining)。

1.1.1 开放寻址法

通过线性探测的方法找到散列表中空闲位置，写入hash值：

如图，834313在hash表中散列到303432的位置上，出现了冲突，则顺序遍历hash表直到找到空闲位置写入834313；当散列表中空闲位置不多的时候，散列冲突的概率就会大大增加，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位，此时，我们用装载因子来表示空闲位置的多少，计算公式是：散列表的装载因子=填入表中的元素个数/散列表的长度。装载因子越大，说明空闲位置越少，冲突越多，散列表的性能就会下降。

当数据量比较小，装载因子小的时候，适合采用开放寻址法，这也是java中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。

1.1.2 链表法

链表法是一种更常用的散列冲突解决办法，也更简单。如图：

在散列表中，每个桶/槽会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中；当散列冲突比较多时，链表的长度也会变长，查询hash值需要遍历链表，这时查询效率就会从O(1)退化成O(n)。

这种解决散列冲突的处理方法比较适合大对象、大数据量的散列表，而且，支持更多的优化策略，比如使用红黑树代替链表；jdk1.8为了对HashMap做进一步优化，引入了红黑树，当链表长度太长（默认超过8）时，链表就会转换成红黑树，这时可以利用红黑树快速增删查改的特点，提高HashMap的性能，当红黑树节点个数小于8个时，又将红黑树转化成为链表，因为在数据量比较小的情况下，红黑树要维护平衡，比起链表，性能上的优势并不明显。

2. 哈希算法的应用场景

2.1 安全加密

最常用于加密的哈希算法是MD5(MD5 Message-Digest Algorithm)和SHA(Secure Hash Algorithm 安全散列算法)，利用hash的特点计算出来的hash值很难反向推导原始数据，从而达到加密的目的。

以MD5为例子，哈希值是固定的128位二进制串，最多能表示 2^128 个数据，这个数据已经是天文数字了，散列冲突的概率要小于1/2^128，如果希望通过穷举法来找到跟这个MD5相同的另一个数据，那耗费的时间也应该是天文数字了，所以在有限的时间内哈希算法还是很难被破解的，这也就达到了加密效果了。

2.2 数据校验

利用Hash函数对数据敏感的特点，可以用来校验网络传输过程中的数据是否正确，防止被恶意串改。

2.3 散列函数

利用hash函数相对均匀分布的特点，取hash值作为数据存储的位置值，让数据均匀分布在容器里面。

2.4 负载均衡

通过hash算法，对客户端id地址或者会话id进行计算hash值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。

2.5 数据分片

假如我们有1T的日志文件，里面记录了用户的搜索关键词，我们想要快速统计出每个关键词被搜索的次数，该怎么做呢？数据量比较大，很难放到一台机的内存中，即使放到一台机子上，处理时间也会很长，针对这个问题，我们可以先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度。

具体的思路是：为了提高处理速度，我们用n台机器并行处理。从搜索记录的日志文件中，依次独处每个搜索关键词，并通过哈希函数计算哈希值，然后再跟n取模，最终得到的值，就是应该被分配到的机器编号；这样哈希值相同的搜索关键词就被分配到了同一台机器上，每个机器会分别计算关键词出现的次数，最后合并起来就是最终的结果。实际上，这里的处理过程也是MapReduce的基本设计思想。

2.6 分布式存储

对于海量的数据需要缓存的情况，一台缓存机器肯定是不够的，于是，我们就需要将数据分布在多台机器上。 这时，我们可以借助前面的分片思想，即通过哈希算法对数据取哈希值，然后对机器个数取模，得到应该存储的缓存机器编号。

但是，如果数据增多，原来的10台机器已无法承受，需要扩容了，这时是如果所有数据都重新计算哈希值，然后重新搬移到正确的机器上，那就相当于所有的缓存数据一下子都失效了，会穿透缓存回源到数据库，这样就可能发生雪崩效应，压垮数据库。为了新增缓存机器不搬移所有的数据，一致性哈希算法就是比较好的选择了，主要的思想是：假设我们有kge机器，数据的哈希值范围是[0,Max]，我们将整个范围划分成m个小区间(m远大于k)，每个机器负责m/k个小区间，当有新机器加入时，我们就将某几个小区间的数据，从原来的机器中搬移到新的机器中，这样，即不用全部重新哈希、搬移数据，也保持了各个机器上数据量的平衡。

3.  写在最后

实际上，哈希算法还有很多其他的应用，比如git commit id等等，很多应用都来自于对算法的理解和扩展，也是基础的数据结构和算法的价值体现，需要我们在工作中慢慢理解和体会。

推荐教程：《Java教程》

以上是常用算法之哈希算法的详细内容。更多信息请关注PHP中文网其他相关文章！