七叶笔记 » java编程 » 常用算法之哈希算法

常用算法之哈希算法

前言

程序员对哈希算法应该都不陌生,比如业界着名的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教程》

相关文章