HashMap源码分析

浮生一境 2019年12月05日 568次浏览

HashMap简介

基于哈希表实现,每一个元素key-value存储,内部实现是数据上挂载单链表,容量不足时(超过了阈值,阈值是通过负载因子计算的),会自动扩展(以2倍方式扩容)。

  1. 允许key value值为null
  1. 线程不安全
  1. 实现Serializable,支持序列化
  1. 实现了Cloneable,支持被克隆
  1. key-value方式存储
  1. 自动扩容,根据负载因子计算,为当前容量的2倍

HashMap源码解读

存储数据结构

如下图:(图是copy自网络,无法找到源头,只能先借用啦(^▽^)) hashMap源码解读

HashMap类结构

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

继承抽象类AbstractMap,实现了序列化Serializable接口,cloneable接口,Map接口
HashMap 重要的常量属性
  • 默认桶的大小
static final int DEFAULT_INITIAL_CAPACITY = 1 &lt;&lt; 4;
  • 默认桶的最大值
static final int MAXIMUM_CAPACITY = 1 &lt;&lt; 30;
  • 负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
  • 链表转成红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;
  • 红黑树转成链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
  • 由链表转换成红黑树的容量的最小阈值
static final int MIN_TREEIFY_CAPACITY = 64;
  • 扩容阈值
int threshold;
构造方法(一共有四种构造方法)
  • 默认构造(负载因子为默认大小)
