前言 哈希表的优势

数据结构存在的意义是处理数据，对数据的基本处理无非是增删改查，即插入、删除、查找、修改。对线性表（数组）来说，插入和删除的时间复杂度是O(N)，即每次插入和删除都要改变插入位置后面所有元素的个数，从而造成O(N)的时间复杂度，而查找和修改的时间复杂度是O(1)，因为可以直接用下标得到那个位置的元素。对链表来说，插入和删除的时间复杂度为O(1)，而查找和修改的时间复杂度为O(N)，因为必须从头结点开始查找。而哈希表却可以实现增删改查都是O(1)的时间复杂度，只要设计的哈希函数足够合理。如果足够不合理的话，它查找和修改的最坏时间复杂度也是O(N)。因此，哈希表不只是一个简单的键值存储结构，而是结合了顺序表和链表共同优点的高速存取的数据结构。

哈希表的实质是分布不均匀的线性表，所有元素散列在线性表中，通过哈希函数来计算线性表的索引，通过索引进行存取，存取的数据结构还是基于线性表和链表。同样也会造成不能对线性表空间的利用最大化。

一、哈希函数和哈希码

A hash function is any function that can be used to map data of arbitrary size to data of fixed size. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes. （来自维基百科）

哈希函数就是能将任意长度的数据映射为固定长度的数据的函数。哈希函数返回的值被叫做哈希值、哈希码、散列，或者直接叫做哈希。

固定长度即为所使用的线性表的长度，哈希码即为线性表的索引，通过哈希码直接对数据进行存取。键值对中的键是计算哈希码的主要依据，

常见的哈希函数有：

  • 直接寻址法：取keyword或keyword的某个线性函数值为散列地址。即H(key)=key或H(key) = a*key + b，当中a和b为常数（这样的散列函数叫做自身函数）。
  • 数字分析法：分析一组数据，比方一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体同样，这种话，出现冲突的几率就会非常大，可是我们发现年月日的后几位表示月份和详细日期的数字区别非常大，假设用后面的数字来构成散列地址，则冲突的几率会明显减少。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

  • 平方取中法：取keyword平方后的中间几位作为散列地址。

  • 折叠法：将keyword切割成位数同样的几部分，最后一部分位数能够不同，然后取这几部分的叠加和（去除进位）作为散列地址。

  • 随机数法：选择一随机函数，取keyword的随机值作为散列地址，通经常使用于keyword长度不同的场合。

  • 除留余数法：取keyword被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p <= m。不仅能够对keyword直接取模，也可在折叠、平方取中等运算之后取模。对p的选择非常重要，一般取素数或m，m为线性表的长度。

好的哈希函数会使所有的因素都均匀的分布在线性表中，不会产生哈希冲突，同样，差的哈希函数也会使每个元素都会产生哈希冲突。

二 哈希表的存取

假如现在有一组需要存入哈希表的字符串，我们设置的键值对为：
"1": A", "2": "B", "3": "C", "4": "D", "5": "E", "6": "F", "7": "G", "8": "H", "9": "I"，假设通过键计算得到的哈希码分别是：2，4，6，9，1，3，6，7，9。可以看出，这些数据可以存储到一个长度为10的线性表中(存储的数据类型为结构体或者模型类)：

从上图可看出，线性表下标为6和9的地方产生了哈希冲突，即同一个坑被两个元素占了，这说明我们的哈希函数计算得到的哈希码不是足够均匀。

当取值的时候，可以直接使用哈希码作为下标直接访问线性表的下标，在访问下标的过程中，会对键进行一次比较，如果当前位置存的键和提供的键是同一个键，则取值，如果不是则根据解决哈希冲突的方法继续寻找。

三 哈希冲突

1、线性探测法

如上文所示，在向哈希表中存值得时候产生了哈希冲突，假设线性表下标为6的位置装填了"3": "C"，而我想通过键"7"，获取"G"这个值得时候，因为"7"和"3"的哈希码都是6，因此通过"7"访问的线性表下标为6的位置，就会得到错误的结果。

线性探测法解决哈希冲突的中心思想就是当向线性表中装填键值对的时候，如果当前位置有值存在，则将它装填在线性表当前位置往后的下一个空位，如果当前位置往后都没有位置，那么就从0开始找空位，然后插入。插入的时间复杂度为O(N)，即：

当我们通过键"7"，获取"G"这个值得时候，会先通过哈希码6去找线性表中下标6对应的位置，然后比较键"7"和线性表中存储的键，如果相等则取出，如果不相等，则从当前位置开始向后遍历线性表，超过最后一个则从0开始，直到找到为止。因此，这种查找的时间复杂度为O(N)，假如哈希函数足够差，例如所有键的哈希函数都相等，就会造成每一个元素的查找时间复杂度都为O(N)。

2、链式法

链式法解决哈希冲突的中心思想为将冲突的元素存入一个链表：

"3": "C"为冲突位置链表的头结点，当我们继续插入一个哈希码也为6的键值对10: "J"时，此时：

每次装填发生冲突的键值对时，都会将新加入的键值对插入到冲突链表的头结点。此时插入的时间复杂度为O(1)，同理，当通过键"7"的哈希码6取值得时候，会先比较6的位置中存的键和"7"是否相等，如果相等则取出，否则从头结点开始遍历链表直到找到相等的键为止，此时取出的值即为结果，这种查找的时间复杂度也为O(N)，java语言的HashMap就是用这种方法解决的哈希冲突。

四、其他概念

1、装填因子

装填因子 = 当前装填的元素个数 / 线性表的长度；

每次插入新的元素的时候，我们都会记录当前装填入线性表的元素个数，当装填因子超过某个值得时候，例如0.75，我们就会将线性表的长度进行扩充，然后将线性表中没一个元素都进行重新hash。这样做的目的当然也是为了尽可能的减少哈希冲突，因为装填因子越大，线性表中剩余的位置越少，就越容易产生哈希冲突。

2、isEqual() & hash()

对于C++、java、OC等语言，任何对象都可以作为哈希表的键。已经有的库中的类，他们会实现对应的hash()函数和isEqual()函数，但是当使用开发者自己实现的类的对象作为键的时候，该类必须重写根类的hash()函数和isEqual()函数，hash()函数是为了计算哈希码，isEqual()是为了当发生哈希冲突的时候，可以通过这个方法找到确定的值，因为键的类型为包装对象而不是基础数据类型，所以不能使用简单的==比较地址。