网站建设官方网站推广方式
回顾/本期梗概
上期我们学习了哈希——字符串哈希（空降链接），本期我们将学习哈希中的哈希表。
1、哈希表原理
（1）使用数组下标直接标记元素
哈希表（也叫数列表）：是一种高效的、通过把关键词码值映射到表中的一个位置来访问记录的数据结构。
类似字符串，查找的时间复杂度是常熟时间，缺点是需要消耗更多的内存。
现在要存储和使用下面的线性表：.
为了用的时间实现查找，可以开一个一维数组
，使得
，虽显然造成了空间上的很大浪费，尤其是数据范围很大时。
（2）除余法构造哈希值
为了使空间开销减少，我们可以对第二种方法加以优化，实际一个哈希函数，然后令
，这样一来定义一个一维数组
就已足够，这种方法就是哈希表。
但这样会造成哈希冲突，比如和
的值都是2.
这里与字符串 Hash 有所不同，可能不论我们怎样选用哈希函数，还是很难避免产生冲突。
因此我们考虑对每一个哈希值记一个链表（其实也就相当于邻接表），把所有等于同一个哈希值的数字都存储下来，而查询只要遍历对应的链表即可，这样实际复杂度取决于查询的链表长度，也可以看做是常熟级。
例如：我们定义哈希函数，对数组
，进行哈希运算后，插入一些数据的效果如下图。
（3）哈希函数的构造
取余法构造哈希：，为了尽量避免冲突，一般选取为能够存储下并且尽量大的素数（一般情况下我们根据空间取
左右的素数）。一般的说，如果 b 的约数越多，那么冲突的几率就越大。
2、使用数组模拟邻接表
（1）插入关键操作：
v = hash(x);//计算x的哈希值
idx++;
e[idx] = x;
ne[idx] = h[v];
h[v] = idx;（2）查找关键操作：
int v = hash(x);//计算x的哈希值
//循环链表
for(int i=h[v];i!=0;i=ne[i]){if(e[i] == x){return true;}
}例如：读入整数2 5 6 8 3 11，假设
则：每个元素的哈希值是2 5 0 2 3 5
存储数组如下：
element数组：按读入的顺序，存储每个元素的值。
next数组：next[i]存储和element[i]哈希值相同的上一个数的编号。
header数组：header[i]存储哈希值为i的最后一个元素的编号
制作不易，点个赞吧！！！
制作不易，点个赞吧！！！
制作不易，点个赞吧！！！