盐析白兔

这个屌丝很懒，什么也没留下！

热门标签

java数据结构之HashMap_java hashmap

作者：盐析白兔 | 2024-08-09 15:09:48

踩

java hashmap

2.2、插入数据：Key不同，但产生hash冲突

前言

做过java开发的同学应该都知道HashMap是使用数组+链表的数据结构进行数据的存储，后来演变到jdk8之后，为了提高插入和查询效率，在插入的数据超过某个阈值之后，会将数组+链表的结构转化成数组+红黑树的数据结构，也即如下图：

最近闲来无事，准备将HashMap插入数据的过程，以及其数据结构的转化过程，再回顾一下，故写此篇文章，以是记录。

1、初始化

对于HashMap，在我们初始化以及插入第一条数据的时候，内部发生了什么事情呢？

1.1、初始化

当我们执行了如下一个初始化操作：

HashMap<String,String> map = new HashMap<String,String>();

从源代码层面看，只是对内部一个叫做loadFactor的属性进行了初始化0.75，那么这个loadFactor参数是做什么用的呢？

我们前言中说过，HashMap是用的一个数组+链表的形式进行数据的存储，那么这个数组的长度是如何决定的呢？什么时候要对数组进行扩充，什么时候又要对数组进行缩减呢？那么这个判断依据就是根据loadFactor来决定的。具体来说就是：当插入数据的个数 / 数组的长度 >= loadFactor时，我们就要对数组的长度进行扩展啦。因为当插入的数据越来越大的时候，在数组长度不变的情况下，hash冲突会越来越严重，数组节点下的数据就会越来越多，进而导致查询效率越来越差。

另外需要说明的是：在扩展数组的时候，数组的长度都是2^n个，在初始化的时候，数组长度是2^4 = 16，每一次扩展，都增加一倍。

1.2、插入第一条数据

当我们执行如下操作，插入第一条数据的时候，hashmap的内部又发生什么事情了呢？

map.put("chenza","30")

第一步：先计算字符串"chenza"的hash值，作为判断插入数据哪个节点的依据。

第二步: 初始化数组表table，如上所述，第一次初始化的时候，数组表table的长度是2^4 = 16

第三步：用"chenza"的hash值和数组表table的长度(n - 1) 做"且"运算，判断当前数据应该插入到数组的哪个位置。(注：做且运算的原因保证插入的位置是[0,n-1]之间，不会数组越界)

第四步：size字段+1，并判断是否超阈值threshold，如果超过阈值threshold，则进行数组table的扩展，且以后每插入一条数据，都会进行阈值判断。(注：这里的threshold = 当前的数组table长度 * loadFactor，与上节描述一致)

代码执行逻辑如下：


public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true); //计算key的hash值
    }
 
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)
            n = (tab = resize()).length; //初始化数组table，长度16
        if ((p = tab[i = (n - 1) & hash]) == null)  //计算数据应该插入的位置
            tab[i] = newNode(hash, key, value, null);  //在数组第i个位置插入数据
        else {
            ....... //暂时省略
        }
 
        ++modCount;
        if (++size > threshold)  //size记录插入的数据的个数，并判断是否超阈值。
            resize();
        ......

至此，我们的初始化及第一条数据插入已经完成。从上所述，我们得知，我们一共做了三方面的工作：

(1)、初始化参数loadFactor

(2)、完成数组table的初始化，将其长度置为2^4 = 16

(3)、将数据插入到数组table对应的节点上。

到目前位置，我们的HashMap的结构如下：

map.put("chenza","30")

2、数组 + 链表

现在，在我们的HashMap中，已经有了一条数据，那么我们接下来插入第二条、第三条...第n条数据，看看HashMap中到底经历了怎样的过程。

2.1、插入数据：没有hash冲突

何为hash冲突，在HashMap中所说的hash冲突，指的是：i = hash(key) & (n - 1)之后，数组table在i处已经有数据，代表两个不同的key需要放到数组的同一个节点下。

当没有hash冲突时，和插入第一条数据一样，直接将数据插入到数组对应的节点即可。

无hash冲突时的代码执行逻辑：


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)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);  //无hash冲突，直接将数据插入到数组中
        else {
            ......
        }

此时的数据结构如下：

2.2、插入数据：Key不同，但产生hash冲突

当Key不同，但是产生hash冲突的情况下，就会产生链表操作了。此时会顺着冲突处的数组节点的链表一个一个的去找，直到找到叶子节点位置，将新数据作为新的叶子节点挂在链表下面，如下图所示:

