哈希表

1.哈希表的一些寻址方式

拉链法：

• 把相同哈希值的 不同的数 以链的形式挂在 数组内以该哈希值为头节点（即该哈希值的下标）的一条链上，数组大小应为一倍的数据范围，取余的数字应为数据范围之后的第一个质数且离二的整数倍尽可能远

开放寻址法

• 线性探测：看看当前坑位有没有人，有人循环加一，数组大小应为一倍的数据范围，取余数字规则同上
• 二级探测：(x + 1)^2, (x - 1)^2,(x + 2)^2, (x - 2)^2
• 随机数：生成一个 固定的 随机数序列
• 双散列表探查：一个函数生成哈希值，另一个函数根据不同的数值规定不同的寻址方式

2.几个名词解释

• 聚集：关键字不一样，探查的时候寻址序列有交集
• 二次聚集：不同哈希地址争夺同一个后继地址

3.取模和取余

• C++里面的 % 类似于数学意义上的取余，商向0方向靠近
• Python的 % 类似于数学意义上的取模，商向负无穷方向靠近