动画: 什么是散列表? (Hash Table 哈希表)
本文来自算法爱好者! (部分详细介绍)
散列表
散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。
散列函数
散列函数,顾名思义,它是一个函数。如果把它定义成 hash(key),其中 key 表示元素的键值,则 hash(key)的值表示经过散列函数计算得到的散列值。
对于一个大小为 M 的散列表,散列函数能够把任意键转换为 [0, M-1] 内的正整数,该正整数即为 hash 值。
散列表存在冲突,也就是两个不同的键可能有相同的 hash 值。
散列函数应该满足以下三个条件:
- 一致性:相等的键应当有相等的 hash 值,两个键相等表示调用 equals() 返回的值相等。
- 高效性:计算应当简便,有必要的话可以把 hash 值缓存起来,在调用 hash 函数时直接返回。
- 均匀性:所有键的 hash 值应当均匀地分布到 [0, M-1] 之间,如果不能满足这个条件,有可能产生很多冲突,从而导致散列表的性能下降。
除留余数法可以将整数散列到 [0, M-1] 之间,例如一个正整数 k,计算 k%M 既可得到一个 [0, M-1] 之间的 hash 值。注意 M 必须是一个素数,否则无法利用键包含的所有信息。例如 M 为 10k,那么只能利用键的后 k 位。
对于其它数,可以将其转换成整数的形式,然后利用除留余数法。例如对于浮点数,可以将其的二进制形式转换成整数。
对于多部分组合的类型,每个部分都需要计算 hash 值,这些 hash 值都具有同等重要的地位。为了达到这个目的,可以将该类型看成 R 进制的整数,每个部分都具有不同的权值。
例如,字符串的散列函数实现如下:
int hash = 0;
for (int i = 0; i < s.length(); i++)
hash = (R * hash + s.charAt(i)) % M;
再比如,拥有多个成员的自定义类的哈希函数如下:
int hash = (((day * R + month) % M) * R + year) % M;
R 通常取 31
散列冲突
理想中的一个散列函数,希望达到
如果 key1 ≠ key2,那 hash(key1) ≠ hash(key2)
这种效果,然而在真实的情况下,要想找到一个不同的 key 对应的散列值都不一样的散列函数,几乎是不可能的,即使是 MD5或者 由美国国家安全局设计的 SHA-1算法也无法实现。
事实上,再好的散列函数都无法避免散列冲突。
为什么呢?
这涉及到数学中比较好理解的一个原理:抽屉原理。
抽屉原理:桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面至少放两个苹果。这一现象就是我们所说的“抽屉原理”。
抽屉原理
对于散列表而言,无论设置的存储区域(n)有多大,当需要存储的数据大于 n 时,那么必然会存在哈希值相同的情况。这就是所谓的散列冲突。
散列冲突
那应该如何解决散列冲突问题呢?
常用的散列冲突解决方法有两类,开放寻址法(open addressing)和链表法(chaining)。
#
开放寻址法
定义:将散列函数扩展定义成探查序列,即每个关键字有一个探查序列h(k,0)、h(k,1)、…、h(k,m-1),这个探查序列一定是0….m-1的一个排列(一定要包含散列表全部的下标,不然可能会发生虽然散列表没满,但是元素不能插入的情况),如果给定一个关键字k,首先会看h(k,0)是否为空,如果为空,则插入;如果不为空,则看h(k,1)是否为空,以此类推。
开放寻址法是一种解决碰撞的方法,对于开放寻址冲突解决方法,比较经典的有线性探测方法(Linear Probing)、二次探测(Quadratic probing)和 双重散列(Double hashing)等方法。
线性探测方法
开放寻址法之线性探测方法
当我们往散列表中插入数据时,如果某个数据经过散列函数散列之后,存储位置已经被占用了,我们就从当前位置开始,依次往后查找,看是否有空闲位置,直到找到为止。
以上图为例,散列表的大小为 8 ,黄色区域表示空闲位置,橙色区域表示已经存储了数据。目前散列表中已经存储了 4 个元素。此时元素 7777777 经过 Hash 算法之后,被散列到位置下标为 7 的位置,但是这个位置已经有数据了,所以就产生了冲突。
于是按顺序地往后一个一个找,看有没有空闲的位置,此时,运气很好正巧在下一个位置就有空闲位置,将其插入,完成了数据存储。
线性探测法一个很大的弊端就是当散列表中插入的数据越来越多时,散列冲突发生的可能性就会越来越大,空闲位置会越来越少,线性探测的时间就会越来越久。极端情况下,需要从头到尾探测整个散列表,所以最坏情况下的时间复杂度为 O(n)。
开放寻址法之线性探测方法的弊端
二次探测方法
二次探测是二次方探测法的简称。顾名思义,使用二次探测进行探测的步长变成了原来的“二次方”,也就是说,它探测的下标序列为 hash(key)+0,hash(key)+1^2或[hash(key)-1^2],hash(key)+2^2或[hash(key)-2^2]。
二次探测方法
以上图为例,散列表的大小为 8 ,黄色区域表示空闲位置,橙色区域表示已经存储了数据。目前散列表中已经存储了 7 个元素。此时元素 7777777 经过 Hash 算法之后,被散列到位置下标为 7 的位置,但是这个位置已经有数据了,所以就产生了冲突。
按照二次探测方法的操作,有冲突就先 + 1^2,8 这个位置有值,冲突;变为 - 1^2,6 这个位置有值,还是有冲突;于是 - 2^2, 3 这个位置是空闲的,插入。
双重散列方法
所谓双重散列,意思就是不仅要使用一个散列函数,而是使用一组散列函数 hash1(key),hash2(key),hash3(key)。。。。。。先用第一个散列函数,如果计算得到的存储位置已经被占用,再用第二个散列函数,依次类推,直到找到空闲的存储位置。
双重散列方法
以上图为例,散列表的大小为 8 ,黄色区域表示空闲位置,橙色区域表示已经存储了数据。目前散列表中已经存储了 7 个元素。此时元素 7777777 经过 Hash 算法之后,被散列到位置下标为 7 的位置,但是这个位置已经有数据了,所以就产生了冲突。
此时,再将数据进行一次哈希算法处理,经过另外的 Hash 算法之后,被散列到位置下标为 3 的位置,完成操作。
事实上,不管采用哪种探测方法,只要当散列表中空闲位置不多的时候,散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率,一般情况下,需要尽可能保证散列表中有一定比例的空闲槽位。
一般使用加载因子(load factor)来表示空位的多少。
加载因子是表示 Hsah 表中元素的填满的程度,若加载因子越大,则填满的元素越多,这样的好处是:空间利用率高了,但冲突的机会加大了。反之,加载因子越小,填满的元素越少,好处是冲突的机会减小了,但空间浪费多了。
#
链表法
链表法使用链表来存储 hash 值相同的键,从而解决冲突。
查找需要分两步,首先查找 Key 所在的链表,然后在链表中顺序查找。
对于 N 个键,M 条链表 (N>M),如果哈希函数能够满足均匀性的条件,每条链表的大小趋向于 N/M,因此未命中的查找和插入操作所需要的比较次数为 ~N/M。
链表法是一种更加常用的散列冲突解决办法,相比开放寻址法,它要简单很多。如下动图所示,在散列表中,每个位置对应一条链表,所有散列值相同的元素都放到相同位置对应的链表中。
链表法
还没有评论,来说两句吧...