数据结构——散列

2024-04-11 17:29:07

散列 (哈希)

复杂度分析:

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

散列表与散列方法

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

Address=Hash( )

需要解决两个问题:

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

散列函数

取余法

\[\rm hash(key) = key\%p, p\leq m \]

散列表中地址数位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

乘法杂凑函数

\[\rm hash(key) = M\times((\phi \times key)\% 1)_{10} \]

将结果化成八进制

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

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

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

线性探查法

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

\[H_{i+1} = (H_i+1)\%m, i=1,2,...,m-1 \]

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

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

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

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

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

二次探查法

若用hash函数算得的桶 \(H_0\) 已经被占用,那么下 \(i\) 个桶号 \(H_{i}\):

\[\begin{aligned} H_{i}=(H_0+i^2)\%m,i = 1,3,5...\\ H_{i}=(H_0-i^2)\%m,i = 2,4,6...\\ \end{aligned} \]

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

\[\begin{aligned} H_{i} = (H_{i_1} + 2*i-1)\% m, odd=0\\ H_{i} = (H_{i_1} - 2*i+1)\% m, odd=1\\ \end{aligned} \]

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

更浅显的

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%时, 可以再散列.

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

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

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

码农公寓