# 10.哈希表：高效率查找的利器

线性表中的栈和队列对增删有严格要求，他们会更关注数据的顺序
数组和字符串需要保持数据类型的统一，并且在基于索引的查找会更有优势
树的优势则体现在数据的层次结构上

他们普遍都存在这样的缺陷，就是数据树值条件的查找，都需要对全部数据或部分数据进行遍历。那么，有没有一种可以省去数据比较过程，从而进一步提升树值条件查找效率？这一课就来介绍这样一种高效率查找神奇，哈希表。

# 10-1 什么是哈希表

哈希表源于Hash,也可以叫做散列表。哈希表是一种特殊的数据结构，它与数组、链表以及树等我们之前学过的数据结构相比，很明显有区别。

# 10-1 哈希表的核心思想

在之前学习的数据结构里，数据存储位置和数据的具体数值之间不存在任何关系，在面对查找问题时，这些数据必须采取逐一比较的方法去实现

哈希表的设计采用的是函数映射的思想，将记录的存储位置与记录的关键字关联起来，这样的设计方式，能够快速定位想要查找的记录，而且不需要与表中存在的记录关键字比较后再进行查找

数组的查找，是通过数据索引值(index)来取值的，例如要找出a数组中，索引值为1的元素，可以直接用a[1]取出这个数据，通过这样的方式，就实现了‘地址 = f(index)’的映射关系

如果用哈希表的逻辑来理解的话，这里的f()就是一个哈希函数。它完成了索引值到司机地址的映射，这就让数组可以快速完成基于索引值的查找。然而局限性在于，它只能基于数据的索引值去查找，而不能基于数据的数值去查找。

如果有一种方法，可以实现‘地址 = f(关键字)’的映射关系，那么就可以快速完成基于数据的数值的查找了，这就是哈希表的核心思想

假如，我们要对一个手机通讯录进行存储，并根据姓名查找一个人的手机号码，如下所示：
张一：155555555
张二：166666666
张三：177777777
张四：188888888

一个可行的方法就是，定义包含姓名、手机号码的结构体，再通过链表把4个联系人的信息存起来；当判断‘张四’是否在链表中，或想查看手机号时，就需要从链表的头结点开始遍历。依次将每个结点中的姓名字段，同‘张四’进行比较。直到查找成功或者全部遍历一次位置，这种做法的时间复杂度为O(n)

如果要降低时间复杂度，就需要借助哈希表的思路，构建姓名到地址映射函数‘地址=f(姓名)’，这样我们就可以通过函数直接计算出‘张四’的存储位置，在O(1)时间复杂度内就可以完成数据的查找。

通过这个例子，不难看出Hash函数设计的好坏会直接影响到对哈希表的操作效率，假如对上面的例子采用Hash为，姓名每个字的拼音开头大写字母的ASCII码之和

  address (张一) = ASCII (Z) + ASCII (Y) = 90 + 89 = 179；

  address (张二) = ASCII (Z) + ASCII (E) = 90 + 69 = 159；

  address (张三) = ASCII (Z) + ASCII (S) = 90 + 83 = 173；

  address (张四) = ASCII (Z) + ASCII (S) = 90 + 83 = 173；

有一个致命问题，就是f(张三)和f(张四)都是173，这种现象称作哈希冲突，是需要在设计哈希函数时进行规避的

本质上，哈希冲突只能尽可能的减少，不能完全避免。这是因为输入的关键字是个开放集合。只要输入的数据量够多，分布够广，就完全可能发生冲突。因此哈希表需要设计合理的哈希函数，并且对冲突有一套处理机制。

# 10-2 如何设计哈希函数

直接定制法

哈希函数为关键字到地址的线性函数。如，H(key) = a*key + b 这里的a和b最好设置函数

数字分析法

假设关键字集合中的每个关键字key都是由s位数字组成(k1,k2,...ks),并从中提取分布均匀的若干位组成哈希地址

平方取中法

如果关键字的每一位都有某些数字重复出现，并且频率很高，我们就先求关键字的平方值，通过平方扩大差异，然后取中间几位作为最终存储地址

折叠法

如果关键字的位数很多，可以将关键字分割位几个等长的部分，取他们的叠加和的值(舍去进位)作为哈希地址

除留余数法

预先设置一个树p,然后对关键字进行取余运算。即地址为 key mod p

# 10-3 如何解决哈希冲突

出现冲突，如何解决，一般有两种方法

第一，开发定址法

当一个关键字和另一个关键字发生冲突时，使用某种探测技术在哈希表中形成一个探测序列，然后沿着这个探测序列依次查下去，碰到一个空单元时，则插入其中

