数据结构与算法-散列表(哈希表)

1. 哈希算法

如何选择哈希算法：

计算公式花费的时间
关键字的长度
散列表大小
关键字分布情况
记录查找概率

1.1 直接定址法

$f(key) = a * key + b$

key是线性的，如年龄、年份等。

1.2 数字分析法

找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

比如一个地区手机号，前面很多位都相同，不同可能是最后4位数，将这部分作为散列算法的依据。

1.3 平方取中法

取关键字平方后的中间几位作为散列地址。

先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀。

1.4 折叠法

将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。

1.5 取余法

取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。
$f(key) = key\ \ mod\ \ p\ (p<=m)$

1.6 随机数法

选择一随机函数，取关键字的随机值作为散列地址，通常用于关键字长度不同的场合。

2. 哈希冲突解决

2.1 开放定址法

就是一旦发⽣了冲突，就去寻找下⼀个空的散列地址。

只有散列表⾜够大，空的散列地址总能找到，并将记录存入。
$f_i (key)=(f(key)+d_i )\ \ mod\ \ m,\ \ (di =1,2,3,......,m-1)$

2.2 再散列函数法

对于散列表来说，我们事先准备多个散列函数：
$f_i(key) = RH_i(key), \ (i=1,2,...,k)$
$RH_i$ 指的是不同的散列函数。

2.3 链地址法

将所有的关键字为同义词的记录存储在一个单链表中。我们称为这种同义词子表。

在散列表中只存储所有同义词⼦表的头指针(头地址)。

简单说，冲突的用一个链表存起来。

2.4 公共溢出法

另开一个公共的表存储冲突的数据。基本表没有查找到，就在溢出表中查找。空间浪费严重。

3. 哈希表的实现

typedef int Status;

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 //存储空间初始分配量
#define SUCCESS 1
#define UNSUCCESS 0

//定义散列表长为数组的长度
#define HASHSIZE 12
#define NULLKEY -32768

typedef struct {
    int *elem;  // 存储哈希key的数组
    int size;   // 哈希表数组大小
    int count;  // 当前数据元素个数
} HashTable;

// 1.初始化散列表
Status InitHashTable(HashTable *H) {
    H->size = HASHSIZE;
    H->elem = (int *)malloc(sizeof(int) * H->size);
    H->count = 0;
    // 数组初始化
    for (int i = 0; i < H->size; i++)
        H->elem[i] = NULLKEY;
    return OK;
}

//2. 散列函数
int Hash(HashTable H, int key) {
    return key % H.size; //除留余数法
}

//3. 插入关键字进散列表
Status InsertHash(HashTable *H, int key) {
    if (H->count >= H->size) { // 满了，可以考虑扩容
        return UNSUCCESS;
    }
    int addr = Hash(*H, key); // 求散列地址
    while (H->elem[addr] != NULLKEY) { // 如果不为空，则冲突
        addr = (addr + 1) % H->size; // 开放定址法的线性探测
    }
    H->elem[addr] = key; // 直到有空位后插入关键字
    H->count++;
    return SUCCESS;
}

//4. 散列表查找关键字
Status SearchHash(HashTable H, int key, int *addr) {
    *addr = Hash(H, key); // 求散列地址
    while (H.elem[*addr] != key) { // 如果不为空，则冲突
        *addr = (*addr+1) % H.size; // 开放定址法的线性探测
        if (H.elem[*addr] == NULLKEY // 开放定地后为空
            || *addr == Hash(H, key)) // 循环有回到了原点
            return UNSUCCESS; // 关键字不存在
    }
    return SUCCESS;
}