public HashMap() {
	this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
  • 指定大小的,指定负载因子的构造方法
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity &lt; 0)
            throw new IllegalArgumentException(&quot;Illegal initial capacity: &quot; + initialCapacity);
        if (initialCapacity &gt; MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor &lt;= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException(&quot;Illegal load factor: &quot; + loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
  • 指定大小的构造方法(负载因子为默认)
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
  • 包含Map的构造方法
    public HashMap(Map&lt;? extends K, ? extends V&gt; m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
单链表的实现

每一个节点是一个Entry对象,每一个node节点都存储有key value,节点的hash值,以及下一个节点的node,实现Map.Entry接口。需要注意到node对象重写了equals方法,当出现hash冲突的时候会通过equals比较是否相同

    static class Node&lt;K,V&gt; implements Map.Entry&lt;K,V&gt; {
        final int hash;
        final K key;
        V value;
        Node&lt;K,V&gt; next;

        Node(int hash, K key, V value, Node&lt;K,V&gt; next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + &quot;=&quot; + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry&lt;?,?&gt; e = (Map.Entry&lt;?,?&gt;)o;
                if (Objects.equals(key, e.getKey()) &amp;&amp;
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }
计算hashMap容量

计算hashMap容量的大小,也就是桶的大小,说到这,先补充一下知识点

这里我们要知道&lt;&lt;运算符的意义,表示移位操作,每次向左移动一位(相对于二进制来说),表示乘以2,此处1&lt;&lt;4表示00001中的1向左移动了4位,变成了10000,换算成十进制就是2^4=16,也就是HashMap的默认容量就是16。Java中还有一些位操作符,比如类似的&gt;&gt;(右移),还有&gt;&gt;&gt;(无符号右移)等,也是需要我们掌握的。这些位操作符的计算速度很快,我们在平时的工作中可以使用它们来提升我们系统的性能。

初始化时,会首先判断初始容量是否小于0,如果小于0,会抛出异常。接着,判断初始容量是否大于最大的容量(即2^31),如果大于,将初始容量设置为最大初始容量。紧接着,判断加载因子:如果小于等于0,或者不是一个数字,都会抛出异常。等这些校验完成之后,会将HashMap的加载因子和扩容的阈值设置上。这里需要注意一下,threshold(阈值)=capacity*loadFactor。

    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n &gt;&gt;&gt; 1;
        n |= n &gt;&gt;&gt; 2;
        n |= n &gt;&gt;&gt; 4;
        n |= n &gt;&gt;&gt; 8;
        n |= n &gt;&gt;&gt; 16;
        return (n &lt; 0) ? 1 : (n &gt;= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

这个方法,是计算桶的大小,根据给定的cap,进行无符号右移,将移动的值与之前的值取非,如下计算逻辑: 例如输入30,求该桶的大小?

int cap = 29
int n = 28 = 29 - 1 

第一次            0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0
右移1位          0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0
计算结果        0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0
右移2位          0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
计算结果        0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
此时看结果已经都是1了,继续移位计算的结果也都是1,所以最终结果是31,如果n&gt;1,则返回31 + 1 = 32,为2的整数次幂。

总结,tableSizeFor方法只是为了让最高位后的值都为1,这样计算出的结果为输入数的最接近2的整数次幂。
求hash值和桶的索引值

接下来重点分析一下求hash值和桶的索引值,这俩个是HashMap最核心的地方,他可以保证哈希表中的元素均匀地散列。

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h &gt;&gt;&gt; 16);
    }

根据key计算hash值,只计算hash值的几位,使用位操作是计算效率很高。目前不去深究为什么这么设计,我们只要知道,这样设计的目的是为了让hash值分布的更加均匀即可。

求桶的索引值,是key的hash &(tab.length - 1)

有一种方法:除法散列法,用hash值对length取模来计算桶的索引,这种方法基本能保证元素在哈希表中散列的比较均匀,但取模会用到除法运算,效率很低。
hashMap 是使用h&amp;(length-1)的方法代替取模,同样实现了均匀的散列,但效率要高很多。

在上面的tableSizeFor方法,计算出的桶的大小是2的整数次幂,为什么桶的大小一定是2的整数次幂呢? 首先,length为2的整数次幂的话,h&(length-1)就相当于对length取模,这样便保证了散列的均匀,同时也提升了效率; 其次,length为2的整数次幂的话,为偶数,这样length-1为奇数,奇数的最后一位是1,这样便保证了h&(length-1)的最后一位可能为0,也可能为1(这取决于h的值),即与后的结果可能为偶数,也可能为奇数,这样便可以保证散列的均匀性,而如果length为奇数的话,很明显length-1为偶数,它的最后一位是0,这样h&(length-1)的最后一位肯定为0,即只能为偶数,这样任何hash值都只会被散列到数组的偶数下标位置上,这便浪费了近一半的空间,因此,length取2的整数次幂,是为了使不同hash值发生碰撞的概率较小,这样就能使元素在哈希表中均匀地散列。

get 方法
public V get(Object key) {
Node&lt;K,V&gt; e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}


final Node&lt;K,V&gt; getNode(int hash, Object key) {
	Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; first, e; int n; K k;
	if ((tab = table) != null &amp;&amp; (n = tab.length) &gt; 0 &amp;&amp; (first = tab[(n - 1) &amp; hash]) != null) {
		if (first.hash == hash &amp;&amp;  ((k = first.key) == key || (key != null &amp;&amp; key.equals(k))))
		return first;
		if ((e = first.next) != null) {
			if (first instanceof TreeNode)
			return ((TreeNode&lt;K,V&gt;)first).getTreeNode(hash, key);
		do {
			if (e.hash == hash &amp;&amp; ((k = e.key) == key || (key != null &amp;&amp; key.equals(k))))
			return e;
		} while ((e = e.next) != null);
		}
	}
	return null;
}

getNode的2个参数,key的hash值和key,首先判断table是否为null,并且table的length大于0,根据key的hash & table表的长度 - 1,计算到表的索引值,判断在此索引值对应的桶是否存在,如果存在在判断key是否相等或者key的值是否相等。如果找到则返回对应的node,否则继续判断next节点是否存在,并且节点的属性是否为TreeNode,如果为红黑树,则通过树快速查找并返回,否则循环链表,查找key对应的节点。

put方法
public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}


    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) &amp; hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node&lt;K,V&gt; e; K k;
            if (p.hash == hash &amp;&amp;
                ((k = p.key) == key || (key != null &amp;&amp; key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode&lt;K,V&gt;)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount &gt;= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &amp;&amp;
                        ((k = e.key) == key || (key != null &amp;&amp; key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size &gt; threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

put 方法有2个参数,key和value, putVal有四个参数 hash:表示key的hash值 key:待存储的key值 value:待存储的value值,从这个方法可以知道,HashMap底层存储的是key-value的键值对,不只是存储了value onlyIfAbsent:这个参数表示,是否需要替换相同的value值,如果为true,表示不替换已经存在的value evict:如果为false,表示数组是新增模式 我们看到put时所传入的参数put(hash(key), key, value, false, true),可以得到相应的含义.

  • 如果table桶为null,或者大小为0,如果为空,则调用resize()方法,对HashMap进行扩容,这次扩容的结果就是HashMap的初始化一个长度为16的数组。获取到数组的长度n
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
  • hash方法,当key=null时,也是有hash值的,是0,所以,HashMap的key是可以为null的,对比HashTable源码我们可以知道,HashTable的key直接进行了hashCode,如果key为null时,会抛出异常,所以HashTable的key不可以是null
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h &gt;&gt;&gt; 16);
    }
  • 接着,根据长度-1和hash值进行按位与运算,算出hash值对应于数组中的位置,如果没有值,则创建一个new node,存储到桶的该索引处
        if ((p = tab[i = (n - 1) &amp; hash]) == null)
            tab[i] = newNode(hash, key, value, null);
  • 如果hash冲突,首先判断hash值是否相等,如果不相等,则判断key的值equals是否相等,如果相等,则标记已找到e
            if (p.hash == hash &amp;&amp;
                ((k = p.key) == key || (key != null &amp;&amp; key.equals(k))))
                e = p;
  • 如果节点类型为TreeNode,则使用红黑树创建,并标记已找到e
            else if (p instanceof TreeNode)
                e = ((TreeNode&lt;K,V&gt;)p).putTreeVal(this, tab, hash, key, value);
  • 若3,4未符合,则循环单链表,找到则标记为e
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount &gt;= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &amp;&amp;
                        ((k = e.key) == key || (key != null &amp;&amp; key.equals(k))))
                        break;
                    p = e;
                }
  • 如果标记e不为null,则表示找到冲突的节点,使用afterNodeAccess更新节点
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
  • modCount 增加1
  • 如果桶的++size > threshold,则自动扩展桶的大小,重新分配元素分配
        if (++size &gt; threshold)
            resize();
  • 使用afterNodeInsertion 增加node
下一篇文章将重点分析resize()

参考资料

https://blog.csdn.net/ns_code/article/details/36034955 https://www.jianshu.com/p/7dcff1fd05ad