HashMap的底层原理分析

水深无声 2022-12-15 11:17 227阅读 0赞

转自：https://zhuanlan.zhihu.com/p/79507868，稍作修改

HashMap是一个集合，键值对的集合,源码中每个节点用Node<K,V>表示

static class Node<K,V> implements Map.Entry<K,V> { 
       final int hash;
       final K key;
       V value;
       Node<K,V> next;
       // ...

Node是一个内部类，这里的key为键，value为值，next指向下一个元素，可以看出HashMap中的元素不是一个单纯的键值对，还包含下一个元素的引用，也就是链表。

总的来说，HashMap的数据结构为 数组+(链表或红黑树)，如图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE1MDAzNTA1_size_16_color_FFFFFF_t_70_pic_center]  
为什么采用这种结构来存储元素呢？

*  数组的特点：查询效率高，插入，删除效率低。
 *  链表的特点：查询效率低，插入删除效率高。  
    在HashMap底层使用数组加（链表或红黑树）的结构完美的解决了数组和链表的问题，使得查询和插入，删除的效率都很高。

## HashMap存储元素的过程 ##

有这样一段代码：

HashMap<String,String> map = new HashMap<String,String>();
    map.put("刘德华","张惠妹");
    map.put("张学友","大S");

现在我要把键值对 “刘德华”,”张惠妹”存入map：  
第一步：计算出键“刘德华”的hashcode，该值用来定位要将这个元素存放到数组中的什么位置。什么是hashcode？在Object类中有一个方法：`public native int hashCode();`  
该方法用native修饰，所以是一个本地方法，所谓本地方法就是非java代码，这个代码通常用c或c++写成，在java中可以去调用它。调用这个方法会生成一个int型的整数，我们叫它哈希码，哈希码和调用它的对象地址和内容有关。  
**哈希码的特点是：  
对于同一个对象如果没有被修改（使用equals比较返回true）那么无论何时它的hashcode值都是相同的，对于两个对象如果他们的equals返回false,那么他们的hashcode值也有可能相等。**

明白了hashcode我们再来看元素如何通过hashcode定位到要存储在数组的哪里，通过hashcode值和数组长度取模我们可以得到元素存储的下标。刘德华的hashcode为20977295 数组长度为 16则要存储在数组索引为 20977295%16=1的地方。  
![在这里插入图片描述][20201016103012488.jpg_pic_center]  
可以分两种情况：

1.  数组索引为1的地方是空的，这种情况很简单，直接将元素放进去就好了。
2.  已经有元素占据了索引为1的位置，这种情况下我们需要判断一下该位置的元素和当前元素是否相等，使用equals来比较。

如果使用默认的规则是比较两个对象的地址。也就是两者需要是同一个对象才相等，当然我们也可以重写equals方法来实现我们自己的比较规则最常见的是通过比较属性值来判断是否相等。如果两者相等则直接覆盖，如果不等则在原元素下面使用链表的结构存储该元素。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE1MDAzNTA1_size_16_color_FFFFFF_t_70_pic_center 1]  
每个元素节点都有一个next属性指向下一个节点，这里由数组结构变成了数组+链表结构,红黑树又是怎么回事呢？因为链表中元素太多的时候会影响查找效率，所以当链表的元素个数达到8的时候使用链表存储就转变成了使用红黑树存储，原因就是红黑树是平衡二叉树，在查找性能方面比链表要高。

## HashMap中的两个重要的参数 ##

HashMap中有两个重要的参数：初始容量大小和加载因子，初始容量大小是创建时给数组分配的容量大小，默认值为16，用数组容量大小乘以加载因子得到一个值，一旦数组中存储的元素个数超过该值就会调用rehash方法将数组容量增加到原来的两倍，专业术语叫做扩容。

在做扩容的时候会生成一个新的数组，原来的所有数据需要重新计算哈希码值重新分配到新的数组，所以扩容的操作非常消耗性能

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE1MDAzNTA1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/b35b5d519c464307a168bdbbe8a73470.png
[20201016103012488.jpg_pic_center]: /images/20221123/b3df1c3d1c844cb8a4e737533dc82b3c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE1MDAzNTA1_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/719bc39621b94d85a345ddb3974b29f8.png