散列表

基本概念

散列函数（哈希函数）：集合元素的关键字（key）与其存储位置之间的关系函数。散列函数计算出的值也称为散列值

Loc（key）：白哦是关键字值为 key 的集合元素的存储地址

散列表（哈希表）：用散列函数建立起来的表，用于存储集合元素

冲突：key1 != key2，但 h(key1) = h(key2) 的现象

同义词：对给定 h，具有相同散列值的不同关键字

避免冲突

散列函数是一个压缩映像，冲突不可避免

散列函数应具有的性质

确定性：同一值被映射的到同一地址
快速：最好是 O(1)
满射：尽可能充分覆盖整个散列表存储空间
均分布：避免扎堆

常见散列函数

取余

$$
h(key)=key%M（M为散列表长）
$$

取模不超过 M 的素数 P 更好（素数同余比非素数同余概率要小）

不足：

• 存在不动点 h(0)=0，与均分布相悖
• 相邻的关键字散列到相邻地址上

改进：MAD

$$
h(key)=(key\times a+b)%P
$$

其中 P 为不超过 M 的最大素数，a>0，b>0，a%P != 0

平方取中法

$$
h(key)=(key)^2 \space 的中间若干位 \space k
$$

其中位数 k 应满足：10^k-1 < n <= 10^k，n 为集合中元素个数（平方后的结果很长，只取中间的一部分）

折叠法

• 把关键字从左到右，分成位数相等的几部分
  • 每部分位数与散列表地址位数相同，最后一部分的位数可以短些
• 把这些数据叠加

叠加时还可以通过正向、逆向转换增加复杂度

数字分析法

观察关键字的编码组合规律，取分布均匀的若干位

冲突处理技术

开散列法与闭散列法（开放地址法）

相同点

• 都具有一个散列表和至少一个散列函数
• 对散列函数的要求一致：均分布、计算快速……

不同点

• 开：将集合元素存储在散列表主表之外
• 闭：主表之内

开放地址法

元素在散列表中的 位置/下标 不完全取决于散列值，而是取决于 散列值、冲突处理策略、散列表中已存储的元素

通过解决冲突的策略来确定探查路径，依次被探索的位置称为探查序列

拉链法（开散列法）

集合元素的查找

• 计算散列值
• 到散列表位置处取出单链表头指针
• 遍历链表进行查找：比较 key

如果单链表的表长很短，就没有必要维护有序性，以节省资源

时间复杂度

查找、插入和删除：O(n/M)，其中 n/M（已存储元素个数 / 散列表长），也称散列表的装填因子

装填因子暗示装满程度（操作中需要比较的次数）

可通过设置其上限，保证快速搜索，超过上限则需进行散列表扩充

在拉链法中，装填因子可以大于1

优缺点

优点：

• 无聚集现象（平均查找长度较短）
• 空间动态申请（适用造表前无法确定表长的情况）

缺点：

• 指针需要额外空间，数据元素占存储空间较小时，空间使用率低

线性探查法

从基位置开始依次向下探查

搜索

从基位置开始线性探查

• 搜索成功
  • 找到
• 搜索失败
  • 遇到空位置
  • 表满

删除

• 不能简单清除元素，否则会影响后续搜索操作
• 删除元素后，空出的位置能够重新使用

解决办法

• 为每个位置增加标志域 empty，表示该位置是否使用过
• 删除元素时不改变标志位，仍为 false，元素值改为 NeverUsed
• 为 true 则代表从未被使用过

简单实现：

#include <iostream>
#include <iomanip>

typedef class Node
{
public:
    int data;
    bool is_used;
    Node()
    {
        data = 0;
        is_used = false;
    }
} Node;

int const total_sum = 100;
Node num_sum[total_sum];

int main()
{
    int num_insert[35] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,77,15,16,17,18,19,20,21,22,96,24,25,26,27,28,29,55,31,32,33,34};
    int pos = 0;
    for (int i = 0; i < 35; i++)
    {
        pos = (num_insert[i] * 7 + 12) % total_sum;
        num_sum[pos].data = num_insert[i];
        num_sum[pos].is_used = true;
    }

    int m = 0;
    int t = total_sum / 25;
    for (int i = 0; i < t; i++)
    {
        for (int j = m; j < m + 25; j++) // 使用不同的变量名 j
        {
            std::cout << std::setw(3) << j << " ";
        }
        std::cout << std::endl;
        for (int j = m; j < m + 25; j++) // 使用不同的变量名 j
        {
            std::cout << std::setw(3) << num_sum[j].data << " "; // 去掉前面的空格，并加上一个空格以保持格式一致
        }
        std::cout << std::endl;
        for (int j = m; j < m + 25; j++) // 使用不同的变量名 j
        {
            std::cout << std::setw(3) << num_sum[j].is_used << " "; // 去掉前面的空格，并加上一个空格以保持格式一致
        }
        std::cout << std::endl
                  << std::endl;
        m += 25;
    }
}

插入

• 搜索，出现重复元素则查找失败
• 表满，插入失败
• 未搜索到，且探查到 NeverUsed 位置，插入，empty 改为 F

二次探查法

从基地址开始第一次探查，此后摇摆探查（先加后减）

$$
h_1(key)=(h(key)+i^2)%M
$$
$$
h_1(key)=(h(key)-i^2)%M
$$

负数取模计算问题：不断加上模值直到第一次变为非负数

优点

可以改善线性聚集现象

缺点

同义词之间有相同的探查序列，出现二次聚集现象

双散列法

$$
(h_1(key)+i\times(h_2(key))%M)
$$

h₂ 的作用：

• 对 h₁ 散列值产生固定增量，实现跳跃式探查
• 改善二次聚集（两个散列函数都为同义词的情况很少）

h₂(key) 应为小于 M 且与 M 互质的整数。若 M 为素数，可取 h₂(key)=key % (M-2)+1

关键代码

// 第二个哈希函数，用于双重哈希法中的步长计算
int hash2(int key)
{
    return 17 - (key % 17); // 17是一个质数且小于total_sum
}

// 遍历待插入的数据数组
for (int i = 0; i < 35; i++)
{
    int key = num_insert[i];               // 获取当前数据
    int hash = (key * 7 + 12) % total_sum; // 计算初始哈希值
    int pos = hash;                        // 当前位置设为初始哈希值
    int step = 0;                          // 步数初始化为0

    // 使用双重哈希法处理冲突
    while (num_sum[pos].is_used)
    {
        step++; // 步数加1
        // 计算新的位置，使用双重哈希法
        pos = (hash + step * hash2(key)) % total_sum;
    }

    num_sum[pos].data = key;     // 将数据插入到计算出的位置
    num_sum[pos].is_used = true; // 标记该位置已被使用
}