参考：
图文并茂详解数据结构之哈希表 - 知乎 (zhihu.com)
数据结构之哈希表以及常用哈希的算法表达（含全部代码）_哈希表代码-CSDN博客
数据结构(哈希表)_哈希函数需要指定哈希表大小吗-CSDN博客
果要存储一组数据，我们都能想到使用数组或者链表来存储，但是实际生产生活中，数据都是非常庞大的，动辄几十G，几十T，甚至以P来计算。这样一来，数组和链表的优势以劣势就非常明显了。
既然这两种方法都不能完美解决实际问题，那就一定会有一种方法的诞生来处理它，我们的哈希表就这样诞生啦，哈希表集这两种存储形式的优点于一身，接下来就让我们走进哈希表吧。
哈希表简介
哈希存储是一种利用哈希表来实现的数据结构。
具体是什么样的思路呢？
我们知道，键值对就是一一对应的关系，我们根据键（一般都是字符串）去找到对应的值，不能找错。
通常，我们会将“键”输入到哈希函数中，这样就能得到一个唯一的输出，那么，我们可以怎么来好好利用这个输出的唯一性呢？在一种思路中，我们可以将键通过哈希函数映射成不会重复的序号，这些序号可以对应数组的下标，之后，就可以将“键”对应的数据“值”存放在对应下标的数组中。通过这种方式，就可以保证键和值的一一对应。
举个例子，假如我们要存储一个人的若干信息到非关系型数据库中
name:"zhangsan"
gender:"male"
age:20
存储的时候，上层调用肯定是要输入键和值两个参数，里面具体是怎么存进数据库的呢？
里面会有个哈希函数，然后另外有个专门用来存储数据的数组arr。
接下来，执行如下步骤：
name输入到哈希函数，得到一个值比如0，我们将“zhangsan”这个值放到arr[0]中；
gender输入到哈希函数，得到一个值比如2，我们将"male"这个值放到arr[2]中；
name输入到哈希函数，得到一个值比如5，我们将20这个值放到arr[5]中；
这里只是个示例，实际实现肯定要考虑到数据类型和内存分配等问题。
取的时候怎么取呢？肯定是上层输入键，然后得到值，里面具体怎么实现的呢？
里面还是先将键输入到哈希函数，然后就会得到一个确定的值，也就是对应着数组的下标，接着去数组对应的下标位置去取数据，再返回给上层调用。
这就是哈希存储的大体思路。接下来我们就来看看到底什么是哈希存储。
所以说，任何机制都难以脱离具体的应用场景来看待，又或者说，是因为某些特殊场景的需求才产生了各种各样的机制。
所以，到底什么是哈希存储呢？
参考：【索引存储方式和散列存储方式】_索引存储和散列存储的区别-CSDN博客
散列存储方式（Hashing）
散列存储方式是一种通过哈希函数将数据映射到固定位置的存储方式。散列技术通过将数据映射到一个固定大小的数组（哈希表）中，从而实现快速查找、插入和删除操作。散列的基本原理
散列存储方式依赖于哈希函数，它将数据的键值（如字符串、整数等）映射到一个数组的索引位置。哈希函数根据键值计算出一个整数（哈希值），这个哈希值用于确定数据在哈希表中的存储位置。哈希表（Hash Table）：是存储数据的数组，其大小通常是固定的。每个数据项通过哈希函数计算得到的索引位置来存储。
哈希值：是通过哈希函数将输入数据映射到数组中的位置值。哈希存储的类型
开放地址法：
开放地址法是一种解决哈希冲突的方法，当两个数据项的哈希值相同（即发生哈希冲突）时，通过探查（如线性探查、二次探查、双重散列等）来寻找下一个空位存放冲突的数据项。
链地址法（Separate Chaining）：
链地址法是另一种处理哈希冲突的方法。当发生冲突时，哈希表的每个位置会维护一个链表，将多个哈希值相同的数据项存储在链表中。
每个哈希表的桶（或槽）是一个链表，链表中的每个节点存储数据项。
哈希桶：
哈希桶是指哈希表中的每个槽，用于存储哈希值相同的多个元素。桶的大小是动态可调的，可以通过调整哈希表的大小来保持负载因子（存储元素数量与表大小的比率）的平衡。
哈希存储的优点与缺点
优点：
查找效率高：哈希存储方式可以在常数时间内完成数据查找、插入和删除（假设哈希函数和哈希表设计得当）。
处理海量数据：通过哈希函数，散列存储方式能够在大规模数据中快速定位目标数据。
缺点：
哈希冲突：当多个键值经过哈希函数映射到相同的哈希值时，会发生哈希冲突，冲突会影响查询和插入效率。虽然有开放地址法和链地址法等解决方法，但会增加计算复杂度。
不适合范围查询：与索引不同，散列存储方式不适合进行范围查询，因为哈希值是随机的，无法按顺序访问数据。
负载因子问题：哈希表的负载因子（即表的填充程度）会影响性能。负载因子过高会导致频繁的冲突，负载因子过低则浪费空间。
下面具体展开说明。
哈希表也叫散列表，哈希表是一种数据结构，它提供了快速的插入操作和查找操作，无论哈希表总中有多少条数据，插入和查找的时间复杂度都是为O(1)，因为哈希表的查找速度非常快，所以在很多程序中都有使用哈希表，例如拼音检查器。
哈希表也有自己的缺点，哈希表是基于数组的，我们知道数组创建后扩容成本比较高，所以当哈希表被填满时，性能下降的比较严重。
哈希表采用的是一种转换思想，其中一个中要的概念是如何将「键」或者「关键字」转换成数组下标？在哈希表中，这个过程有哈希函数来完成，但是并不是每个「键」或者「关键字」都需要通过哈希函数来将其转换成数组下标，有些「键」或者「关键字」可以直接作为数组的下标。我们先来通过一个例子来理解这句话。
我们上学的时候，大家都会有一个学号「1-n号」中的一个号码，如果我们用哈希表来存放班级里面学生信息的话，我们利用学号作为「键」或者「关键字」，这个「键」或者「关键字」就可以直接作为数据的下标，不需要通过哈希函数进行转化。如果我们需要安装学生姓名作为「键」或者「关键字」，这时候我们就需要哈希函数来帮我们转换成数组的下标。
哈希函数
哈希函数的作用是帮我们把非int的「键」或者「关键字」转化成int，可以用来做数组的下标。比如我们上面说的将学生的姓名作为「键」或者「关键字」，这是就需要哈希函数来完成，下图是哈希函数的转换示意图。
哈希函数的写法有很多中，我们来看看「HashMap」中的哈希函数
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }「HashMap」中利用了「hashCode」来完成这个转换。哈希函数不管怎么实现，都应该满足下面三个基本条件：
- 散列函数计算得到的散列值是一个非负整数
- 如果 key1 = key2，那 hash(key1) == hash(key2)
- 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)
第一点：因为数组的下标是从0开始，所以哈希函数生成的哈希值也应该是非负数
第二点：同一个key生成的哈希值应该是一样的，因为我们需要通过key查找哈希表中的数据
第三点：看起来非常合理，但是两个不一样的值通过哈希函数之后可能才生相同的值，因为我们把巨大的空间转出成较小的数组空间时，不能保证每个数字都映射到数组空白处。所以这里就会才生冲突，在哈希表中我们称之为哈希冲突。
哈希冲突是不可避免的，我们常用解决哈希冲突的方法有两种「开放地址法」和「链表法」，具体参考开头的链接文章。
在哈希表中执行插入和搜索操作都可以达到O(1)的时间复杂度，在没有哈希冲突的情况下，只需要使用一次哈希函数就可以插入一个新数据项或者查找到一个已经存在的数据项。
如果发生哈希冲突，插入和查找的时间跟探测长度成正比关系，探测长度取决于装载因子，装载因子是用来表示空位的多少。
装载因子的计算公式：
❝ 装载因子 = 表中已存的元素 / 表的长度
❞装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。
哈希算法形式
常见的哈希算法形式有，根据键值进行加法运算，减法运算，乘法运算，位移运算。
值得一说的是位移运算，无论是前移还是后移， 都会使键值转换出来的哈希值大小难以确定，可能有键值很大，但是哈希值很小的情况，这就让使用者无法大致确定键值对应的哈希值。但这并不是缺点，看实际生产要求。
而一般都是以上几种运算的复合运算作为哈希算法。例如;
hashvalue = (hashvalue << 4) + hashvalue + *key++;//hashvalue为哈希值，key为键值更多待补充。
哈希冲突的处理
哈希冲突即为不同键值通过哈希算法得到了相同的哈希值，这种情况，我们肯定不能将数据直接存储到对应的地址去，这样会将原来的数据覆盖。对此常见的 方法有一下三种，我们最推荐使用链表的方式。
线性探测法
在线性探测哈希表中，数据的插入是线性的查找空白单元，例如我们将数88经过哈希函数后得到的数组下标是16，但是在数组下标为16的地方已经存在元素，那么就找17,17还存在元素就找18，一直往下找，直到找到空白地方存放元素。再哈希法
双哈希是为了消除原始聚集和二次聚集问题，线性探测每次的探测步长都是固定的。双哈希是除了第一个哈希函数外再增加一个哈希函数用来根据关键字生成探测步长，这样即使第一个哈希函数映射到了数组的同一下标，但是探测步长不一样，这样就能够解决聚集的问题。第二个哈希函数必须具备如下特点
- 和第一个哈希函数不一样
- 不能输出为0，因为步长为0，每次探测都是指向同一个位置，将进入死循环，经过试验得出stepSize = constant-(key%constant);形式的哈希函数效果非常好，constant是一个质数并且小于数组容量
链表法
通过在哈希表中再寻找一个空位解决冲突的问题，还有一种更加常用的办法是使用「链表法」来解决哈希冲突。「链表法」相对简单很多，「链表法」是每个数组对应一条链表。当某项关键字通过哈希后落到哈希表中的某个位置，把该条数据添加到链表中，其他同样映射到这个位置的数据项也只需要添加到链表中，并不需要在原始数组中寻找空位来存储。
和索引存储的对比
索引存储方式和散列存储方式对比
索引存储方式和散列存储方式都是为了优化数据的查找效率，但它们的实现原理和应用场景有所不同。索引存储和哈希存储听起来有点像，要注意区分，一个很明显的区别就是，索引存储需要维护索引表，但是哈希存储是通过哈希函数来实时计算出哈希值，不需要维护索引表。下面是二者的一些区别，可以先看看：
索引存储和散列存储都是数据存储结构，它们在存储方式、存取效率以及冲突处理等方面存在区别。以下是具体分析：
存储方式
●索引存储：索引存储是一种间接存储方式，数据元素存储在数据区中，而索引则存储在索引表中。索引表中的每个索引项包含一个关键字和一个指向数据区的指针，用于快速定位数据元素。比如，中断向量表就是一种索引存储方式，它包含一系列指向中断处理程序的指针。当发生中断时，处理器会根据中断类型在中断向量表中查找相应的指针，然后跳转到该指针指向的内存地址，执行中断处理程序。
●散列存储：散列存储是一种直接存储方式，数据元素存储在散列表中，散列表中的每个位置称为一个槽，每个槽中可以存储一个数据元素。散列函数将关键字映射到散列表中的槽，用于快速查找数据元素。
存取效率
●索引存储：索引存储的存取效率较高，因为可以通过索引表中的关键字快速定位到数据元素。
●散列存储：散列存储的存取效率也很高，因为可以通过散列函数快速定位到数据元素。
冲突处理
●索引存储：索引存储中的冲突处理一般采用链式法，即将哈希值相同的数据元素存储在同一条链表中。
●散列存储：散列存储中的冲突处理一般采用开放地址法，即将哈希值相同的数据元素存储在散列表的其他位置中。
存储空间
●索引存储：索引存储需要额外的索引表来存储索引，因此需要更多的存储空间。
●散列存储：散列存储不需要额外的索引表，只需要散列表和散列函数即可，因此需要较少的存储空间。
适用场景
●索引存储：适用于静态数据集合，数据集合更新较少的情况。例如，数据库中的索引。
●散列存储：适用于动态数据集合，数据集合更新较频繁的情况。例如，哈希表和查找表。
总的来说，索引存储和散列存储各有优缺点，适用于不同的应用场景。在选择时，应根据数据的特性和访问模式来决定使用哪种存储结构。
总结
索引存储方式：适用于需要快速查找、范围查询和顺序访问的数据。索引通过建立层次化的索引结构（如B树、B+树、倒排索引等）来加速查询，适合大规模的复杂查询场景。
散列存储方式：适用于快速查找、插入和删除操作，尤其在点查找时表现优秀。散列存储方式通过哈希函数将数据映射到固定位置，能够在常数时间内完成查找，但不适合范围查询和排序操作。
