哈希表(Hash Table)

哈希表，又称散列表，一种数据结构设计出来用于存放数据。

哈希表是一个数组，数组里放的是一个指针，指针指向的是存放的数据。

之所以叫哈希表，是因为有一个哈希函数用于计算数组的下标。

通过哈希函数将数据的关键字计算为数组的下标，再将该数据的指针存放在该数组里。

例，如下图：

图片.png

不同的数据关键字哈希函数计算出来的下标重复怎么办？？

1. 链表式解决
   写入结构体时加入next指针，遇到冲突时加入到同样下标的next位置

图片.png

2. 开放地址

2.1. 线性探测法

如果遇到冲突，就往下一个位置寻找空位
新位置 = 原始位置 + i （i 是查找的次数）

2.2. 平方探测法（二次方探测法）

如果遇到冲突，就往（原始位置+i^2）寻找空位
新位置 = 原始位置 + i ^2（i 是查找的次数）

2.3. 双哈希

需要设置第二个哈希函数，在遇到冲突时使用
新位置 = 原始位置 + i *hash2(关键字)

哈希表满了怎么办？

单哈希表数据超过70%就建一个旧表尺寸2倍以上的新哈希表，把之前的数据再次通过哈希函数计算记录到新表里

课代表笔记，知识来源：https://www.bilibili.com/video/BV1MC4y1p7rP