首页 / JAVA  

HashMap底层原理解析

HashMap概述
      在JDK1.8之前,HashMap采用数组+链表实现,即使用链表处理冲突,也就是说同一hash值的节点都存储在哈希数组同一下标下的一个链表里。但是当一个链表太长(元素较多)时,即hash值相等的元素较多时,通过key值依次查找的效率较低。而JDK1.8中,HashMap采用数组+链表+红黑树实现,当链表长度超过阈值(8)时,将链表转换为红黑树,这样大大减少了查找时间。

下图中代表jdk1.8之前的hashmap结构,左边部分即代表哈希数组,数组的每个元素都是链表中的一个节点,链表是用来解决冲突的,也就是说不同的key可能hash(key)的值相同,即它们在哈希数组中的下标相同,就将其放入单链表中。


jdk1.8之前的hashmap都采用上图的结构,都是基于一个数组和多个单链表,hash值冲突的时候,就将对应节点以链表的形式存储。如果在一个链表中查找其中一个节点时,将会花费O(n)的查找时间,会有很大的性能损失。到了jdk1.8,当同一个链表的节点数大于等于8时,不再采用单链表形式存储,而是采用红黑树,如下图所示。


说明:上图很形象的展示了HashMap的数据结构(数组+链表+红黑树),桶中的结构可能是链表,也可能是红黑树,红黑树的引入是为了提高效率。

HashMap的存储原理:首先每个元素(key,value)都是哈希数组下标中链表的一个节点,当添加一个元素(key-value)时,就首先计算元素key的hash值,以此确定插入数组中的索引位置,但是可能由于hash值相同,某个数组下标中已经有其它节点数据了,这时就添加到同一hash值的元素的后面,他们在数组的同一位置,这样就形成了链表,所以说数组存放的是链表。而当链表长度太长时(大于等于8)时,链表就转换为红黑树,这样大大提高了查找的效率。

HashMap 的源码分析

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
//所能容纳的key-value对极限
int threshold;
//负载因子
final float loadFactor;
//记录修改次数
int modCount;
//实际存在的键值对数量
int size;
//哈希桶数组
transient Node<K,V>[] table;
}

主要有 5 个关键参数:

threshold:表示容器所能容纳的 key-value 对极限。

loadFactor:负载因子。

modCount:记录修改次数。

size:表示实际存在的键值对数量。

table:一个哈希桶数组,键值对就存放在里面。


接着来看看Node这个类,Node是HashMap的一个内部类,实现了Map.Entry接口,本质是就是一个映射(键值对)

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;//hash值
        final K key;//k键
        V value;//value值
        Node<K,V> next;//链表中下一个元素
}

在 HashMap 的数据结构中,有两个参数可以影响 HashMap 的性能:

初始容量(inital capacity)和负载因子(load factor)。

初始容量(inital capacity)是指 table 的初始长度 length(默认值是 16);

负载因子(load factor)用指自动扩容的临界值(默认值是 0.75);


threshold是HashMap所能容纳的最大数据量的Node(键值对)个数,计算公式threshold = capacity * Load factor。

当 Node的数量超过capacity*load_factor时,容器将自动扩容并重新哈希,扩容后的HashMap容量是之前容量的两倍,所以数组的长度总是 2 的 n 次方。


初始容量和负载因子也可以修改,具体实现方式,可以在对象初始化的时候,指定参数,比如:

Map map = new HashMap(int initialCapacity, float loadFactor);

但是,默认的负载因子 0.75 是对空间和时间效率的一个平衡选择,建议大家不要修改,除非在时间和空间比较特殊的情况下,如果内存空间很多而又对时间效率要求很高,可以降低负载因子 Load factor 的值;相反,如果内存空间紧张而对时间效率要求不高,可以增加负载因子 loadFactor 的值,这个值可以大于 1。同时,对于插入元素较多的场景,可以将初始容量设大,减少重新哈希的次数。


HashMap 的内部功能实现有很多,本文主要从以下几点,进行逐步分析。

通过 K 获取数组下标;

