Java集合源码:(四) HashMap 原理(JDK8)

集合整体架构文章:

罗政:JAVA 集合整体架构


HashMap 是使用频繁的集合,底层使用数组加链表实现,今天我们就来揭开它的神秘面纱。

先来大致感受下HashMap的数据结构图


JDK 8 之前 HashMap 的实现是 数组+链表,即使哈希函数取得再好,也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时,这个桶下有一条长长的链表,极端情况下HashMap 就相当于一个单链表,假如单链表有 n 个元素,遍历的时间复杂度就是 O(n),完全失去了它的优势。


JDK7与JDK8中HashMap实现的最大区别就是对于冲突的处理方法。JDK 1.8 中引入了红黑树(当链表长度大于8时,链表转化为红黑树,查找时间复杂度为 O(logn)),用 数组+链表+红黑树 的结构来优化这个问题。


HashMap 源码解析

几个重要成员变量

// node节点数组
transient Node<K,V>[] table;
transient int size;
// 加载因子:为了计算扩容临界值的。  扩容临界值=table[].lenght * 加载因子
final float loadFactor;
//扩容的临界值,通过capacity * load factor可以计算出来。超过这个值HashMap将进行扩容
int threshold;

// Node节点
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash; // 缓存的key的hash
        final K key;   // hashmap的key
        V value;       // hashmap的值
        Node<K,V> next;   // node链表的next指针
}

构造函数

public HashMap() {
    this.loadFactor = 0.75f ;
}

初始化加载因子0.75 , 加载因子后面讲

put源码

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

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

先來了解下hash算法

int h = key.hashCode();
// 扰动函数,降低hash冲突概率
hash = h ^ (h >>> 16);

h >>>16

右位移16位,正好是32bit的一半,假设有个key的hashcode为

1111 1111 1111 1111 1111 0000 1110 1010
//右移16位后
0000 0000 0000 0000 1111 1111 1111 1111

就是取出了自己的高半区域,然后异或自己:

1111 1111 1111 1111 1111 0000 1110 1010
// ^ 异或
0000 0000 0000 0000 1111 1111 1111 1111
//结果为
1111 1111 1111 1111 0000 1111 0001 0101

这样我们就把原始hashcode的高16位,低16位都参与起来运算了,保留了高位和地位的特性,降低了冲突概率。如果没有上面的扰动函数,我们发现:

1111 1111 1111 1111 1111 0000 1110 1010
1111 0000 1111 1111 1111 0000 1110 1010
1111 1111 0000 1111 1111 0000 1110 1010

这几个原始的hash是不是无论高位怎么变得到的结果都一样!!!

导致后面计算数组下标时
index = h & (length-1);
比如length为16则减一为 15 15的二进制位 1111
index = h & 1111

1111 1111 1111 1111 1111 0000 1110 1010 & 1111 = 1010
1111 0000 1111 1111 1111 0000 1110 1010 & 1111 = 1010
1111 1111 0000 1111 1111 0000 1110 1010 & 1111 = 1010

我们看到没有扰动函数把高位特性参与进来所有的结果下标都是1010 hash冲突极高!!!

HashMap的table数组大小为什么是2的N次幂-1?

按位与&的计算方法是,只有当对应位置的数据都为1时,运算结果也为1, 当HashMap的容量是2的n次幂时,(n-1)的2进制也就是1111111***111这样形式的(上面的例子15就是1111),这样与添加元素的hash值进行位运算时,能够充分的散列,使得添加的元素均匀分布在HashMap的每个位置上,减少hash碰撞。


再回到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<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)//第一次put,tab为null
            n = (tab = resize()).length; // resize 初始化 table[]
        if ((p = tab[i = (n - 1) & hash]) == null) //计算下标: 相当于 hash%table.lenght-1
            tab[i] = newNode(hash, key, value, null);// 没有hash冲突
        else {  //  有hash冲突时,构建链表 或者 升级成 树
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)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 >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && 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 > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

上面很复杂,我们拆解来讲,首先是resize,初始化table 数组:

 final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        // 获取table[] 此时的大小
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 扩容的临界值 , 初始为0 
        int oldThr = threshold;
        int newCap;   // 新计算的 table[] 大小
        int newThr = 0;  // 新计算的 扩容临界值
        if (oldCap > 0) {
            // table[] 大小已经很大了
            if (oldCap >= 1073741824) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
           // oldCap << 1  : 左移运算符,num <<1,相当于num乘以2 低位补0。
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                  
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {  //第一次初始化 table[] 会走这里
            newCap = 16; // 初始化table[]大小为16
            newThr = (int)(0.75f * 16); // 新的扩容临界值为: 加载因子0.75 * 16 
        }
        threshold = newThr; // 新计算的扩容临界值 赋值给全局的扩容临界值threshold
        //  new出了 table[]
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;

       // 由于table[]数组大小变大,以前的元素hash计算key的下标位置也变了,要重新移动
      //下面就是重组移动的算法,我们后面讲。
        if (oldTab != null) {
           //  ...... 重组移动数据算法,rehashing算法
        }
        return newTab;
    }