当然在寻找叶子节点的过程中，如果发现当前数组节点下的链表长度超过一定的阈值时，就会自动将链表转化为红黑树进行存储(转化为红黑树的操作，参见第三节数组+红黑树 )。HashMap默认的链表长度不能超TREEIFY_THRESHOLD = 8.代码逻辑如下：


if ((p = tab[i = (n - 1) & hash]) == null)
	tab[i] = newNode(hash, key, value, null);
else {
	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); //如果链表长度超过8，则将链表转化为红黑树
				break;
			}
			if (e.hash == hash &&
				((k = e.key) == key || (key != null && key.equals(k))))
				break;
			p = e;
		}
	}

2.3、插入数据：Key相同

key相同，hash(Key)自然相同，自然也会有hash冲突。所以key相同是hash冲突的一种特殊情况。

第一种情况：新数据的key和数组table的节点key相同，则直接替换数组table节点的value值即可。

第一种情况：新数据的key和链表下某个节点的key相同，遍历链表，替换key相同处的value值即可。

代码执行逻辑：


if ((p = tab[i = (n - 1) & hash]) == null)
	tab[i] = newNode(hash, key, value, null);
else {
	Node<K,V> e; K k;
	if (p.hash == hash &&
		((k = p.key) == key || (key != null && key.equals(k))))
		e = p;  // 和数组table节点的值相同，直接替换value即可，value的替换见最下面的代码e.value = value
	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) { //在这里进行了e的赋值，value的替换见最下面的代码e.value = value
				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;  // 循环遍历链表，寻找key值相同的链表节点，找到直接挑出循环。
			p = e;
		}
	}
 
 
    if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;  //替换key相同的value
                afterNodeAccess(e);
                return oldValue;
            }

3、数组 + 红黑树

至此，我们在每个数组节点下插入的数据都不超过8个，所以一直是链表的形式进行数据的存储。

在第二节中，我们也预埋了伏笔，当数组table某个节点下的链表超过8个以后，HashMap就会调用treeifyBin函数，将链表转化成红黑树的结构，本节，我们就来看看他是如何转化为红黑树的，以及为什么要转化为红黑树？

3.1、链表如何转化为红黑树？

链表转化为红黑树的过程，就写在treeifyBin函数中，我们先看一下这块儿代码，然后再逐个分析。


//链表转化为红黑树的过程代码
final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else 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);
        }
    }

第一步：转化成红黑树的条件： n = (tab.length) < MIN_TREEIFY_CAPACITY(64)，也就是说当数组table的长度小于64时，不会使用红黑树，只会对数组table进行扩展，重新分配数据的存放位置。

第二步：当数组table长度大于64时，才开启转化红黑树的执行逻辑。代码中有一个while循环，注意这个while循环只是把链表节点Node转化为红黑树的节点TreeNode，这个循环中并不进行生成红黑树。这就引入一个问题，他是如何把Node转化为TreeNode的呢？其实从继承关系中可以看到TreeNode是继承自Node，TreeNode和Node的结构如下，从图上看，TreeNode比Node多了几个属性：parent,left,right,prev,red

第三步：当把所有的Node节点转化为TreeNode节点之后，继续调用hd.treeify(tab)，这个才是真正的把链表转化为红黑树。

3.2、为什么要转化为红黑树？

(1)、从链表和红黑树的结构就可以看到，红黑树的层级更低，在进行查询时，链表的查询时间复杂度是O(n)，红黑树的查询时间复杂度是O(log(n))，在数据量很大的情况下，显然红黑树的查询效率比链表要好的多。

(2)、我们知道，平衡二叉树的结构更加平衡，左右子树的高度差不会超过1，为什么不使用平衡二叉树呢? 原因是我们还要考虑插入数据的性能，平衡二叉树的结构的确更加均衡，但是为了维持这种均衡，在插入数据时，需要不断的进行平衡二叉树的旋转调整，插入效率相比红黑树来说，差的多。根据权威资料显示：插入操作是红黑树的优势之一，红黑树的插入操作可以在 O(log(n)) 的时间内完成，而平衡二叉树的插入操作在最坏情况下需要 O(n)的时间。

4、数组resize

最后，我想给大家重放一下数组resize的过程，为什么呢？在我们实际使用HashMap的过程中，如果数据量很大，免不了要进行数组的resize。resize不仅仅要对数组table进行扩展，还要对数组table节点上下挂的数据进行重新分配，所以是一个非常消耗性能的过程。

