哈希表

一、哈希表的简介

哈希表，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数。

为什么叫哈希？

可能大家会觉得他是不是以某个人名字命名的，毕竟在国外有很多人的名字以哈开头，比如哈利波特、哈里森.福特.......,其实不是人名，他是英语Hash的音译，Hash 的意思呢是把什么弄乱，把什么弄糟的意思，所以哈希函数还有一些其他称呼，比如散列函数、杂凑函数。

二、什么叫哈希表？

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希（Hash）表，函数f(key)为哈希(Hash) 函数。

从这段解释中，我们理应知道的：

哈希表是一种数据结构

哈希表表示了关键码值和记录的映射关系

哈希表可以加快查找速度

任意哈希表，都满足有哈希函数f(key)，代入任意key值都可以获取包含该key值的记录在表中的地址

用大白话举个例子：假如我有一家水果店，我把所有的水果价格都都放到一张表里，那这张表就可以称为哈希表（或者散列表）。光是一张表还没有太大作用，我们要在这张表里加入哈希函数，接下来我们再来了解一下哈希函数是什么。

三、哈希表能解决什么问题？

那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。

例如要查询一个名字是否在这所学校里。

要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1) 就可以做到。

我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

将学生姓名映射到哈希表上就涉及到了hash function ，也就是哈希函数。

四、什么叫哈希函数？

为了方便理解，我们还是来举一个例子：

首先要知道数据都存储在内存中，假设有几万条商品价格的数据在内存中，我们想从中找到“苹果”价格，如果你事先不知道商品存储规律，就只能一个个去查找，比如第一个是香蕉、第二个是梨，直到第250个才查到苹果。而如果我们记得每个商品价格存在那个位置就没必要去查找，比如直接去查250号的苹果价格。在计算机中的表现就是知道每条数据对应的内存地址，直接去取相应地址的数据。现在的需求是如何在计算机中实现告诉我一个商品描述，瞬间得到该商品信息存储在哪个地址。于是数学家们设计了一套算法，这套算法能够对数据进行一个简单的摘要，可以简单理解为用不同的整数代表不同的数据，这套算法就是哈希算法（也称为哈希函数）。

在存储数据时，我们先对数据的一些描述信息，比如“苹果”，进行哈希运算，得到一个整数，将该整数做些简单处理，转化为一个内存地址，然后将数据存在这个地址对应的存储空间。下次取数据时，仍然对描述信息做哈希运算，得到对应的存储地址，然后到该地址直接取到完整的数据。这样就不用一个个去遍历查找了，即便上亿条数据，也可以瞬间得到想要的数据。

这种数据储存的地址依赖哈希运算得到的整数，所以存储是不连续的，编程中提到的字典、map一般就是这种数据结构，而另一种数据结构“数组”则是连续存储的，这两种数据结构各有优缺点各有用途。还有哈希具体的算法实现有很多，也可以根据不同的需求进行不断完善改进。哈希可以对任意数据运算，包括文本，电影，图片，这个很容易理解，因为计算机中数据本质都是二进制01。

还有个很重要的点，哈希运算得到的值并不一定唯一，也就是不同数据有可能哈希值相同。这个也很容易理解，比如我们生成一个8位的哈希值，只要正数，最多也就127个数，如果对1000个数据进行运算，生成1-127之间的数，那必然会有重复。当然这个例子比较极端，我们取的位数不可能那么小。一般重复率极低，我们也有其他办法应对重复的问题。

五、哈希函数内部实现

经过上面的介绍，大家可能会觉得这个函数太难了、太高大上了，其实也不尽其然，技术是为现实需要服务的，抛开需求谈技术方案都是耍流氓，在某些特定的场合，我们甚至可以自己设计算法来实现这个函数，有个很容易理解的方法，叫平方取中法：

     当无法确定关键字中哪几位分布较均匀时，先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。通过平方扩大差别，另外，中间几位与关键字中的每一位都相关，故不同关键字会以较高的概率产生不同的、均匀的哈希地址。这是一种较常用的构造哈希函数的方法。

       举例：将一组关键字(0100，0110，1010，1001，0111)

       平方后得(0010000，0012100，1020100，1002001，0012321)

       若取表长为1000，则可取中间的三位数作为散列地址集：(100，121，201，020，123)。

除了平方取中法，还有一些其他的方法可以构造哈希函数，接下来就依次列举一下。

直接地址法（适合均匀哈希函数）：

对于关键字是整数类型的数据，直接地址的哈希函数H直接利用关键字求的哈希地址。H(Ki)=aKi+b， (a，b为常量)

例，有一个人口统计表，记录了从1岁到100岁的人口数目，其中年龄作为关键字，哈希函数取关键字本身，如下图：

　　可以看到，当需要查找某一年龄的人数时，直接查找相应的项即可。如查找99岁的老人数，则直接读出第99项即可。

　　显然对空间需求较大，这种哈希函数简单，并且对于不同的关键字不会产生冲突，但可以看出这是一种较为特殊的哈希函数，实际生活中，关键字的元素很少是连续的。用该方法产生的哈希表会造成空间大量的浪费，因此这种方法适应性并不强。

　　此法仅适合于：地址集合的大小 = 关键字集合的大小，其中a和b为常数。

优点：简单、均匀，不会产生冲突

缺点：需要知道关键字的分布，现实中不常用

数字分析法（适用于关键字位数比哈希地址位数大，且关键字已知）：

若关键字是以r为基的数（如：以10为基的十进制数），并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。

举例：有80个记录，其关键字为8位十进制数，假设哈希表长，则可取两位十进制数组成哈希地址，为了 尽量避免冲突，可先分析关键字。

8 1 3 4 6 5 3 2

8 1 3 7 2 2 4 2

8 1 3 8 7 4 2 2

8 1 3 0 1 3 6 7

8 1 3 2 2 8 1 7

8 1 3 3 8 9 6 7

8 1 3 5 4 1 5 7

8 1 3 6 8 5 3 7

8 1 4 1 9 3 5 5

                                             ...........

经分析，发现第一位、第二位都是8,1，第三位只可能取3或4，第八位只可能取2,5或7，所以这四位不可取，那么对于第四、五、六、七位可看成是随机的，因此，可取其中任意两位，或取其中两位与另外两位的叠加求和舍去进位作为哈希地址。

六、总结

优点：

1.不论哈希表中有多少数据，查找、插入、删除（有时包括删除）只需要接近常量的时间即0(1）的时间级。实际上，这只需要几条机器指令。

2.哈希表运算得非常快，在计算机程序中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器)哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。

3.哈希表不仅速度快，编程实现也相对容易。如果不需要有序遍历数据，并且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

缺点：

它是基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重，所以程序员必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。