目录
1.哈希概念
2.哈希冲突
3.哈希函数
4.哈希冲突解决
闭散列 --- 开放定值法
开散列
开散列与闭散列比较
5.哈希表的闭散列实现
6.哈希表的开散列实现(哈希桶)
7.哈希表大小建议为素数
- 顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。搜索的效率取决于搜索过程中元素的比较次数，因此顺序结构中查找的时间复杂度为O(N)，平衡树中查找的时间复杂度为树的高度O(logN)。
- 而最理想的搜索方法是，可以不经过任何比较，一次直接从表中得到要搜索的元素，即查找的时间复杂度为O(1)。
- 如果构造一种存储结构，该结构能够通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时就能通过该函数很快找到该元素。
①向该结构当中插入和搜索元素的过程如下：
- 插入元素： 根据待插入元素的关键码，用此函数计算出该元素的存储位置，并将元素存放到此位置。
- 搜索元素： 对元素的关键码进行同样的计算，把求得的函数值当作元素的存储位置，在结构中按此位置取元素进行比较，若关键码相等，则搜索成功。
②该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表 (Hash Table)(或者称散列表)
- 例如：数据集合{1，7，6，4，5，9}；
- 哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
- 用该方法进行存储，在搜索时就只需通过哈希函数判断对应位置是否存放的是待查找元素，而不必进行多次关键码的比较，因此搜索的速度比较快。
- 不同关键字通过相同哈希函数计算出相同的哈希地址，这种现象称为哈希冲突或哈希碰撞。我们把关键码不同而具有相同哈希地址的数据元素称为“同义词”。
- 例如: 在上述例子中，再将元素44插入当前的哈希表就会产生哈希冲突。 因为元素44通过该哈希函数得到的哈希地址与元素4相同，都是下标为4的位置
- hash(44)=44%10=4
(1)引起哈希冲突的一个原因可能是哈希函数设计不够合理 ；哈希函数设计的原则：
- 哈希函数的定义域必须包括需要存储的全部关键码，且如果散列表允许有m个地址，其值域必须在0到m-1之间。
- 哈希函数计算出来的地址能均匀分布在整个空间中。
- 哈希函数应该比较简单。
(2)常见的哈希函数如下
- 哈希函数设计的越精妙，产生哈希冲突的可能性越低，但是无法避免哈希冲突
①直接定址法（常用）
- 取关键字的某个线性函数为哈希地址 : Hash(Key) = A*Key + B
- 优点：每个值都有一个唯一位置，效率很高，每个都是一次就能找到。
- 缺点：使用场景比较局限，通常要求数据是整数，范围比较集中。
- 使用场景：适用于整数，且数据范围比较集中的情况。
②除留余数法（常用）
- 设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(Key) = Key % p(p<=m)，将关键码转换成哈希地址。
- 优点：使用场景广泛，不受限制。
- 缺点：存在哈希冲突，需要解决哈希冲突，哈希冲突越多，效率下降越厉害。
③平方取中法(了解)
- 假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址。
- 使用场景：不知道关键字的分布，而位数又不是很大的情况。
④折叠法(了解)
- 折叠法是将关键字从左到右分割成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。
- 使用场景：折叠法适合事先不需要知道关键字的分布，或关键字位数比较多的情况。
⑤随机数法(了解)
- 选择一个随机函数，取关键字的随机函数值为它的哈希地址，即 Hash(Key) = random(Key)，其中random为随机数函数。
- 使用场景：通常应用于关键字长度不等时。
⑥数字分析法
- 设有n个d位数，每一位可能有r种不同的符号，这r中不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，而在某些位上分布不均匀，只有几种符号经常出现。此时，我们可根据哈希表的大小，选择其中各种符号分布均匀的若干位作为哈希地址。
举例:
- 假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同的，那么我们可以选择后面的四位作为哈希地址。
- 如果这样的抽取方式还容易出现冲突，还可以对抽取出来的数字进行反转（如1234改成4321）、右环位移（如1234改成4123）、左环位移（如1234改成2341）、前两数与后两数叠加（如1234改成12+34=46）等操作。
- 数字分析法通常适合处理关键字位数比较大的情况，或事先知道关键字的分布且关键字的若干位分布较均匀的情况。
闭散列 --- 开放定值法
-
闭散列，也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表种必然还有空位置，那么可以把产生冲突的元素存放到冲突位置的“下一个”空位置中去。
1.线性探测
-
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止
(1)插入
用除留余数法将序列{1，7，6，4，5，9 , 44 , 54 }插入到表长为10的哈希表中，当发生哈希冲突时我们采用闭散列的线性探测找到下一个空位置进行插入
- 通过哈希函数获取待插入元素在哈希表中的位置
- 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探 测找到下一个空位置，插入新元素
负载因子
①随着哈希表中数据的增多，产生哈希冲突的可能性也随着增加，最后在54进行插入的时候更是连续出现了6次哈希冲突。
②我们将数据插入到有限的空间，那么空间中的元素越多，插入元素时产生冲突的概率也就越大，冲突多次后插入哈希表的元素，在查找时的效率必然也会降低。介于此，哈希表当中引入了负载因子（载荷因子）：
- 负载因子 = 表中有效数据个数 / 空间的大小
- 负载因子越大，产出冲突的概率越高，增删查改的效率越低。
- 负载因子越小，产出冲突的概率越低，增删查改的效率越高。
③负载因子越小，也就意味着空间的利用率越低，此时大量的空间实际上都被浪费了。
- 对于闭散列（开放定址法）来说，负载因子是特别重要的因素，一般控制在0.7~0.8以下，超过0.8会导致在查表时CPU缓存不命中（cache missing）按照指数曲线上升。
- 因此，一些采用开放定址法的hash库，如JAVA的系统库限制了负载因子为0.75，当超过该值时，会对哈希表进行增容。
④线性探测优缺点
- 线性探测的优点：实现非常简单。
- 线性探测的缺点：一旦发生冲突，所有的冲突连在一起，容易产生数据“堆积”，即不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要多次比较（踩踏效应,洪水效应），导致搜索效率降低。
(2)删除
2.二次探测
(1)线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：
- Hi = (H0 + i^2 )%m (i=1,2,3,...)
- H0：通过哈希函数对元素的关键码进行计算得到的位置。
- Hi：冲突元素通过二次探测后得到的存放位置。
- m：表的大小。
(2)用除留余数法将序列{1，7，6，4，5，9 , 44 , 54 }插入到表长为10的哈希表中, 当发生哈希冲突时我们采用闭散列的二次探测找到下一个空位置进行插入
- 采用二次探测为产生哈希冲突的数据寻找下一个位置，相比线性探测而言，采用二次探测的哈希表中元素的分布会相对稀疏一些，不容易导致数据堆积。
- 和线性探测一样，采用二次探测也需要关注哈希表的负载因子
- 因此，闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。
开散列
-
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
(1)用除留余数法将序列{1，7，6，4，5，9 , 44 , 54 }插入到表长为10的哈希表中，当发生哈希冲突时我们采用开散列的形式，将哈希地址相同的元素都链接到同一个哈希桶下
- 闭散列解决哈希冲突，采用的是一种报复的方式，“我的位置被占用了我就去占用其他位置”。而开散列解决哈希冲突，采用的是一种乐观的方式，“虽然我的位置被占用了，但是没关系，我可以‘挂’在这个位置下面”。
- 与闭散列不同的是，这种将相同哈希地址的元素通过单链表链接起来，然后将链表的头结点存储在哈希表中的方式，不会影响与自己哈希地址不同的元素的增删查改的效率，因此开散列的负载因子相比闭散列而言，可以稍微大一点。
- 闭散列的开放定址法，负载因子不能超过1，一般建议控制在[0.0, 0.7]之间。
- 开散列的哈希桶，负载因子可以超过1，一般建议控制在[0.0, 1.0]之间。
(2)在实际中，开散列的哈希桶结构比闭散列更实用
- 哈希桶的负载因子可以更大，空间利用率高。
- 哈希桶在极端情况下还有可用的解决方案。
①哈希桶的极端情况就是，所有元素全部产生冲突，最终都放到了同一个哈希桶中，此时该哈希表增删查改的效率就退化成了O(N)
②我们可以考虑将这个桶中的元素，由单链表结构改为红黑树结构，并将红黑树的根结点存储在哈希表中
- 为了避免出现这种极端情况，当桶当中的元素个数超过一定长度，有些地方就会选择将该桶中的单链表结构换成红黑树结构，比如在JAVA中比较新一点的版本中，当桶当中的数据个数超过8时，就会将该桶当中的单链表结构换成红黑树结构，而当该桶当中的数据个数减少到8或8以下时，又会将该桶当中的红黑树结构换回单链表结构。
- 但有些地方也会选择不做此处理，因为随着哈希表中数据的增多，该哈希表的负载因子也会逐渐增大，最终会触发哈希表的增容条件，此时该哈希表当中的数据会全部重新插入到另一个空间更大的哈希表，此时同一个桶当中冲突的数据个数也会减少，因此不做处理问题也不大。
开散列与闭散列比较
- 应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上： 由于开地址法必须保持大 量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间
(1)哈希表结构
①在闭散列的哈希表中，哈希表每个位置除了存储所给数据之外，还应该存储该位置当前的状态，哈希表中每个位置的可能状态如下：
- EMPTY（无数据的空位置）。
- EXIST（已存储数据）。
- DELETE（原本有数据，但现在被删除了）。
②为什么需要标识哈希表中每个位置的状态？
1. 若是不设置哈希表中每个位置的状态，那么在哈希表中查找数据的时候可能是这样的。以除留余数法的线性探测为例，我们若是要判断下面这个哈希表是否存在元素44，步骤如下：
- 通过除留余数法求得元素44在该哈希表中的哈希地址是4。
- 从4下标开始向后进行查找，若找到了44则说明存在。
2. 但是我们在寻找元素44时，不可能从4下标开始将整个哈希表全部遍历一次，这样就失去了哈希的意义。我们只需要从4下标开始往后查找，直到找到元素44判定为存在，或是找到一个空位置判定为不存在即可。但这种方式是不可行的，原因如下：
- 如何标识一个空位置？用数字0吗？那如果我们要存储的元素就是0怎么办？因此我们必须要单独给每个位置设置一个状态字段。
- 如果只给哈希表中的每个位置设置存在和不存在两种状态，那么当遇到下面情况时就会出现错误。
- 我们先将上述哈希表当中的元素44找到，并将其删除，此时我们要判断当前哈希表当中是否存在元素54，当我们从4下标开始往后找到8下标（空位置）时，我们就应该停下来，此时并没有找到元素54，但是元素54却在哈希表中存在。
- 因此我们必须为哈希表中的每一个位置设置一个状态，并且每个位置的状态应该有三种可能，当哈希表中的一个元素被删除后，我们不应该简单的将该位置的状态设置为EMPTY，而是应该将该位置的状态设置为DELETE。
- 这样一来，当我们在哈希表中查找元素的过程中，若当前位置的元素与待查找的元素不匹配，但是当前位置的状态是EXIST或是DELETE，那么我们都应该继续往后进行查找，而当我们插入元素的时候，可以将元素插入到状态为EMPTY或是DELETE的位置。
3.闭散列的哈希表中的每个位置存储的结构，应该包括所给数据和该位置的当前状态。
4.而为了在插入元素时好计算当前哈希表的负载因子，我们还应该时刻存储整个哈希表中的有效元素个数，当负载因子过大时就应该进行哈希表的增容。
(2)哈希表插入
①向哈希表中插入数据的步骤如下：
- 查看哈希表中是否存在该键值的键值对，若已存在则插入失败。
- 判断是否需要调整哈希表的大小，若哈希表的大小为0，或负载因子过大都需要对哈希表的大小进行调整。
- 将键值对插入哈希表。
- 哈希表中的有效元素个数 ++
②哈希表的调整方式如下：
- 若哈希表的大小为0，则将哈希表的初始大小设置为10。(可以更大)
- 若哈希表的负载因子大于0.7，则先创建一个新的哈希表，该哈希表的大小为原哈希表的两倍，之后遍历原哈希表，将原哈希表中的数据插入到新哈希表，重新映射，最后将原哈希表与新哈希表交换即可。
- 注意 : 在将原哈希表的数据插入到新哈希表的过程中，不能只是简单的将原哈希表中的数据对应的挪到新哈希表中，而是需要根据新哈希表的大小重新计算每个数据在新哈希表中的位置，然后再进行插入。
③将键值对插入哈希表的具体步骤如下：
- 通过哈希函数计算出对应的哈希地址。
- 若产生哈希冲突，则从哈希地址处开始，采用线性探测向后寻找一个状态为EMPTY或DELETE的位置。
- 将键值对插入到该位置，并将该位置的状态设置为EXIST。
④代码
- 产生哈希冲突向后进行探测时，一定会找到一个合适位置进行插入，因为哈希表的负载因子是控制在0.7以下的，也就是说哈希表永远都不会被装满。
(3)哈希表查找
①在哈希表中查找数据的步骤如下：
- 先判断哈希表的大小是否为0，若为0则查找失败。
- 通过哈希函数计算出对应的哈希地址。
- 从哈希地址处开始，采用线性探测向后向后进行数据的查找，直到找到待查找的元素判定为查找成功，或找到一个状态为EMPTY的位置判定为查找失败。
②代码
- 在查找过程中，必须找到位置状态为EXIST，并且key值匹配的元素，才算查找成功。若仅仅是key值匹配，但该位置当前状态为DELETE，则还需继续进行查找，因为该位置的元素已经被删除了。
(4)哈希表删除
①我们只需要进行伪删除即可，也就是将待删除元素所在位置的状态设置为DELETE。
- 查看哈希表中是否存在该键值的键值对，若不存在则删除失败。
- 若存在，则将该键值对所在位置的状态改为DELETE即可。
- 哈希表中的有效元素个数 - -
②代码
- 虽然删除元素时没有将该位置的数据清0，只是将该元素所在状态设为了DELETE，但是并不会造成空间的浪费，因为我们在插入数据时是可以将数据插入到状态为DELETE的位置的，此时插入的数据就会把该数据覆盖
(1)哈希表的结构
① 哈希表的每个位置存储的实际上是某个单链表的头结点，即每个哈希桶中存储的数据实际上是一个结点类型，该结点类型除了存储所给数据之外，还需要存储一个结点指针用于指向下一个结点。
②哈希表的开散列实现方式，在插入数据时也需要根据负载因子判断是否需要增容，所以我们也应该时刻存储整个哈希表中的有效元素个数，当负载因子过大时就应该进行哈希表的增容。
(2)哈希表的插入
①插入步骤
- 查看哈希表中是否存在该键值的键值对，若已存在则插入失败。
- 判断是否需要调整哈希表的大小，若哈希表的大小为0，或负载因子过大都需要对哈希表的大小进行调整。
- 将键值对插入哈希表。
- 哈希表中的有效元素个数 ++。
②哈希表的调整方式如下：
- 若哈希表的大小为0，则将哈希表的初始大小设置为10。(可更改)
- 若哈希表的负载因子已经等于1了，则先创建一个新的哈希表，该哈希表的大小为原哈希表的两倍，之后遍历原哈希表，将原哈希表中的数据插入到新哈希表，最后将原哈希表与新哈希表交换即可。
③补充
- 重点： 在将原哈希表的数据插入到新哈希表的过程中，不要通过复用插入函数将原哈希表中的数据插入到新哈希表，因为在这个过程中我们需要创建相同数据的结点插入到新哈希表，在插入完毕后还需要将原哈希表中的结点进行释放，多此一举。
- 实际上，我们只需要遍历原哈希表的每个哈希桶，通过哈希函数将每个哈希桶中的结点重新找到对应位置插入到新哈希表即可，不用进行结点的创建与释放。
④代码
将键值对插入哈希表的具体步骤如下：
- 通过哈希函数计算出对应的哈希地址。
- 若产生哈希冲突，则直接将该结点头插到对应单链表即可。
(3)哈希表的查找
- 先判断哈希表的大小是否为0，若为0则查找失败。
- 通过哈希函数计算出对应的哈希地址。
- 通过哈希地址找到对应的哈希桶中的单链表，遍历单链表进行查找即可。
(4)哈希表删除
- 通过哈希函数计算出对应的哈希桶编号。
- 遍历对应的哈希桶，寻找待删除结点。
- 若找到了待删除结点，则将该结点从单链表中移除并释放。
- 删除结点后，将哈希表中的有效元素个数 - -
注意 : 不要先调用查找函数判断待删除结点是否存在，这样做如果待删除不在哈希表中那还好，但如果待删除结点在哈希表，那我们还需要重新在哈希表中找到该结点并删除，还不如一开始就直接在哈希表中找，找到了就删除。(如果该元素在单链表中间，我们需要知道它的上个节点，删除该元素之后需要重新连接起来)
表的大小是素数更不容易冲突，是有数学理论在里面的
- 我们如果每次增容时让哈希表的大小增大两倍，那么增容后哈希表的大小就不是素数了。因此我们可以将需要用到的素数序列提前用一个数组存储起来，当我们需要增容时就从该数组当中进行获取就行了。
- 下面这些都是素数，且它们近似以2倍的形式进行增长，我们就可以将它们用一个数组存储起来
- 我们需要增容时，就在该素数数组中找到下一个素数作为哈希表增容后的大小即可。