常用算法之哈希算法

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

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

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个小区间，当有新机器加入时，我们就将某几个小区间的数据，从原来的机器中搬移到新的机器中，这样，即不用全部重新哈希、搬移数据，也保持了各个机器上数据量的平衡。

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

推荐教程：《Java教程》

以上就是常用算法之哈希算法的详细内容，更多请关注其它相关文章！