散列表

散列表的优缺点

• 优点是查找效率高
• 缺点是空间浪费大

散列表如何解决冲突问题

• 开放地址法：有冲突就找空位
  • 线性探测法：有冲突就顺序查找下一个空位存入。
  • 二次探测法：有冲突就按照增量序列移动位置继续探测。
  • 伪随机探测法：有冲突就随机位移几位看看是否有空位
• 链地址法：相同哈希值的记录连成一个链表

散列表的查找

依据哈希值取数，如果查到的不是目标数据，就依据事先定好的冲突方法，继续查找。

如果目标地址为空，则停止查找，说明没有相关记录。