算法基础-散列表与开放寻址

散列表

散列表是一种动态的集合，它支持插入，检索，删除等字典操作。散列表是数组的扩展，一般的数组可以在 O(1) 的时间复杂度内进行随机读取，而散列表则使用一个特殊的函数来为各个元素分组在查找元素，只需要用特殊函数计算一次，就可以知道元素存放的位置

散列表的基本结构是一个关键字数组和链表，任意元素通过哈希函数计算出一个关键字，通过关键字可以直接定位到一个具体链表，然后往链表末尾添加该元素

struct HashTable{
    int length;
    Node* keyList;
};
 
struct Node{
    void* value;
    Node* next;
};

直接寻址表

当关键字全集 U 较小时，可以使用直接寻址表。例如需要存放的元素为 1 到 10 的数字，则可以创建一个长度为 10 的数组，每个数字对应唯一一个数组元素，例如数字 5 对应数组 a[4]，如果不存在数字 6，则 a[6] 的值为 NULL

当关键字全集 U 较大特别大时，内存中已经无法容下一个散列表，此时应该对关键字进行函数计算，例如除余，将所有关键字依照余数分类。此时会出现重复，对于重复项，我们只需要往列表的末尾延申就行

哈希函数

除法散列表

除法散列表的哈希函数为

将传入的关键字转化成数字以后，进行求余，这样哈希函数的值域就会被严格限制在 [0,m-1]

乘法散列表

乘法散列表的哈希函数为

将关键字乘上一个常数 A，然后取小数部分，乘上 m，最后向下取整

哈希冲突

如果存在不相同的元素 k1,k2，使得 h(k1) == h(k2)，则这两个元素会被映射到散列表的同一个地址，此时称为哈希冲突

开放寻址法

在开放寻址法中，如果需要往散列表中插入一个新的元素，则需要用一种方法按顺序探查散列表，直到找到一个空槽来存放新元素。当查找元素时，也应该按照相同的方法探查整个散列表，直到找到一个空槽，这时可以证明该元素不存在。因为如果它存在的话，那么它应该会在当前空槽的位置

散列函数的扩展

为了解决冲突问题，需要对散列函数进行扩展，将探查次数作为自变量加入到原散列函数中

即在原扩展函数的基础上，引入了探查次数，当第一次探查时，i 为0，就是原散列函数值，而从第二次开始，每次探查时 i 都会加一，直到找到一个空槽

集群

如果对于不同的 k1 和 k2，使得这两个元素出现冲突时，后续的探查次序完全一致，则说明槽位出现集群，即大量元素被按照某一规律储存，后序探查时又会按顺序一个一个遍历，这样就造成了效率低下

线性探查

线性探查在遇到冲突时，会按顺序探查下一个槽的位置

假设一个散列表共有10个槽位，第一次探查的槽位是T(2)，那么下一次就是T(3)

该方法会导致被占用的槽位出现集群，即一大串连续占用的槽位，因此平均查找时间也会大大增加

二次探查

二次探查使用二次函数来探查空的槽位

该方案的优点是不会出现连续集群，但是仍有一个缺点：如果 h(k1) == h(k2)，那么后序的探查顺序也会完全一致，这会造成轻度的集群，称为“二次集群”

双重散列

双重散列使用两个哈希函数来防止出现集群

这样的好处是难以出现不同的 k 值对应相同的槽位，也就避免了集群的出现