put 方法的详细执行;

resize 扩容过程;

get 方法获取参数值;

remove 删除元素;


通过 K 获取数组下标

不管增加、删除还是查找键值对,定位到数组的位置都是很关键的第一步,打开 hashMap 的任意一个增加、删除、查找方法,从源码可以看出,通过key(我们保存数据的(key,value)中的key)获取数组下标,主要做了 3 步操作,其中length指的是容器数组的大小。

/**获取hash值方法*/
static final int hash(Object key) {
     int h;
     // h = key.hashCode() 为第一步 取hashCode值(jdk1.7)
     // h ^ (h >>> 16)  为第二步 高位参与运算(jdk1.7)
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//jdk1.8
}
/**获取数组下标方法*/
static int indexFor(int h, int length) {
//jdk1.7的源码,jdk1.8没有这个方法,但是实现原理一样的
     return h & (length-1);  //第三步 取模运算
}

put 方法的详细执行



1、判断键值对数组 哈希table是否为空或为 null,否则执行 resize()进行扩容;

2、根据键值 key 计算 hash 值得到插入的数组索引 i,如果 table[i]==null,直接新建节点添加;

3、当 table[i]不为空,判断 table[i]的首个元素是否和传入的 key 一样,如果相同直接覆盖 value;

4、判断 table[i] 是否为 treeNode(红黑树),如果是红黑树,则直接在树中插入键值对;

5、遍历 table[i],判断链表长度是否大于 8,大于 8 的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现 key 已经存在直接覆盖 value 即可;

6、插入成功后,判断实际存在的键值对数量 size 是否超多了最大容量 threshold,如果超过,进行扩容操作;


resize方法

①.在jdk1.8中,resize方法是在hashmap中的键值对大于阀值时或者初始化时,就调用resize方法进行扩容;

②.每次扩展的时候,都是扩展2倍;

③.扩展后Node对象的位置要么在原位置,要么移动到原偏移量两倍的位置。


get 方法获取参数值

get(Object key)方法根据指定的 key 值返回对应的 value,getNode(hash(key), key))得到相应的 Node 对象 e,然后返回 e.value。因此 getNode()是算法的核心。



get 方法,首先通过 hash()函数得到对应数组下标,然后依次判断。

1、判断第一个元素与 key 是否匹配,如果匹配就返回参数值;

2、判断链表是否红黑树,如果是红黑树,就进入红黑树方法获取参数值;

3、如果不是红黑树结构,直接循环判断,直到获取参数为止;


remove 删除元素

remove(Object key)的作用是删除 key 值对应的 Node,该方法的具体逻辑是在removeNode(hash(key), key, null, false, true)里实现的。


jdk1.8 的删除逻辑实现比较复杂,相比 jdk1.7 而言,多了红黑树节点删除和调整:

1、默认判断链表第一个元素是否是要删除的元素;

2、如果第一个不是,就继续判断当前冲突链表是否是红黑树,如果是,就进入红黑树里面去找;

3、如果当前冲突链表不是红黑树,就直接在链表中循环判断,直到找到为止;

4、将找到的节点,删除掉,如果是红黑树结构,会进行颜色转换、左旋、右旋调整,直到满足红黑树特性为止;


总结

1、如果 key 是一个对象,记得在对象实体类里面,要重写 equals 和 hashCode 方法,不然在查询的时候,无法通过对象 key 来获取参数值!

2、相比 JDK1.7,JDK1.8 引入红黑树设计,当链表长度大于 8 的时候,链表会转化为红黑树结构,发生冲突的链表如果很长,红黑树的实现很大程度优化了 HashMap 的性能,使查询效率比 JDK1.7 要快一倍!

3、对于大数组的情况,可以提前给 Map 初始化一个容量,避免在插入的时候,频繁的扩容,因为扩容本身就比较消耗性能!


线程不安全的HashMap

    因为多线程环境下,使用Hashmap进行put操作会引起死循环,导致CPU利用率接近100%,所以在并发情况下不能使用HashMap。

2019-10-24