常用的探测方法是线性探测法：比如一组关键字{12,13,25,23},采用的哈希函数为key mod 11,但插入12,13,25时可以直接插入，地址分别为1、2、3；而当插入23时，哈希地址为23 mod 11 = 1;然而，地址1已经被占用，因此沿着地址1依次往下探测，直到探测到地址4，发现为空，则将23插入其中。

第二，链地址法

将哈希地址相同的记录存储在一张线性链表中
哈希表相对于其他数据结构有很多优势，它可以提供非常快速插入-删除-查找操作，无论多少数据，插入和删除值需要接近常量的时间。在查找方面，哈希表的速度比树还快，基本可以瞬间查找到想要的元素。
哈希表也有一些不足，哈希表中的数据是没有顺序概念的，所以不能1⃣以一种固定的方式来遍历其中的元素。在数据处理顺序敏感问题时，选择哈希表并不是一个好的处理方法。同时，哈希表的key是不允许重复，在重复性非常高的数据中，哈希表也不是一个好的选择。

# 10-4 哈希表的基本操作

在很多高级语言中，哈希函数、哈希冲突都已经在底层完成了黑盒化处理，是不需要自己设计的，也就是说，哈希表完成了关键字到地址的映射，可以在常数级时间复杂度内通过关键字查找到数据。

哈希表中的增加和删除数据操作，不涉及增删后对数据的挪移问题(数组需要考虑)，因此处理就可以了
哈希表查找的细节过程是：对于给定的key,通过哈希函数计算哈希地址H(key)

如果哈希地址对应的值为空，则查找不成功
反之，则查找成功

虽然哈希表查找的细节过程还比较麻烦，但是因为一些高级语言的黑盒化处理，可以不需要关注这些

# 10-5 哈希表的案例

例一：将关键序列{7,8,30,11,18,9,14}存储到哈希表中，哈希函数H(key) = (key*3)%7,处理冲突采用线性探测法

1.首先，我们尝试建立哈希表，求出这个哈希地址

  H (7) = (7 * 3) % 7 = 0

  H (8) = (8 * 3) % 7 = 3

  H (30) = 6

  H (11) = 5

  H (18) = 5

  H (9) = 6

  H (14) = 0

2.按照关键字顺序依次向哈希表中填入，发生冲突后按照‘线性探测’探测到第一个空位置填入
3.接着，有了这个表之后，我们再看一下查找流程
查找 7。输入 7，计算得到 H (7) = 0，根据哈希表，在 0 的位置，得到结果为 7，跟待匹配的关键字一样，则完成查找
查找 18。输入 18，计算得到 H (18) = 5，根据哈希表，在 5 的位置，得到结果为 11，跟待匹配的关键字不一样（11 不等于 18）。因此，往后挪移一位，在 6 的位置，得到结果为 30，跟待匹配的关键字不一样（11 不等于 30）。因此，继续往后挪移一位，在 7 的位置，得到结果为 18，跟待匹配的关键字一样，完成查找

例二：假设一个在线系统，可以实时接收用户提交的字符串关键字，并实时返回给用户累积至今这个关键字被提交的次数
例如，用户输入‘abc’,系统返回1，再输入‘jk’，系统返回1；用户再输入‘abc’,系统返回2，再输入‘abc’,系统返回3

一种解决方法是：用一个数组保存用户提交过的所有关键字，收到新关键字后，插入到数组中，并统计关键字出现的次数

根据数组知识可以计算出，插入到最后的动作，时间复杂度为O(1).但统计出现次数必须要全部数据遍历一遍，时间复杂度为O(n),随着数据越多，时间就会越长，这不是一个明智的方法。

一种是采用哈希表：可以利用哈希表的新增、查找常数级时间复杂度，在O(1)时间复杂度内完成相应。预先定义好哈希表后(可以采用 Map < Integer, Integer > d = new HashMap <> (); ）对于关键字（用变量 key_str 保存），判断 d 中是否存在 key_str 的记录.
1.如果存在，则把它对应的value(记录频次)加1
2.如果不存在，则把它添加到d中，对应的 value 赋值为 1。最后，打印处 key_str 对应的 value，即累积出现的频次

 if(d.containsKey(key_str)){
   d.push(key_str,d.get(key_str) + 1)
 }else{
   d.push(key_str,1)
 }
 doucument.write(d.get(key_str))

# 10-6 总结

哈希表有很多独特的优点，不论哈希表中多少数据，查找、插入、删除都只需要接近常量时间，即O(1)的时间级
哈希表运算非常快，在计算机程序中，如果需要一秒钟内查找上千条数据通常使用哈希表，哈希表速度明显比树快。哈希表不仅速度快，编程实现也相对容易。如果不需要有遍历数据，并且可以提前预测数据量大小，那么哈希表在速度和易用性方面是无与伦比的

← 9.树和二叉树：如何实现增删改查 11.递归：求解汉诺塔问题 →