哈希表介绍和实现
目录
开篇
一. 什么是哈希表
二. 解决哈希冲突
1. 开放寻址法
2. 拉链法
三. 哈希表数据的读取
开篇
数组是我们所熟知并广泛使用的重要的数据结构**，那么它有哪些优势呢？
人们普遍认识到，在我们掌握数组中某元素的索引值时（或说是已知某个元素的位置），能够快速定位该元素的方法非常高效（或说是快捷有效）。
然而，在这种情况下存在一定的缺陷：如果我们无法识别某个特定元素在数组中的具体索引位置，则仅仅知道该元素存在于数组中也无法直接获取它。此时我们唯一的选择就是执行线性查找——依次遍历每一个元素——直到找到目标为止。这种方法虽然简单直观但存在显著缺陷：当处理一个包含1万项的长数组时所需的时间将会大幅增加（假设目标项恰好位于第9999个位置），此时就需要遍历整个数组才能找到目标项。在这种极端情况下所需的时间成本已经变得难以接受
为了克服数组在数据存储方面的局限性，在本节中我们介绍了哈希表技术作为解决方案的核心概念，并将其广泛应用于各种编程语言的基础实现中。
一. 什么是哈希表
哈希表（Hash table; Hash Map），又称散列表（Dictionary），是一种基于键值计算得出对应的位置并快速定位所需数据的数据结构。具体来说，
其核心原理是利用特定算法生成键值对应的地址，
从而实现高效的插入、查找和删除操作。
具体来说，
它通过计算一个关于键值的函数
确定存储位置并快速定位所需数据。
其核心算法称为哈希函数（Hash Function）。
一般来说啊，实现哈希表我们可以采用两种方法 ：1、数组+链表 2、数组+二叉树
两种方法其实都比较简单。实际上来说，在设计上无论是哪种方法都需要用到一个基础的数组结构。每个方法都需要用到一个基础的数组结构去扩展功能。比如说第一种方法采用的是数组加链表的形式，在这种情况下主要是用来解决哈希冲突问题的一种解决办法。通过链表来存储数据的方式能够有效地避免哈希冲突问题的存在，并且这种方式也被广泛地应用于构建哈希表的基础架构上。需要注意的是，在传统的数据存储中我们通常只会在单个元素中存储数据本身而在这种特殊的数据结构中则会将多个键值对整合在一起形成一个统一的整体存储空间。
举个例子来说吧，假设我现在给你一张电话本（即一个列表），上面存储了姓名及其对应的手机号信息。我想让您帮我查找一下王二的电话号码是多少。一般情况下，默认的做法是逐一排查（类似于使用for循环遍历整个数组），直到找到目标信息为止。然而，在这种情况下如果目标人物（即王二）位于电话本的末尾一页附近时，则会让前面查找的部分显得有些徒劳无功——有没有更高效的办法呢？
按照人名给个类的话, 比如说按照首字母来排序, 就像abc这样的顺序, 这样根据王二我就知道去找对应的w类信息, 这样就不费劲多了。
从姓名中提取出其首字母并对其进行排序。这是否相当于采用某种特定的方法来获取所需的结果？例如，在这里我们选取的是人名的首字母作为特征字段。将其应用于数学领域是否类似于一种映射关系？即接受输入数据并进行一系列运算以生成输出结果。哈希表中就叫做散列函数 ，其中规定的一些操作就叫做函数法则。
哈希表的数据存储机制是什么？ 请查看上面的图表说明，请记住我们已经知道哈希表本质上是一个数组结构，请问这个数组长度是8，请问我们需要如何将学生信息存储到这个哈希表中即这个数组中呢？具体来说就是把学生数据按照一定的规则填入到数组相应的位置上，在这里我们需要考虑如何实现这一过程才能确保数据能够高效地存取操作
这里的学号被视为一个关键码。我们已经了解了这一点。哈希表的作用是利用key值通过哈希函数计算得到一个对应的位置。该位置直接用于确定Entry在哈希表中的存储位置。实际上该位置即为数组的一个索引位置。
例如，在这里我们有一个学号值为101011。当对其应用哈希函数进行处理后得到的结果是1。这个数值则指示我们需要将此条目存储于数组中的某个特定位置。具体而言，则代表该数组元素的位置索引即为此数值所确定的整数值。即其对应的存储位置即为数组索引值为1的位置，请参考图示部分以获得更直观的理解
在之前的介绍中已经讲解过什么是Entry。因此，请注意以下几点：数组中的位置编号为' ̲̄̄ '处存放了一个特定的Entry。这个Entry不是一个单纯的数值而是包含了一个完整的键值对（key-value）。也就是说，在这里存储的是一个键值对（key-value），其中的关键字（key）是学号' ̲̄̄ '对应的value是' 张三 '。通过哈希函数计算得到的结果是位置编号为' ̲̄̄ '。
二. 解决哈希冲突
对于学号为102011的李四而言，在经过哈希函数计算后得到的结果是1，则同样需要将该学号放置到数组中的位置1处。然而此时该位置已经被张三占用，则面临这种情况即被称为哈希冲突问题或者也称为哈希碰撞现象。
解决哈希冲突 两种主要的方法，一个是开放寻址法 ，一个是拉链法 。
1. 开放寻址法
**
**
开放寻址法其实说起来很简单就是当一个位置被占用时 我们就需要另找一个可用的位置 为了寻找下一个可用的位置 这里具体实现的方式也很多 最简单的方式就是如果当前位置已经被占用 我们就会检查该位置的下一个位置是否可用 即检查1的位置是否被占用 如果2的位置也被占用了 那么我们就继续往下寻找 依次检查3的位置 以此类推 直到找到一个空闲的位置
2. 拉链法
**
**
之前说的开放寻址法采用的方式是在数组上另外找个新位置。
而拉链法则与之不同的是，在同一位置上出现了多个元素时该怎么办？这时我们采用链表结构来处理这个问题。具体来说，在这种情况下（如图所示），当多个元素（例如张三和李四）试图占据同一个初始位置时（即索引1），由于张三先到达并占据了该位置后就无法移动（即该Position已存在），那么李四该如何安置呢？解决这个问题的方法就是使用链表结构：此时对应的每一个Element不仅存储了当前的数据，并且还保存了一个指向下一个位置的next指针（即所谓的next指针）。这个next指针指向数组外的一个新空间（即内存地址），将李四安排到该新空间中；同时将张三所在的Element中的next指针也指向这个新的空间地址。如果后续仍然出现冲突的情况，则把又出现冲突的那个Element放置到一个新的空闲空间中，并将其对应的next指针指向新的空间地址；依此类推就可以形成一个完整的链表结构
三. 哈希表数据的读取
为了查询学号为H(学号)=位置的学生姓名，请问操作流程是怎样的？首先通过学号应用哈希函数计算得到存储位置索引值为H(学生ID)的结果即得到存储的位置索引值为H(学生ID)的位置。接着访问存储位置索引值为H(学生ID)处获取相关数据。拿到该记录之后检查该记录的关键字是否匹配我们的目标学生ID。结果发现记录的关键字是H(学生ID')=position'而非我们的目标学生ID。然后根据该记录的关键字next指向下一个存储位置。好成功找到李四
在哈希表设计中占据核心地位的是哈希函数，在其设计达到优秀水平时会降低冲突概率，在未达到最佳状态时则可能导致冲突并显著地影响性能。
文件参考:庆哥java
哈希表的具体代码实现：[c开源hash项目 uthash的用法总结]( "c开源hash项目 uthash的用法总结_whatday的专栏-博客_uthash)