社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
一、哈希表理解:
哈希表,别名散列表,是根据关键码值直接进行访问的数据结构,也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
数据结构中,有个时间算法复杂度O(n)的概念来衡量某种算法在时间效率上的优劣。哈希表的理想算法复杂度为O(1),也就是说利用哈希表查找某个值,系统所使用的时间在理想情况下为定值,这就是它的优势。那么哈希表是如何做到这一点的呢?这个时候问题来了,出现了这种情况ChangeToHashValue(关羽)和ChangeToHashValue(张飞)得到的值是一样的,都是 250,我们岂不是在存储过程中会遇到麻烦,怎么安排他们二位的地方呢(总不能让二位打一架,谁赢了谁呆在那吧),这就需要一个解决冲突的方法。当遇到这 种情况时我们可以这样处理,先存储好了关羽,当张飞进入系统时会发现关羽已经是250了,那咱就加一位,251得了,这不就解决了。我们查找张飞的时候也 是,一看250不是张飞,那就加个1,就找到了。这时还存在一个问题。直接用ChangeToHashValue(赵云)为251,张飞已经早早占了他的 地方,那就再加1存到252呗。呵呵,这时我们会发现,当哈希函数冲突发生的机率很高时,可能会有一群英雄豪杰在250这个值后面扎堆排队。要命的是查找 的时候,时间算法复杂度早已不是O(1)了(所以我们说理想情况下哈希表的时间算法复杂度为O(1))。 这就是说哈希函数的编写是哈希表的一个关键问题,会涉及到一个存储值在哈希表中的统计分布。如果哈希函数已经定义好了,冲突的解决就成为了改变系统性能的 关键因素。其实还有很多种方法来解决冲突情况下的存储和查找问题,不一定非要线性向后排队,如果有好的哈希表冲突的解决方法也能很大程度上提高系统的效率。
二、哈希算法:
HASH主要用于信息安全领域中加密算法,它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做HASH值. 也可以说,hash就是找到一种数据内容和数据存放地址之间的映射关系。
数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?答案是肯定的,这就是我们要提起的哈希表,哈希表有多种不同的实现方法,我接下来解释的是最常用的一种方法——拉链法,我们可以理解为“链表的数组”,如图:
左边很明显是个数组,数组的每个成员包括一个指针,指向一个链表的头,当然这个链表可能为空,也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去,也是根据这些特征,找到正确的链表,再从链表中找出这个元素。
元素特征转变为数组下标的方法就是散列法。散列法当然不止一种,下面列出三种比较常用的:
1,除法散列法
最直观的一种,上图使用的就是这种散列法,公式:
index = value % 16
学过汇编的都知道,求模数其实是通过一个除法运算得到的,所以叫“除法散列法”。
2,平方散列法
求index是非常频繁的操作,而乘法的运算要比除法来得省时(对现在的CPU来说,估计我们感觉不出来),所以我们考虑把除法换成乘法和一个位移操作。公式:
index = (value * value) >> 28 ( 右移,除以2^28。记法:左移变大,是乘。右移变小,是除。 )
如果数值分配比较均匀的话这种方法能得到不错的结果,但我上面画的那个图的各个元素的值算出来的index都是0——非常失败。也许你还有个问题,value如果很大,value * value不会溢出吗?答案是会的,但我们这个乘法不关心溢出,因为我们根本不是为了获取相乘结果,而是为了获取index。
3,斐波那契(Fibonacci)散列法
平方散列法的缺点是显而易见的,所以我们能不能找出一个理想的乘数,而不是拿value本身当作乘数呢?答案是肯定的。
1,对于16位整数而言,这个乘数是40503
2,对于32位整数而言,这个乘数是2654435769
3,对于64位整数而言,这个乘数是11400714819323198485
这几个“理想乘数”是如何得出来的呢?这跟一个法则有关,叫黄金分割法则,而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列,即如此形式的序列:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377, 610, 987, 1597, 2584, 4181, 6765, 10946,…。另外,斐波那契数列的值和太阳系八大行星的轨道半径的比例出奇吻合。
对我们常见的32位整数而言,公式:
index = (value * 2654435769) >> 28
如果用这种斐波那契散列法的话,那上面的图就变成这样了:
注:用斐波那契散列法调整之后会比原来的取摸散列法好很多。
适用范围
快速查找,删除的基本数据结构,通常需要总数据量可以放入内存。
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!