算法基础-散列表与开放寻址
算法基础-散列表与开放寻址
散列表
散列表是一种动态的集合，它支持插入，检索，删除等字典操作。散列表是数组的扩展，一般的数组可以在 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 值对应相同的槽位，也就避免了集群的出现