哈希表详解

雨点打透心脏的1/2处 2024-04-03 12:52 95阅读 0赞

#### 文章目录 ####

*  哈希表
 *   *  什么是哈希表
     *  核心思想
     *  哈希表原理解析
     *   *  java代码示例
         *   *  Hash表插入
     *  什么是哈希函数
     *  什么是映射？
     *  哈希冲突处理
     *  参考链接：

## 哈希表 ##

### 什么是哈希表 ###

哈希表：也叫做**散列表**。是《数据结构与算法》中的学术用语。

它是**根据关键字和值（Key-Value）**直接进行访问的数据结构。也就是说，它通过关键字 key 和一个映射函数 Hash(key) 计算出对应的值 value，然后把键值对映射到表中一个位置来访问记录，以加快查找的速度。

这个映射函数叫做**哈希函数（散列函数）**，用于存放记录的数组叫做 哈希表（散列表）。 哈希表的关键思想是使用哈希函数，将键 key 和值 value 映射到对应表的某个区块中。

### 核心思想 ###

哈希表算法思想分为两个部分：

*  **插入**：向哈希表中插入一个关键字，哈希函数决定该关键字的对应值应该存放到表中的哪个区块，并将对应值存放到该区块中
 *  **查询**：在哈希表中搜索一个关键字，使用相同的哈希函数从哈希表中查找对应的区块，并在特定的区块搜索该关键字对应的值

### 哈希表原理解析 ###

哈希表的本质是`数组`加`哈希函数`。

在哈希表中，它的作用就是`将哈希表的某个key作为输入，然后经过一系列的运算后，得到数组的某个索引`。

一种很朴素的思路是，先用key计算出一个很大的数，然后对数组长度取模，从而得到索引，这只是众多方法中的一种，其他的比如：直接寻址法，平方取中法等。

得到索引后就可以通过索引对数组执行`插入或查找`的操作，因为`本质上是通过索引来访问数组`，所以哈希表的插入和查找的效率非常高，时间复杂度都是O(1)。  
![在这里插入图片描述][8f64ef5d67c54c4d938b7726c61bb06c.png]

#### java代码示例 ####

##### Hash表插入 #####

public static void main(String[] args) {
        
            Map<Integer,String> map = new HashMap<>();	//创建HashMap实例
            map.put(1,"张三");	//向Hash表插入一条数据：key=1,value=张三
            map.put(2,"李四");	//向Hash表插入一条数据：key=2,value=李四
            map.put(3,"王五");	//向Hash表插入一条数据：key=3,value=王五
     }

创建HashMap实例，并往Hash表里面插入三条数据，实现原理如下图：

1.  向Hash表插入一条数据：key=1,value=张三，经过Hash函数运算后，存入到数组下标为0的区域
2.  向Hash表插入一条数据：key=2,value=李四，经过Hash函数运算后，存入到数组下标为1的区域
3.  向Hash表插入一条数据：key=3,value=王五，经过Hash函数运算后，存入到数组下标为2的区域

![在这里插入图片描述][f9f932e038c14ec5b528f75d0a0bf6e9.png]

查询的原理同上，不做过多描述。

### 什么是哈希函数 ###

哈希函数：将哈希表中元素的关键键值映射为元素存储位置的函数。一般来说，哈希函数会满足以下几个条件：

*  易于计算，并且尽量使`计算出来的索引值均匀分布`，以此减少哈希冲突
 *  哈希函数计算得到的`哈希值是一个固定长度的输出值`
 *  如果 Hash(key1) 不等于 Hash(key2)，那么 key1、key2 一定不相等
 *  如果 Hash(key1) 等于 Hash(key2)，那么 key1、key2 可能相等，也可能不相等（会发生哈希碰撞）

在实际应用中，key值除了数字类型，还有可能是字符串类型、浮点数类型、大整数类型，甚至还有可能是几种类型的组合。

一般会`将各种类型的关键字先转换为整数类型，再通过哈希函数，将其映射到哈希表中`。 而关于整数类型的关键字，通常用到的哈希函数方法有：`直接定址法、除留余数法、平方取中法、基数转换法、数字分析法、折叠法、随机数法、乘积法、点积法`等。

***注意：特别的，当Key值是一个JavaBean时，应当如何处理？***

### 什么是映射？ ###

映射属于数学的范畴。在高中数学中，映射定义为：

两个元素的集之间元素相互“对应”的关系，为名词。映射，或者射影，在数学及相关的领域经常等同于函数。

举一个最简单的例子，一次函数：***y = x +1***，x属于自然数集A，y属于自然数集B。当 `x=1,y=2；x=2,y=3；x=3,y=4`。在A集合中随便找出一个值x，在B集合中都有一个y值与其对应。这就是映射。

如下图：  
![在这里插入图片描述][9a331eec6f6c42fd812d763c28ede48f.png]

### 哈希冲突处理 ###

哈希冲突：不同的关键字通过同一个哈希函数可能得到同一哈希地址，即 key1 ≠ key2，而 Hash(key1) = Hash(key2)，这种现象称为哈希冲突。

### 参考链接： ###

*  [java的Map接口常用的方法][java_Map]
 *  [java集合学习笔记][java]
 *  [Map集合遍历方法][Map]
 *  [java解决Hash冲突][java_Hash]

[8f64ef5d67c54c4d938b7726c61bb06c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/9f687b40c8c54a0dada6e05d7f1821ca.png
[f9f932e038c14ec5b528f75d0a0bf6e9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/12aeca764a1c461c91a5e0847acbd879.png
[9a331eec6f6c42fd812d763c28ede48f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/1656fbc53b21471892e558c6809dace1.png
[java_Map]: https://blog.csdn.net/m0_58680865/article/details/124963560
[java]: https://blog.csdn.net/m0_58680865/article/details/124803192
[Map]: https://blog.csdn.net/liaomingwu/article/details/118333917
[java_Hash]: https://blog.csdn.net/u010843421/article/details/81181280