八、哈希表

常用术语

（1）同义词（Synonym）：哈希函数值相同的关键字称为同义词。

（2）冲突（Collision）：对不同的关键字可能得到同一哈希地址，即 $ke{y_1} \ne ke{y_2}$，而 $H(ke{y_1}) = H(ke{y_2})$。

（3）哈希函数和哈希地址（Hash function）：在记录的存储位置 $p$ 和其关键字 $key$ 之间建立一个确定的对应关系 $H$，使 $p=H(key)$，称这个对应关系 $H$ 为哈希函数，$p$ 为哈希地址。

（4）哈希表：一个有限连续的地址空间，用以存储按哈希函数计算得到相应散列地址的数据记录。通常哈希表的存储空间是一个一维数组，哈希地址是数组的下标。

哈希函数的构造方法

一、直接定址法

最简单的直接定址法（Direct addressing）直接用关键字 $key$ 作为哈希地址，即 $H(key)=key$。

虽然这种哈希函数简单，且不会产生冲突，但在实际应用中，关键字很少是连续的，采用这种特殊哈希函数会造成哈希表空间浪费。一般情况下，直接定址法可通过对关键字缩放和平移，获得合适的地址区间，即 $H(key) = a \times key + b$。其中，$a$ 为缩放系数，$b$ 为平移系数。

int hash_d(int key)
{
    return a*key+b;
}

二、除留余数法

假设哈希表表长为 $m$ ，除留余数法（Divided and get the remainder）选择一个不大于 $m$ 的数 $p$ 为模 ，用 $p$ 去除关键字，除后所得余数为哈希地址，即 $H(key)=key%p$。

这个方法的关键是选取适当的 $p$ ，一般情况下，可以选 $p$ 为小于表长的最大质数（素数）。例如，表长 $m=100$ ，可取 $p=97$ 。

int hash_m(int key)
{
    return key%p;
}

处理冲突的方法

一、链地址法

链地址法（Separate chaining）的基本思想是：把具有相同哈希地址的记录放在同一个单链表中，称为同义词链表。有 $m$ 个哈希地址就有 $m$ 个单链表，同时用数组 $HT[0...m - 1]$ 存放各个链表的头指针，凡是哈希地址为的记录都以结点方式插入到以 $HT[i]$ 为头结点的单链表中。