视频地址：https://www.bilibili.com/video/BV1MC4y1p7rP?from=search&seid=1477330995972769629

概念

hash表是一种数据存储的方式，简单讲就是数组中存放对应的指针。
image.png

哈希函数

哈希函数是用来计算数据对应下标的方法。
image.png

  • 举个栗子：哈希函数是f(x) = x % 13 那么针对 12 和 16 这两个关键字可以计算出，下标是 12 和 3。

hash冲突

当通过hash函数计算出来的下标有冲突时如何处理下标？

链表式解决法

遇到冲突时在冲突对应的地方用链表指向下一个关键词。

  • 例子
    • 关键字：15，16，24，22
    • 数组大小：7
    • 哈希函数：下标 = 关键字 % 7
  • 处理后如下：

image.png

线性探测法

遇到冲突时，往冲突的后一位下标探测，如果还冲突继续往再下一位探测，直到不冲突。

  • 例子
    • 关键字：15，2，28，4, 38, 12
    • 数组大小：13
    • 哈希函数：下标 = 关键字 % 13
  • 处理后如下：

image.png

平方探测法

遇到冲突时，往冲突次数i的平方位下标探测，如果还冲突继续往再下一位探测，直到不冲突。

  • 例子
    • 关键字：15，2，28，4，19， 10
    • 数组大小：13
    • 哈希函数：下标 = 关键字 % 13
  • 处理后如下：

image.png

双哈希法

遇到冲突时，遇到冲突时用另外一个hash函数来计算

  • 例子
    • 关键字：15，2，18，28
    • 数组大小：13
    • 哈希函数1：下标 = 关键字 % 13
    • 哈希函数2：下标 = 7 - （关键字 % 7）
    • 遇到冲突：下标 = 原始位置 + i * 哈希函数2（关键字）
  • 处理后如下：

image.png

hash表满了怎么办

image.png

如下例子:

image.png

为什么设计hash表

  • 因为查找速度快，直到下标就可以得到值。复杂度o(1);

hash表的缺点

  • 表越满性能越差，原因是表越满冲突的概率就越大，需要处理冲突的次数就越多