哈希表

哈希表定义

l  哈希表（Hash table，也叫散列表），是根据关键码值 (Key value)而直接进行访问的数据结构。 也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。 这个映射函数叫做散列函数，存放记录的数组叫做散列表。

散列函数

l  直接定址法: H(key)=a*key+b，可以保证不冲突，但散列表表长依赖于关键字值，具有随意性。

l  除素取余：H(key) = key mod p，其中p往往取素数

l  平方取中

l  数字分析

l  。。。 。。。

冲突处理

l  开放定址法——允许关键字存入非匹配位置

Addr = Hash(Key)，若Addr处已有元素占位，那么通过一个增量序列d1, d2, … …

向前探测，即Addr = Addr + di (i=1, 2, … …)，直到找到一个空位。在查找时，先计算Hash(Key)得到Addr，若散列表Addr处为空，则查找失败，否则作第一次比较，若相等，查找成功，否则依据di向前探测，直到查找到该值（查找成功）或查到一个空缺（查找失败）由此可见，在散列表中不可以随便删除一个元素，因为这样可能导致断链，可以采用标记法，这时应不定期的进行物理调整。

       Hi = (Hash(Key) + di)%m (m为表长)

n  线性探测法：{ di } = { 0, 1, 2, 3, … … }，也即每次向前看一个位置，这种方法可能造成聚集现象，增大平均查找长度

n  平方探测法（二次探测法）：{ di } = { 0, 1, -1, 4, -4, 9, -9, … … , k^2, -k^2}其中k<=m/2，m是可以表示为 m = 4*k + 3的素数，优点是避免了堆积问题，缺点是无法探测到所有单元

n  再散列法：使用Hash2(Key)作为di的值，di = i*Hash2(key)

l  链接法

n  将冲突的元素组成一个链表

例题

1、 设记录的关键字集合K = { 24，15，39，26，18，31，05，22}，哈希表表长m=16，哈希函数H(key) = Key % 13，冲突处理策略为“二次探测法”。请依次取K中各元素构造哈希表并求等概率条件下查找成功的平均查找长度。

解：

24%13 = 11，直接插入       15%11=4，直接插入         

39%13=0，直接插入          26%13=0，冲突，di=1, (26+1)%16=1

18%13=6，直接插入           31%13=5，直接插入

05%13=5，冲突，d1=1, (05+1)=6，冲突，di=-1，(05-1)=4，冲突，di=4，5+4 = 9, 不冲突，

22%13=8, 不冲突，直接插入

根据以上插入过程，则平均查找长度

为：(1+1+1+2+1+1+4+1+1)/8 = 1.5