HashMap 原理详解

女爷i 2023-06-30 04:18 9阅读 0赞

#### 一、HashMap的原理详解 ####

首先我们要知道什么是哈希表以及它的结构。在介绍哈希表之前我们需要了解并且掌握数组、链表以及红黑树的结构以及特点。

**1、我们先来看一下HashMap的使用**

public class Test { 
    	public static void main(String[] args) { 
    	
    		HashMap<String, Object> maps = new HashMap<>();
    		maps.put("name","zhao");
    		maps.put("age", 20);
    		maps.put("weight", "54KG");
    		maps.put("height", "174cm");
    		
    		System.out.println(maps.get("name"));
    		System.out.println(maps.get("age"));
    		
    	}
    }

控制台输出：  
![在这里插入图片描述][20200404203954787.png]  
从中我们可以看出来，我们可以根据name得到zhao，根据age 可以得到20。这其实就是HashMap里面的**key**和**value**，我们可以根据key得到value。

###### 2、对HashMap中的存和取操作的原理分析 ######

> HashMap在不同的语言中的定义稍有不同，在java中，HashMap在JDK1.8之前的实现方式 **数组+链表**,但是在JDK1.8后对HashMap进行了 底层优化,改为了由 **数组+链表+红黑树** 实现,主要的目的是提高查找效率。在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下（后面会探讨下哈希冲突的情况），仅需一次定位即可完成，时间复杂度为O(1)

那我们需要知道在java中为什么要用数组和链表实现，以及在jdk1.8之后为什么要加上红黑树？  
**（1）、在jdk1.8之前：**

哈希表的原理结构如图所示：  
( 数组中记录的是链表头结点的地址）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTIyMTEz_size_16_color_FFFFFF_t_70]

###### 1）、存储过程分析(key，value都存在链表中) ######

> 首先我们来解释一下如何将数据存到HashMap中：  
> maps.put(“name”,“zhao”);  
> **数组加链表，数组里存的是对应链表头部结点的地址。通过拉链法存储数据到链表中。**  
> 在这里我们需要知道什么是**散列**、**散列函数** 和 **HashCode（哈希值）**

> 在存储的时候，将所有要存取的数据通过一个函数转为相对应的一个值，这些值是无序的、杂乱无章的，然后将转化后的一堆值比较平均的放在数组每个索引后的链表里面，这个过程就是散列；这个函数就是散列函数；转化后的值就是HashCode值。  
> **引入散列的原因** 就是避免出现数据倾斜的情况，也就是100个数据，一个数组索引后面的链表占据了90个，这就是数据倾斜，导致查询速度大大降低，所以说这是不合适的，因此引入了散列。

存储原理图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTIyMTEz_size_16_color_FFFFFF_t_70 1]  
对于一堆数据，我们会给出具体的算法（散列函数）来确定某个元素具体放在哪个数组下标的后面，因此我们一定要确定好这个算法，否则会产生数据倾斜的现象。

**还有一点需要注意(重新哈希)：**

> 在存的过程中，链表的长度是有限制的，在没有达到临界点的时候，存储的时间复杂度为O(1)；但当达到临界点的时候，他要进行重新哈希，这时候存储的时间复杂度变为O(n)。

###### 2）读取分析 ######

maps.get("name")

> 在读取的时候我们是根据key去获取value值，只要确定了key散列以后的哈希值，那么我们就可以找到它对应的value值。  
> 假如我们想得到name对应的value值，首先在读取的过程中先将name通过散列函数得到散列值，根据散列值判断他在那个数组索引下标，找到数组索引下标后去遍历索引后的链表，找到对应的hashcode，进而获得value值。

读取原理图分析：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTIyMTEz_size_16_color_FFFFFF_t_70 2]

**（2）、在jdk1.8之后：**

java语言在jdk1.8之后对于HashMap进行优化，加上了红黑树，那么为什么要加上红黑树呢，其他二叉树结构不可以吗？之前的结构有什么缺点，加上红黑树以后做了哪些优化？我们下面来分析一下：

> 在1.8之前，在存储数据的时候我们规定了链表的长度不能超过多少，如果超过了这个值的话，增加数组的长度，重新进行哈希（rehash），如果要是这样的话，会大大增加时间复杂度(为O(n))，所以这样是不合适，因此我们引入了 红黑树 的结构。那为什么不引用AVL树呢，关键在于红黑树的局部平衡，而其他的二叉树可能会退化为链表，所以说也是不合适的。  
> 根据散列函数我们将数据依次放入到哈希表中，在java中规定当某一链表的字节数大于8并且数组长度大于等于64的时候，我们便采用`红黑树`进行存储，时间复杂度为O(logN)，这样大大减少了查找时间。(如下图所示)  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTIyMTEz_size_16_color_FFFFFF_t_70 3]

#### 二、HashMap的注意事项 ####

1.  **线程不安全**（没有加**锁**）;
2.  **HashMap用于场景：读多写少的情况下使用（一次写入，剩下为读）；HashMap经常用于读取和数据匹配的情况下。**
3.  **在进行数据匹配的情况下，整体时间复杂度为O(n)，因为单次查找为O(1)，循环n次，所以为O(n)。**
4.  **如果遇到key一样存储的时候HashMap会把value值覆盖。这时候有一种跟HashMap一样的结构Set，Set只有一个值，即Set< Integer >，并且在使用的时候不能为空，它在存储数据的时候，会先对这些数据进行去重的操作以及判断有没有这个数。**

[20200404203954787.png]: https://img-blog.csdnimg.cn/20200404203954787.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTIyMTEz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200114231551535.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTIyMTEz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTIyMTEz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200404212552459.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTIyMTEz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTIyMTEz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200404213435247.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTIyMTEz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTIyMTEz_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200114232953962.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTIyMTEz,size_16,color_FFFFFF,t_70