哈希表

哈希表是第一种非常重要的数据结构。

哈希表通常是基于数组实现的，但是相对于数据，他有很多优势：

哈希表的特点

• 可以提供非常快速的插入-删除-查找操作
• 无论多少数据，插入和删除值需要解禁常量的时间，即O（1）的时间级，实际上，只需要几个机器指令即可完成
• 哈希表的速度比树还快，基本可以瞬间查找到想要的元素
• 哈希表相对于树来说编码要容易很多

数组的缺点

数组插入数据操作时候，效率比较低，需要将元素挪位置

数组进行查找操作的效率：

如果是基于索引查找效率非常高，如果基于内容查找（比如查找name = '小鱼'）需要不停的对比元素

数组进行删除操作，需要将被删除后面的元素依次往前移动，效率也不高。

修改操作和查找操作一样，需要依次对比数据找到元素后进行修改，效率也不高。

哈希表的不足

哈希表中的数据是没有顺序的，所以不能以一种固定的方式（比如从小到大）来遍历其中的元素。

通常情况下哈希表的key是不允许重复的，不能放置相同的key，用于保存不同的元素。

什么是哈希表

他的结构是数组，但是他神奇的地方在于对下标值的一种变换，这种变换可以称之为哈希函数，通过哈希函数可以获取HashCode

下面有三个案例，需要挑选某种数据结构，而你会发现最好的选择就是哈希表

案例一：使用一种数据结构保存所有员工

案例二：设计一个数据结构，保存联系人和电话

案例三：使用一种数据结构存储单词信息，比如有50000个单词，找到单词后每个单词有自己的翻译&读音&应用等

• 案例介绍

假如一家公司有1000个员工，现在需要将这些员工的信息使用某种数据结构来保存，你会采用什么数据结构呢？

方案一：数组

按照顺序将所有员工依次存入一个长度为1000的数组中，每个员工的信息都保存在数组的某个位置上。但是要查找某个具体员工的信息怎么办呢？一个个找吗？不太好找。数组最大的优势是什么？通过下标值获取信息。

所以为了可以通过数组快速定位到某个员工，最好给员工信息中添加一个员工编号（工号），而编号对应的就是员工的下标值。当查找某个员工的信息时，通过员工编号就可以快速定位到员工的信息。

方案二：链表

链表对应插入和删除数据有一定的优势。但是对于获取员工的信息，每次都必须从头遍历到尾，这种方式显然不是特别合适。

最终方案

链表和数组对比，似乎就是数组了，但是数组还有缺点，什么缺点呢？假如想查看一下 Hurry 这位员工的信息，但是又不知道 Hurry 的员工编号，怎么办呢？

当然，你说我可以问 Hurry ，但是你每查一个员工都问一下这个员工的编号么，显然不这样做不好。

线性查找呢？效率非常的低。

能不能有一种办法，让Hurry的名字和他的员工编号产生直接的关系呢？也就是通过 Hurry 这个名字，就能获取到他的索引值，而在通过索引值就能获取到 Hurry 的信息呢？ 这样的方案已经存在了，就是使用哈希函数，让某个 key 的信息和索引值对应起来。

认识哈希化

怎样才能将一个字符串转成数组的下标值呢？

计算机中有很多编码方案就是用数字代替单词的字符即字符编码。比如ASCII编码，a 是 97, b 是 98 以此类推 122 代表 z。我们可以设计一个自己的编码系统，比如 a 是 1 , b 是 2, c 是 3 以此类推 z 是 26。空格用 0 表示。有了对应的编码，一个单词如何转成数字呢？

方案一：数字相加

一种转换单词的简单方案就是把单词的每个字符编码求和。例如单词 cats 转成数字： 3 + 1 + 20 + 19 = 43。那么 43 就作为 cats 单词的下标存在数组中。

按照这种方案有一个明显的问题就是很多单词最终的下标可能都是 43。 比如 was 、tin 、tend 、 moan 等。数组中一个下标位置只能存储一个数据。如果存入后来的数据，必然会造成数据的覆盖。一个下标存储这么多单词显然是不合理的。

方案二：幂的连乘

通过一个种算法，让 cats 转成数字后不那么普通（数字相加的方案过于普通）。

cats = 3 * 27^3 + 1 * 27^2 + 20 * 27 + 19 = 60337。这样可以基本保证他的唯一性。不会和别的单词重复。

但是如果存放一个单词，就需要创建一个 60337 大的数组，也是不合理的，数组太大没有意义，有很多无效的空数据。

第一种方案把数字相加求和，产生的数组下标太少

第二种方案与27幂相乘求和产生的数组下标又太多

需要一种压缩方法，把幂的连乘方案中得到的巨大整数范围压缩到可接受的数组范围。

如果只有50000 个单词，可能会定义一个长度为 50000 的数组。但是实际情况中，往往需要更大的空间来存储这些单词，比如两倍的大小 100000，因为不能保证单词会映射到每一个位置。

有一种简单的解决方法就是使用取余操作符，他的作用是得到一个数被另一个数整除后的余数。假设把从 0 ~ 199 的数字（largeNumber）压缩为 0 到 9 的数字（smallRange）。 下标值的结果： index = largeNumber % smallRange 即当一个数被 10 整除时，余数一定在 0 ~ 9 之间。比如 13 % 10 = 3 ， 157 % 10 = 7。 当然中间还是有重复的，不过重复的数量明显变小了。

哈希化

哈希化：将大数字转化成数组范围内下标的过程，称之为哈希化。

哈希函数：通常我们会将单词转成大数字，大数字在进行哈希化的代码实现放在一个函数中，这个函数我们称为哈希函数

哈希表：最终将数据插入到这个数组中，对整个结构的封装，称之为哈希表

什么是冲突

0 - 199 的数字选取 5 个放在长度为10 的单元格中，如果随机选出来的数字是 33、82、11、45、90 那么最终他们的位置会是 3、2、1、5、0，此时没有冲突。

如果在加一个 73呢，那么就有两个 3 了。

需要针对这种冲突，提出一些解决方案。

• 链地址法
• 开放地址法