有同学可能要问了，为什么要对数组table节点上下挂的数据进行重新分配，让他们安静的待在原来的节点下不是挺好的吗？为什么要翻来覆去的去折腾？对于这样的同学，送给你三个字："要多想"

原因很简单，数组table进行了扩展，那么数组的长度n也发生了变化，我们判断数据放在数组哪个节点之下用的是 hash(key) & (n - 1)，现在数组table长度n变了，数据存放的位置自然也要发生变化，不然查询key时定位的数组节点位置不一样，无法从HashMap中查出key对应的数据。

另外在走读源码的过程中，发现一个很有意思的设计：那就是原来一个数组节点下的链表(红黑树)数据，在进行resize之后，数据会被重新分配到几个新的节点上呢？答案是两个。这个点在没看源代码之前是没有想到的，看了源代码之后，感觉这个点设计的太精妙了。原因是什么呢？待我慢慢道来。

我们知道，数组table的长度每次resize都是扩展一倍，且长度还都是2^n，也就是说数组table的长度只会是16,32,64,128,256...；而数据存放到数组哪个节点是有由hash(key) & (length - 1) 来决定的。在这两个条件下，就会发生上述一个节点数据分裂成两个节点数据的情况。我们以扩展前数组table长度是16和扩展后数组table长度是32为例，来说明具体原因。

hash(key) 是不会变的，变的只有length - 1；

当length = 16时，length - 1就是15，15的二进制是00001111，

当length = 32时，length - 1就是31，31的二进制是00011111，

看出来什么特殊之处了吗？对，就是31的二进制比15的二进制的上一位多了一个1，这就导致(hash(key) & 31) 和 (hash(key) & 15) ，要么相等(数据保留在数组原位置)，要么最高位多一个1(也就是数组位置+16)；

32扩展到64； 64扩展到128... 原理类似。

看到这里，真是不得不感叹二进制世界的奇妙和jdk编程人员对二进制的运用达到了炉火纯青的地步。

所以在扩展前后一个数组节点下的数据的分裂过程如下：

下面是代码层面链表一分二的过程(代码里有作者注释)：(另：红黑树的分裂过程类似，也是将一个红黑树分裂成两个红黑树，在这里就不赘述了，大家可以看((TreeNode<K,V>)e).split(this, newTab, j, oldCap)中的split函数，里面也是两个变量loHead 和 hiHead分别存放分裂后的两个红黑树)


final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        //扩展前的数组长度
        int oldCap = (oldTab == null) ? 0 : oldTab.length; 
        //扩展前的插入数据的阈值(数组长度 * 0.75)
        int oldThr = threshold; 						   
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) { //如果数组长度已经大于1 << 32，不再进行扩展，直接返回。
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // newCap = oldCap << 1,左移一位，相当于扩展一倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&  
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
                //插入数据的阈值也扩展一倍。
                newThr = oldThr << 1; 
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                    (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
		// -----上面的代码主要是对新数组的长度和数据个数的阈值进行重新计算
		// -----下面的代码主要是对数据重新分配
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        //如果是红黑树，则进行红黑树的分裂
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 
                    else {//如果是链表，则进行链表的分裂
						/**
						 *由分析知，一个链表只可能分裂成两个链表。
						 *loHead：存放的是位置不动的数据
						 *hiHead：存放的是位置+16(以分析为例)的数据
						*/
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
							//j不动，loHead还存放在原来的数组位置
                            newTab[j] = loHead; 
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
							//j + 16(以分析为例),hiHead存放在j + 16位置
                            newTab[j + oldCap] = hiHead; 
                        }
                    }
                }
            }
        }
        return newTab;
    }

5、后记

断断续续写了好久，一边走读源码，一边画图，一边写文章，终于把HashMap的内部结构分析完了。相对其他java数据结构来说，HashMap结构算是稍微比较复杂的，但是HashMap并不是多线程安全的，在多线程使用的情况下，要注意线程安全问题。

了解了HashMap之后，其实也就了解了HashSet，因为HashSet就是内部构建了一个HashMap对象，使用了HashMap的key不会重复的特性来进行数据的去重。

另外本篇文章旨在探究HashMap的结构，对其中的红黑树并没有过多着墨进行进一步深究，因为红黑树的生成条件、插入数据时节点的旋转、红黑节点的变化等等，还是比较复杂的，如果写在这篇文章中，有点鸠占鹊巢的意思。所以，红黑树的内容完全可以单独抽离一篇文章进行探究，就不在HashMap文章中进行赘述了，后面有时间，我会再学习一下红黑树，再来跟大家唠叨唠叨。

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】