引入
对于学生信息有如下结构
struct student {
id int,
name string,
}
如果要在一堆学生数组中查找某一个学生的信息，那么可以用遍历的方法，例如我想通过学号查找学生信息那么可以这么写
{id:2,name:"李四"}
{id:1,name:"张三"}
{id:3,name:"王五"}
foreach s in students {
if s.id == 3 {
print(s.name)
}
}
但是这样查找效率太低了，因此我们想到为什么不直接将学号当作下标访问，例如我想找学号为3的，直接使用arr[3]
在存储阶段我们将id作为数组下标，例如我想存放1-3的学号学生信息，我就创建空间为4的数组，然后将学号1对应的信息放入arr[1]中，学号2放入arr[2]中，以此类推。这样查找的时候就能直接根据学号定位下标。恭喜你发明了Hash表！
我们常用的字典就是以Hash实现的，通过set(1,"张三")键值对来保存数据
Hash表可以看作一个数组，数组内每一个空间存放键值对信息，并且数组的下标与KEY对应，这样通过KEY就可以直接定位到数据，平均时间复杂度O(1)，最坏为O(n)
Hash函数/散列函数
{id:1001,name:"张三"}
{id:1002,name:"李四"}
{id:1003,name:"王五"}
已知上面的信息，id是从1001开始的，我们不可能创建一个空间为1004的数组，因为我们只需要存放三个数据，因此需要用到散列函数。
散列函数维护了键值对之间的映射关系
最常用的映射关系如下
- 直接定址（线性映射）：
- 除留余数：H(Key) = key % p
直接定址
满足H(Key) = Key或H(Key) = k * Key + b
取偏移量b = 1000，则H(Key) = Key – 1000，但是这种方法只适用于Key连续的情况，如果Key稀疏且跨度大依旧会带来空间上的浪费
优点：映射简单，不会产生碰撞
缺点：要求Key连续分布否则会带来大量空间浪费
除留余数
H(Key) = key % p，（p一般取小于等于表长的最大质数）
优点：能够将Key放到连续空间
缺点：会产生Key碰撞，降低散列表性能
碰撞：两个Key通过散列函数计算后映射到数组同一个下标
散列表性能决定因素：
- 散列函数（选用哪种映射策略）
- 装填因子（表中元素数量 / 表长）
- 碰撞处理方法
装填因子：装填因子 = 表中元素数 / 表长。开放定址法一般要求装填因子 < 1（常见阈值 0.7~0.75），超过时需要扩容（再散列）
碰撞处理方法
开放定址法
线性探测法
表尾的下一个位置是表首，碰撞后依次探测下一个位置，直到遇到空闲位置
对于线性探测法删除Key不能直接将下标所在元素删除，因为如果查找的元素在删除元素的后面，那么在线性探测时探测到空会误认为后面没有查找的元素了，导致查找失败。所以删除元素需要打上删除标记。
- 在查找时，遇到空会放弃查找，而删除标记不会影响查找
- 做插入时，空位置和删除标记位置可以插入
弊端：堆积问题
平方探测法
冲突时按照+1²，-1²，+2²，-2²，+3²，-3²，…的顺序进行探测（表尾之后是表首）
表长=某个4k+3的质数(k为正整数) 时一定能探测到所有位置
- 在查找时，遇到空会放弃查找，而删除标记不会影响查找
- 做插入时，空位置和删除标记位置可以插入
拉链法
冲突时通过挂载串联单链表实现查找
- 插入时，头插法和尾插法都可以
- 删除时，直接让上一个节点的尾指针指向下一个节点即可
注意
编程语言 API 里说的 hash()，只是将Key（如字符串）进行转化为一个 int，不含映射。
如Java的String.hashCode()只把字符串变成整数。真正映射到桶，是HashMap容器内部做的事。
评论（0）
暂无评论