哈希——哈希表

回顾/本期梗概

        上期我们学习了哈希——字符串哈希（空降链接），本期我们将学习哈希中的哈希表。

---

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的最后一个元素的编号

---

制作不易，点个赞吧！！！ 

制作不易，点个赞吧！！！ 

制作不易，点个赞吧！！！