2.1哈希表高清版本.pdf

哈希表

主讲人：邓哲也

哈希表的引入

如果要储存和使用线性表（1，75，324，43，1353，90，46）

一般情况下我们会使用一个数组A[1..7]来顺序存储这些数。

但是这样的存储结构会给查询算法带来O(n)的时间开销。

对A排序，使用二分查询法，时间复杂度变为O(logn)

也可以用空间换时间的做法，用数组A[1..1353]来表示每

个数是否出现，查找的时间复杂度变为O(1)，但是空间上的

开销变得巨大。

哈希表的引入

优化上一种做法，建立一个哈希函数h(key)=key%23.

(1,75,324,43,1353,90)-(1,6,2,20,19,21,0)

我们只要用一个A[0..22]数组就可以快速的查询每个数是

否出现。

这种线性表的结构就称为哈希表（HashTable）。

哈希表的基本原理

可以看出，哈希表的基本原理是用一个下标范围比较大的数

组A来存储元素。

设计一个函数h，对于要存储的线性表的每个元素node，

取一个关键字key，算出函数值h(key)然后把这个值作为

下标，用A[h(key)]来存储node。

最常见的h就是模函数，也就是选定一个m，令h(key)=

key%m.

哈希表的冲突

但是有一个问题，可能存在两个key:k1,k2使得

h(k1)=h(k2)，这时也称产生了“冲突”。

解决冲突有很多种办法：

可以用另一个函数I去计算I(k1),I(k2)，找到新的

位置。

可以让A的每个元素都存一个链表，对于

h(k1)=h(k2)，我们可以让这两个node都接在A[h(k1)]

的链表上。

……

哈希表的冲突

假设我们使用第二种方法解决冲突。

对于插入元素(node,key)：

•计算h(key)，把node插入A[h(key)]链表。

对于查询元素(node,key)：

•计算h(key)，如果A[h(key)]为空，说明node不存在。

否则遍历A[h(key)]链表，寻找node。

哈希表的代码实现

structnode{

intnext,info;

}hashNode[N];

inttot;//哈希表节点计数

inth[M];//初始化为-1

哈希表的代码实现

voidinsert(intkey,intinfo){

intu=key%M;

hashNode[tot]=(node){h[u],info};

h[u]=tot++;

}

哈希表的代码实现

intfind(intkey,intinfo){

intu=key%M;

for(inti=h[u];i!=-1;i=hashNode[i].next){

if(hashNode[i].info==info)

return1;

}

return0;

}

边学边练

已知X[1..4]是[-T,T]中的整数，求出满足方程

AX[1]+BX[2]+CX[3]+DX[4]=P

的解有多少组？

94

|P|≤10，|A|,|B|,|C|,|D|≤10，T≤500

边学边练

4

最直观的方法枚举X[1..4],时间复杂度O(n)

适当优化，枚举了X[1..3]之后，实际上X[4]已经确