resize在 第一次初始化table[] 和 元素达到了扩容临界值threshold 会 执行:

  • 初始化时的table[]大小为16,扩容临界值为: 0.75f*16 = 12。
  • 当第一次扩容时,table[]大小会增倍,也就是从16变成 32 , 扩容临界值也是翻倍,从12变成24 。

resize 还有一个重要的移动table[] 元素的操作(rehashing),后面讲。


上面构造好了table[] 后在回到我们的 put方法

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)//刚new出来为空
            n = (tab = resize()).length;  // resize扩容
        if ((p = tab[i = (n - 1) & hash]) == null) //计算下标: 相当于 hash%table.lenght-1
            tab[i] = newNode(hash, key, value, null);// 没有hash冲突
        else {  //  有hash冲突时,构建链表 或者 升级成 树
              // 先省略,后面开专栏讲....
        }
        ++modCount;
        if (++size > threshold) // 大于了 扩容临界值 进行扩容
            resize();  // 扩容
        afterNodeInsertion(evict);
        return null;
    }
    // 构造 Node 节点
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
        return new Node<>(hash, key, value, next);
    }

put流程总结

  • 先通过扰动函数计算key的hash值。
  • 第一次put时,会resize构建大小 为16,扩容临界值为12的table[]数组,然后通过 上面的hash值 & table[].lenght 计算在table[]数组中落的位置。
  • 如果该位置有Node节点,则进行冲突处理,添加到链接或者树。
  • 如果该位置无Node节点,进行newNode,然后放到table[]位置。
  • 最后进行resize判断,如果当前table[]数组元素的个数大于了扩容临界值,进行resize扩容,扩容时,会进行rehashing操作。

hash冲突时处理

// Node<K,V> p  节点 为计算落到table[]的位置的链表(数)第一个节点
// hash  为当前 put 时 的 key 经过扰动函数计算出的hash值
Node<K,V> e; K k;
if (p.hash == hash && // key的hash值 一样
	((k = p.key) == key || (key != null && key.equals(k))))// key的hashcode和equals一样
	e = p; // 直接认为 key相同,覆盖原来的节点就行了
else if (p instanceof TreeNode) // 树结构,插入到 树节点中
	e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
       // 插入到 链表
	for (int binCount = 0; ; ++binCount) {
            // next为空,代表找到了链表的尾部了
	    if ((e = p.next) == null) {
               // 将当前 key value 做成Node 链到链表的尾部
		p.next = newNode(hash, key, value, null);
		if (binCount >= 8 - 1) // 循环了8次 就进入 将链表 转成树
		    treeifyBin(tab, hash);
		break;
	    }
           // 链表中有一个节点 key 相等进行覆盖
	    if (e.hash == hash &&
		((k = e.key) == key || (key != null && 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;
}

先看链表的头结点的key是否等于当前的key,比较算法为: 扰动hash值 , key类本身的hashcode方法,key类的 equals方法。 如果相等,就用新的value覆盖这个Node。

如果上面不相等,然后遍历链表,期间也按上面算法判断key是否相等,相等就覆盖。如果找到了链表尾部(next指针为null), 则链接到尾部节点,如果链表数量大于了8,还要将链表转成红黑树。

treeifyBin 链表转成红黑树

    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }
    TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
        return new TreeNode<>(p.hash, p.key, p.value, next);
    }
  static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }
}

红黑树还要花很大篇幅讲,必须要另起一篇文章。

罗政:Java集合:(四) HashMap 红黑树(JDK8)


