复杂度分析:

  • 顺序查找: O(n)
  • 二分查找: O($\log_2n$)
  • 散列方法: O(C)

散列表与散列方法

将一个元素的关键码和存储位置之间建立对应的函数关系 Hash( ), 使得每个关键码与结构中的唯一的存储位置相对应:

Address=Hash( )

需要解决两个问题:

  • 找到一个合适的散列函数,避免或尽量减少冲突
  • 拟定解决冲突的方案

散列函数

取余法

散列表中地址数位m, p为不大于m但最接近m的质数.

取最大质数是为了减少冲突.

平方取中法

hash(key) = key^2的中间部分

长度取决于表的大小. 如表长 = $2^9$ =$(512)_{10}$ , 地址 $000\sim 777$,

key 平方 散列地址
$(2061)_8$ $4\underline{310}541$ $310$
$(1100)_8$ $1\underline{210}000$ 210

乘法杂凑函数

将结果化成八进制

处理冲突的闭散列(开地址)方法

产生冲突元素的关键码互为同义词.

闭散列又叫开地址法. 所有的桶都直接放在散列表数组中,并且把该数组组织成环形结构. 每个桶只有一个元素. 当发生冲突时, 把这个元素存放进表中”下一个”空桶中.寻找空桶的方法有很多.

线性探查法

若hash(key)=d并且这个桶已经被占用, 那么检查数组中连续的桶:d+1,d+2...m-1,0,...d-1.寻找下一个桶的公式:

每次发生冲突就探查下一个桶, 当循环 m-1 次后就会回到开始探查时的位置,说明待查关键码不在表内且表已满,不能再插入新的关键码.

$\rm ASL{succ}$ : 搜索成功的平均搜索次数, 搜索成功时, 把找到的每个元素的比较次数求和比上元素个数得到$\rm ASL{succ}$

$\rm ASL_{unsucc}$: 搜索失败时平均探查次数, 指在表中没有找到与待插入元素关键码相同的元素, 但找到空桶(即最终插入位置)时平均探查次数. 它是对于散列表中每个地址而言的, 其实就是从每个桶到下一个空桶需要探查的次数的平均值.

散列表存储的是元素集合, 不允许关键码相同的元素存在.

注意:闭散列情况下不能真正地将已有的元素删去, 因为中间的元素被删掉后会影响到之后元素的探查. 所以用一个状态数组来标识哈希表中每个元素的状态.

二次探查法

若用hash函数算得的桶 $H0$ 已经被占用,那么下 $i$ 个桶号 $H{i}$:

假设上一个桶号为 $H{i-1}$,用一个标识 odd 控制是加还是减, 可得 $H{i}$:

每次查找完后, 将odd 取反.

更浅显的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool QuadraticProbing(key)
{
  	int h0 = key%divisor;
    if(info[h0]==empty||info[h0]==deleted||table[h0]==key)
        return h0;
    int i = 0;
    int iSqure = 0;
    int odd = 1;
    while(1)
    {
        if(odd == 1) 
        {
            iSqure = iSqure+2*i+1;
        }
        h0 = (h0 + odd * iSqure)%divisor;
        if(info[h0]==empty||info[h0]==deleted||table[h0]==key)
     	   return h0;
        if(odd==1) odd=-1;
        else {i++;odd=1;}
    }
}

双散列

如果hash1(key)计算得到的桶号d已经被占用, 那么用第二个散列函数hash2(key)计算得到 c, 则依次探查 d+c,d+2c,d+3c….

再散列

当表项数>表的70%时, 可以再散列.

即, 建立一个两倍大的表, 新的散列函数取距离原规模两倍大小最近的素数.

处理冲突的开散列(链地址)方法

将同义词放入同一个桶. 各个桶中的元素分别用单链表连接起来, 各个链表的表头结点组成一个向量.