哈希表是什么

哈希表（hash table）又叫散列表。

和二叉树、链表这一类一样。它是一种数据结构，设计出来用于存放数据。

需要哪些基础知识

指针和数组

链表

模运算

哈希表的构建方法：

1.创建一个固定大小的数组

2.对需要进行存储的数据应用哈希函数，将数据转换为数组的索引位置

3.将数据存储在该索引位置处

如下：

关键字：x -> f(x)（哈希函数）->下标

哈希函数是根据关键字设计的，有很多种函数，主要的原理就是根据数组的大小求模运算。

(关键字) % (数组大小)

例如：20048157 % 17 (结果在0-16)

数组的大小一般设计为质数，因为需要均匀的散布。

遇到冲突怎么办

1、链表式解决(Separate Chaining)

写结构体的时候加入next指针(和链表一样)

数据 Next->数据 Next

遇到冲突的时候，把数据写到next的位置.

例如：

产生冲突时，往后面放指针（15->22->...）

2、开放地址(Open Addressing)

不用next指针，把其他下标的位置都对外开放。

开放地址的方法：

a. 线性探测法

如果遇到冲突，就往下一个地址寻找空位。

如果遇到冲突，新位置=原始位置+ i（i是冲突的次数）

例如：

（说明：28%13=2，由于下标2占位，往后寻找空位放入即最终找到下标4这个空位；4、12同理）

b. 平方探测法(二次方探测)

如果遇到冲突，就往(原始位置 + i2 )的位置

寻找空位(i 代表冲突的次数)

如果遇到冲突，新位置=原始位置+ i2

例如：

（说明：28%13=2，由于下标2被占用，下标换为2+12；28%13=2，下标换为2+22，...同理 ）

c.双哈希

要设置第二个哈希的函数，例如: hash2(key)=R-(key mod R)

R要取比数组尺寸小的质数。

例如R=7: hash2(关键字)= 7- (关键字% 7 )

也就是说，二次哈希的结果在1-7之间，不会等于0;

如果遇到冲突，新位置=原始位置+ i . hash 2(关键字)

例如：

如果遇到冲突，新位置=原始位置+i.hash 2（关键字）

哈希表满了怎办?

再次哈希(Rehashing)

当哈希表数据存储量超过70%，那么就自动新建一个新的哈希表

新表的尺寸是旧表的2倍以上，选择-一个质数

把之前的数据再次通过哈希计算搬到新表里

如果往旧表里再插入-一个数据，那么旧表的存储量将会超过70%

旧表:下标=关键字mod 7

新表:下标=关键字mod 17

旧表：

新表：

为什么设计哈希表

因为哈希表查找的性能快，它比搜索叉树的速度还快。

搜索二叉树的查找速度是0(log2 N),而哈希表发挥稳定的话

可以达到0(1)。

哈希表的缺点

表越满，性能越差