resize的rehashing操作

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 构造一个扩容的新表
if (oldTab != null) {
    for (int j = 0; j < oldCap; ++j) { // 遍历 老的table[]数组
	Node<K,V> e;
	if ((e = oldTab[j]) != null) {// table位置有数据
	    oldTab[j] = null; //先置空老表的table[]位置
	    if (e.next == null) //链表就一个元素
		newTab[e.hash & (newCap - 1)] = e; // 放到新表的位置: hash&table[].length
	    else if (e instanceof TreeNode) // 树节点的rehashing
		((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
	    else { // 链表的 rehashing
		Node<K,V> loHead = null, loTail = null;
		Node<K,V> hiHead = null, hiTail = null;
		Node<K,V> next;
		do {
		    next = e.next;
                     //为true则说明e这个节点在resize之后不需要挪位置,反之则需要换个位置
		    if ((e.hash & oldCap) == 0) {
                       // 等于0 加入到 lo链表 loHead为链表头 loTail为链表尾
			if (loTail == null)
			    loHead = e;
			else
			    loTail.next = e;
			loTail = e;
		    }
		    else {
                     // 不等于0 加入到 hi链表 hiHead为链表头 hiTail为链表尾
			if (hiTail == null)
			    hiHead = e;
			else
			    hiTail.next = e;
			hiTail = e;
		    }
		} while ((e = next) != null);
		if (loTail != null) {
                    // lo链表不为空  直接位置不变 放入到源table位置
		    loTail.next = null;
		    newTab[j] = loHead;
		}
		if (hiTail != null) {
                      // hi链表不为空 位置改变 放入到源table位置 + 源table的大小
		    hiTail.next = null;
		    newTab[j + oldCap] = hiHead;
		}
	    }
	}
    }
}

rehashing三步曲

从0开始遍历老的table[]数组,如果该位置只有一个元素就按 hash&table.size-1 直接放入到新表的位置。如果该位置是TreeNode,就执行红黑树的split。如果是链表则执行下面步骤。

先定义lo ,hi 链表。遍历源链表元素,判断 (e.hash & oldCap)==0 时,将当前元素放入到lo链表,否则放入到hi链表。最后完成遍历。

遍历完成之后,判断lo不为空,则直接将lo链表加入到源链表在table[]数组的位置。如果hi链表不为空,则将hi链表加入到源链表在table[]数组的位置+table[]数组大小。

if((e.hash & oldCap)==0)是个什么?

我们知道table[]数组的大小都是2的n次幂,如:16,32,64.... , 减1就为: 15,31,63.... 二进制为:

15 ==> 0000 0000 0000 0000 0000 0000 0000 1111

31 ==> 0000 0000 0000 0000 0000 0000 0001 1111

63 ==> 0000 0000 0000 0000 0000 0000 0011 1111

由于计算落在table[]位置的公式为 :key.hash&(table.length-1) , 因此大小为 16,32,64 的table[] ,位置结果分别就在于key.hash 的 后4位,5位,6位 ...

因此如果长度为16的HashMap扩容后(32),也就是取key.hash的后四位到取key.hash的后5位。

(e.hash & oldCap)==0 , e是源计算好的位置。等于0的话,也就是刚好e.hash的后四位有值,前面的位数都是0,所以后5位的结果跟后4位的结果一样。因此放入到lo链表中。

如果不等于0的话,表示e.hash的后五位有值,比如11101(第一位肯定不为0),也就是等于原来的四位1101 + 10000 (16的二进制为10000),这个10000也就是源容量的大小。 因此放入到hi链表中。

故虽然数组大小扩大了一倍,但是同一个 key 在新旧table中对应的index却存在一定联系: 要么一致,要么相差一个 oldCap

得出一个结论

如果(e.hash & oldCap) == 0则该节点在新表的下标位置与旧表一致都为j

如果(e.hash & oldCap) == 1则该节点在新表的下标位置j + oldCap


get(Object key) 源码

    public V get(Object key) {
        Node<K,V> e;
        // 先计算 扰动 hash
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) { // table[]数组桶的位置的节点
            if (first.hash == hash && // key相等比较  算法
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first; // 比较相等,直接返回 找到了
            if ((e = first.next) != null) {// 还有下一个节点
                if (first instanceof TreeNode)
                    // 红黑树查找
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    // 链表遍历
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

先通过key的hash找到落在table[]数组桶的位置元素,判断key是否相同,相同就返回找到,否则就遍历当前桶的数据结构,如果是TreeNode,则调用红黑树的getTreeNode, 否则遍历链表,一个一个节点去判断key是否相同。

key相同判断算法 : 扰动hash相等 & key类的hashcode相等 & key类的equals相等。

红黑树查找请见这篇文章:

罗政:Java集合:(四) HashMap 红黑树(JDK8)



HashMap 默认加载因子为什么是 0.75 ?

table[]加链表的数据结构会导致下面两个问题:

  • 如果空间利用率高,那么经过的哈希算法计算存储位置的时候,会发现很多存储位置已经有数据了(哈希冲突);
  • 如果为了避免发生哈希冲突,增大数组容量,就会导致空间利用率不高。

加载因子就是表示Hash表中元素的填满程度,公式为:

加载因子 = 填入表中的元素个数 / 散列表的长度

加载因子越大,table[]能存更多的元素,空间利用率大,但是hash冲突会加大。

加载因子越小,填满的元素越少,冲突发生的机会减小,但空间浪费了更多了,而且还会提高扩容rehash操作的次数。

所以必须在“冲突的机会”与“空间利用率”之间,寻找一种平衡 。至于为什么是数字0.75,是根据 泊松分布数学公式 计算的,就不研究了


Hash算法常见碰撞解决方法

1.开放地址法(再散列法)

当发生地址冲突时,按照某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止。假如:55 % 7 = 6 发生冲突,下一个存储地址( 6 + 1 )% 7 = 0 ,仍然发生冲突,再下一个存储地址:( 6 + 2 )% 7 = 1 未发生冲突,可以存入。

2.再哈希法Rehash

这种方法是同时构造多个不同的哈希函数:

Hi=RH1key i=12,…,k

当哈希地址Hi=RH1(key)发生冲突时,再计算Hi=RH2(key)……,直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间。

3.链地址法(拉链法) HashMap使用此法

将所有关键字为同义词的记录存储在同一线性链表中.基本思想:将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

拉链法的优缺点

优点:

  • 拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;
  • 由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;
  • 开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;
  • 在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表,删除结点不能简单地将被删结 点的空间置为空,否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中,空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点。

缺点:

指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。

4.建立一个公共溢出区

假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表,另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。


强烈推荐一篇 干货,精华 博客:


Java架构师修炼

本文完~

支付宝打赏 微信打赏

如果文章对您有帮助,您可以鼓励一下作者