散列表

散列表

Hash Table,也叫哈希表。支持按照下标随机访问数据的特性，是数组的一种扩展，由数组演化而来。

散列冲突的原因：散列地址不同的结点争夺同一个后继散列地址的现象称为聚集或堆积(Clustering)。

1
2
1再好的散列函数也无法避免散列冲突
2最常见的哈希算法是取模法

散列函数设计的基本要求

1
2
3
1散列函数计算得到的散列值是一个非负整数；
2如果 key1 = key2，那 hash(key1) == hash(key2)；
3如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。

从解决冲突的角度，主要有开放寻址法和拉链法。

开放寻址-线性探测：

1
2
3
1插入：通过散列函数找到理想位置->发现被占->继续遍历直到寻到一个空位 
2查找：查看散列位置->不匹配->继续找till第一个空位 
3删除：不清空存储位置，而是标记deleted，以避免查找功能失效

存在问题：当散列表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，最坏情况下的时间复杂度为 O(n)

开放寻址-二次探测：

1
线性探测每次探测的步长是 1,即hash(key)+0，hash(key)+1，hash(key)+2……，而二次探测探测的步长就变成了原来的“二次方”,即下标序列就是 hash(key)+0，hash(key)+1<sup>2</sup>，hash(key)+2<sup>2</sup>...

开放寻址-双重散列：

1
不是使用一个散列函数，而是使用一组散列函数 hash1(key)，hash2(key)，hash3(key)……hash1(key)计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置

装载因子

1
2
3
散列表的装载因子=填入表中的元素个数/散列表的长度

装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

链表法

每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中

hash冲突时，如何通过key，查询到对应的value?(即当key1 != key2 ，f(key1)==f(key2),怎么找到key1、key2对应的value呢？)

1
2
3
4
5
6
从解决冲突的角度，主要有开放定址法和拉链法。
开放地址法：又分线性探查法和平方探查法。

拉链法-查询：
通过散列函数f(key)，返回一个地址（一个链表的指针，即链表的位置），再通过遍历链表匹配key,找到对应的value
参考链接：https://blog.csdn.net/freedom_like_wind/article/details/71078188#commentBox

时间复杂度：与散列函数、装载因子、散列冲突等有关，不能笼统的说成O(1),最坏的情况是O(n)

以上学于极客时间，做的笔记