脚本宝典收集整理的这篇文章主要介绍了数据结构 - 哈希表 - 哈希表介绍，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

如果要存储和使用线性表 ((1,75,324,43,1353,90,46))，一般情况下我们会使用一个数组 (A[1..7]) 来顺序存储这些数。但是这样的存储结构会给查询算法带来 (O(n)) 的时间开销。对数组 (A) 排序，使用二分查询法，@R_226_1304@变为 (O(LOG n))。也可以用空间换时间的做法，比如对值域建一个数组，这里用数组 (A[1..1353]) 来表示每个数是否出现，此时查找的时间复杂度变为 (O(1))，但是空间上的开销变得巨大。

哈希表的引入

让我们想一下，若在手机通信录中查找一个人，那我们应该不会从第一个人一直找下去，因为这样实在是太慢了。我们其实是这样做的：首先看这个人的名字的首字母是什么，比如姓张，那么我们一定会滑到最后，因为“Z”姓的名字都在最后。

还有在查字典时，要查找一个单词，肯定不会从头翻到尾，而是首先通过这个单词的首字母，找到对应的那一页；再找第 (2) 个字母、第 (3) 个字母……这样可以快速跳到那个单词所在的页。

对于引用部分给定的例子而言，我们使用哈希表来优化。先建立一个哈希函数 (h(text{key}) = text{key} , % , 23)（这里的 (%) 表示模运算）。此时不管 (text{key}) 有多大，都转化成了模数的范围内，对给定的线性表例子有

此时对值域建立数组，我们只要用一个 (A[0..22]) 数组就可以快速的查询每个数是否出现。这种线性表的结构就称为哈希表（(text{Hash Table})），也称散列表。对哈希表有一种需要重点讨论的情况，即对两个的 (text{key}_1) 和 (text{key}_2) 出现了

此时称这种情况为冲突。

哈希表的基本原理

可以看出，哈希表的基本原理是用一个下标范围比较大（下标范围太小容易冲突），相对原值域又比较小的数组 (A) 来存储元素（上述例子中的下标范围 (23) 相对于值域 (1353)）。

设计一个哈希函数 (h)，对于要存储的线性表的每个元素 (text{node})，取一个关键字 (text{key})，算出函数值 (h(text{key}))，然后把这个值 (text{value}) 作为下标，用 (A[h(text{key})]) 来存储 (text{node})。

举一个例子，在手机通信录中查找一个人，这个人的姓名是“张三”（即 (text{node})），我们取该姓名的首字母"Z"作为关键字（即 (text{key})），然后利用哈希函数 (h(text{Z})=26) 得到哈希值 (26)（即 (text{value})，哈希函数的映射规则表示为 "Z" 是第 (26) 个英文字母），然后在哈希表中找到 (h[26])，若用链地址法，可能还需再在 (h[26]) 的链表中具体查找 (text{node}) “张三”。

例子所展示的过程如图所示：

哈希函数的选择

按我们之前的介绍，哈希函数需要满足以下条件

• 哈希函数计算得到的哈希值应该是一个非负整数（以便作为哈希表的索引或称下标）。

• 如果两个关键字 (k_1 = k_2)，则 (h(k_1) = h(k_2))。

哈希函数比较常用的实现方法比较多，通常需要考虑几个因素：关键字的长度、哈希表的大小、关键字的分布情况、记录的查找频率，等等。

下面简单介绍几种哈希函数。

• 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。

• 数字分析法：通过对数据的分析，发现数据中冲突较少的部分，并构造散列地址。例如同学们的学号，通常同一届学生的学号，其中前面的部分差别不太大，所以用后面的部分来构造散列地址。

• 平方取中法：当无法确定关键字里哪几位的分布相对比较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为散列地址。这是因为：计算平方之后的中间几位和关键字中的每一位都相关，所以不同的关键字会以较高的概率产生不同的散列地址。

• 取随机数法：使用一个随机函数，取关键字的随机值作为散列地址，这种方式通常用于关键字长度不同的场合。

• 除留取余法：取关键字被某个不大于散列表的表长 (n) 的数 (m) 除后所得的余数 (p) 为散列地址。这种方式也可以在用过其他方法后再使用。该函数对 (m) 的选择很重要，一般取素数或者直接用 (n)。

哈希表的冲突

存在一个问题，可能存在两个 (text{key})，分别为 (k_1)，(k_2)。使得 (h(k_1) = h(k_2))，即此时产生了冲突。

解决冲突有很多种方法：

• 开放地址法（也叫开放寻址法）：实际上就是当需要存储值时，对Key哈希之后，发现这个地址已经有值了，这时该怎么办？不能放在这个地址，不然之前的映射会被覆盖。这时对计算出来的地址进行一个探测再哈希，比如往后移动一个地址，如果没人占用，就用这个地址。如果超过最大长度，则可以对总长度取余。这里移动的地址是产生冲突时的增列序量。

• 再哈希法：在产生冲突之后，使用关键字的其他部分继续计算地址，如果还是有冲突，则继续使用其他部分再计算地址。这种方式的缺点是时间增加了。即我们可以用另一个函数 (I) 去计算 (I(k_1)) 和 (I(k_2))，并使得 (I(k_1) neq I(k_2))，从而找到新的位置（这种方式与查字典很像，我们查找 ant 和 and 两个单词，首字母 a 发生了冲突，就接着继续哈希第二个字母）。

• 链地址法：链地址法其实就是对 (text{Key}) 通过哈希之后落在同一个地址上的值，做一个链表。即对于 (h(k_1)) 和 (h(k_2))，如果这两个产生了冲突，我们让这两个 (text{node}) 都接在 (A[h(k_1)]) 的链表上。在很多高级语言的实现当中，也是使用这种方式处理冲突的，我们一般着重使用这种方式。

实现过程中，我们一般采用后一种。假设我们使用第二种方法解决冲突。

对于插入元素 ((text{node},text{key}))：计算 (h(text{key}))，把 (text{node}) 插入到 (A[h(text{key})]) 链表中。

对于查询元素 ((text{node},text{key}))：计算 (h(text{key}))，如果 (A[h(text{key})]) 为空，说明 (text{node}) 不存在。否则遍历 (A[h(text{key})]) 链表，寻找 (text{node})。

哈希表的代码实现

我们以结点 (text{node}) 为整数做代码介绍，此时可直接将 (text{node}) 的值作为关键字。

脚本宝典总结

以上是脚本宝典为你收集整理的数据结构 - 哈希表 - 哈希表介绍全部内容，希望文章能够帮你解决数据结构 - 哈希表 - 哈希表介绍所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。