HashMap源码分析

HashMap源码分析

zenos 47 2023-06-30

HashMap源码

基础知识

底层数据结构：数组+链表+红黑树

优化：

JDK 1.8开始优化了hashmap的数据结构，链表 -> 红黑树，解决hash冲突的问题。

JDK 1.8以后，如果一个链表的长度超过了8，就会自动将链表转换为红黑树，链表的遍历性能，时间复杂度是O(n)，红黑树是O(logn)，所以如果出现了大量的hash冲突以后，红黑树的性能比链表高得多

红黑树的基础知识

1. 红黑树是二叉查找树，左小右大，根据这个规则可以快速查找某个值

2. 但是普通的二叉查找树，是有可能出现瘸子的情况，只有一条腿，不平衡了，导致查询性能变成O(n)，线性查询了

3. 红黑树，红色和黑色两种节点，有一大堆的条件限制，尽可能保证树是平衡的，不会出现瘸腿的情况

4. 如果插入节点的时候破坏了红黑树的规则和平衡，会自动重新平衡，变色（红 <-> 黑），旋转，左旋转，右旋转

JDK8的优化项

  • 扩容机制和原理

  • hash冲突后如何解决

  • 链表及红黑树的解决方式

  • 如何减少hash碰撞

  • 如何优化hash寻址

  • 高性能rehash算法

核心方法

对key，进行一个hashCode()的一个运算，获取key的hash值

常规的一个做法，就是用这个hash值对数组的长度进行取模，根据取模的结果，将key-value对方在数组中的某个一个元素上

详见hashmap数据结构图

[![hashmap数据结构图](03_hashmap数据结构.png)](https://www.mdeditor.com/images/logos/markdown.png "hashmap数据结构图")

核心成员变量

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 运算得到的值为16

数组的默认的初始大小是16，这个跟ArrayList是不一样的，初始的默认大小是10

    static final float DEFAULT_LOAD_FACTOR = 0.75f //负载因子

这个参数，默认的负载因子，如果数组里的元素个数达到了数组大小（16） * 负载因子（0.75f），默认是达到12个元素，就会进行数组的扩容


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

这是一个很关键的内部类，他其实是代表了一个key-value对，里面包含了key的hash值，key，value，还有就是可以有一个next的指针，指向下一个Node，也就是指向单向链表中的下一个节点，通过这个next指针，就可以形成一个链表

  transient Node<K,V>[] table;

Node<K, V>[]，这个数组就是map核心数据结构的数组，数组的元素就可以看到是Node类型的，天然就可以挂成一个链表，单向链表，Node里面只有一个next指针。

   transient int size;

这个size代表的是就是当前hashmap中有多少个key-value对，如果这个数量达到了指定大小 * 负载因子，那么就会进行数组的扩容。

   int threshold;

这个值，其实就是说capacity（就是默认的数组的大小），就是说capacity * loadFactory，就是threshold，如果size达到了threshold，那么就会进行数组的扩容。

    final float loadFactor;

默认就是负载因子，默认的值是0.75f，你也可以自己指定，如果你指定的越大，一般就越是拖慢扩容的速度，一般不要修改。

优化后的降低冲突概率的hash算法


   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);
   }

这个方法是计算出来了key的hash值

h = key.hashCode()：这个就是直接获取了key的hash值，通过的是hashCode()方法

1111 1111 1111 1111 1111 1010 0111 1100

h >>> 16，这个是位运算的操作，这个东西是把32位的二进制的数字，所有的bit往右侧右移了16位

1111 1111 1111 1111 1111 1010 0111 1100

-> h >>> 16

0000 0000 0000 0000 1111 1111 1111 1111

-> h ^ (h >>> 16)

1111 1111 1111 1111 1111 1010 0111 1100

0000 0000 0000 0000 1111 1111 1111 1111

1111 1111 1111 1111 0000 0101 1000 0011

他这么做，其实是考虑到，将他的高16位和低16位进行一个异或运算，必须记住这么一个结论，在面试的时候被问到hashmap的话，必须得说出来这个意思

就是因为，后面在用这个hash值定位到数组的index的时候，也有一个位运算

但是的话呢，一般那个后面的位运算，一般都是用低16位在进行运算，所以说如果你不把hash值的高16位和低16位进行运算的话，那么就会导致你后面在通过hash值找到数组index的时候，只有hash值的低16位参与了运算

提前在hash()函数里面，就会把高16位和低16位进行一下异或运算，就可以保证说，在hash值的低16位里面，可以同时保留他的高16位和低16位的特征，大家一定要记住这个结论

这么做有什么好处呢？为什么要保证同时将高16位和低16位的特征同时纳入运算，考虑到数组index的定位中去呢？因为这样子可以保证降低hash冲突的概率，如果说直接用hash值的低16位去运算定位数组index的话，可能会导致一定的hash冲突

put操作原理以及hash寻址算法


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

   if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;

(n - 1) & hash

n = 16

n - 1 = 15

15 & hash

1111 1111 1111 1111 0000 0101 1000 0011

0000 0000 0000 0000 0000 0000 0000 1111

-> 与操作

就是必须都是1，才是1，否则就是0

0000 0000 0000 0000 0000 0000 0000 0011，转成10进制，就是3，index = 3

他的hash寻址的算法， 并不是说用hash值对数组大小取模，取模就可以将任意一个hash值定位到数组的一个index那儿去，取模的操作性能不是太高

位运算，性能很高，&与操作，来实现取模的效果

他优化以后的一个效果，就是说他的数组刚开始的初始值，以及未来每次扩容的值，都是2的n次方

也就是说他后面每次扩容，数组的大小就是2的n次方，只要保证数组的大小是2的n次方，就可以保证说，(n - 1) & hash，可以保证就是hash % 数组.length取模的一样的效果，也就是说通过(n - 1) & hash，就可以将任意一个hash值定位到数组的某个index里去

i = (n - 1) & hash，i就是最后寻址算法获取到的那个hash值对应的数组的index

hash冲突时的链表处理


   /**
	 * Implements Map.put and related methods
	 *
	 * @param hash         hash for key
	 * @param key          the key
	 * @param value        the value to put
	 * @param onlyIfAbsent if true, don't change existing value
	 * @param evict        if false, the table is in creation mode.
	 * @return previous value, or null if none
	 */
	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;
		//hash定位到的这个位置是空的，之前没有任何人在这里，此时直接是放一个Node在数组的这个位置即可
		if ((p = tab[i = (n - 1) & hash]) == null)
			tab[i] = newNode(hash, key, value, null);
		else {
			Node<K, V> e;
			K k;
			// 如果满足条件，说明是相同的key，覆盖旧的value
			// map.put(1, “张三”)
			// map.put(1, “李四”)
			if (p.hash == hash &&
					((k = p.key) == key || (key != null && key.equals(k))))
				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) {
					if ((e = p.next) == null) {
					// 把旧值的下一个指针指向这个新值
						// 单向链表
						p.next = newNode(hash, key, value, null);
						// 如果当前链表的长度（binCount），大于等于等于8的话，那么此时就需要将这个链表转换为一个红黑树的数据结构
						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
				// 张三就是oldValue
				V oldValue = e.value;
				if (!onlyIfAbsent || oldValue == null)
					e.value = value;
				afterNodeAccess(e);
				return oldValue;
			}
		}
		++modCount;
		if (++size > threshold)
			resize();
		afterNodeInsertion(evict);
		return null;
	}

JDK 1.8引入红黑树优化hash冲突

如果说出现大量的hash冲突之后，假设某给位置挂的一个链表特别的长，就很恶心了，如果链表长度太长的话，会导致有一些get()操作的时间复杂度就是O(n)，

但是如果链表，大量的key冲突，会导致get()操作，性能急剧下降，导致很多的问题

所以说JDK 1.8以后人家优化了这块东西，会判断，如果链表的长度达到8的时候，那么就会将链表转换为红黑树，如果用红黑树的话，get()操作，即使对一个很大的红黑树进行二叉查找，那么时间复杂度会变成O(logn)，性能会比链表的O(n)得到大幅度的提升

链表转红黑树是怎么搞的

当你遍历一个链表达到第7个节点的时候，binCount是6

当你遍历到第8个节点，此时binCount是7，同时你挂上了第9个节点，然后就会发现binCount >= 7，达到了临界值，也就是说，当你的链表节点的数量超过8的时候，此时就会将链表转换为红黑树


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);

上面那个do while循环执行完了以后，先是将单向链表转换为了TreeNode类型组成的一个双向链表

if ((tab[index] = hd) != null)

hd.treeify(tab);

接下来针对双向链表，将双向链表转换为一颗红黑树，直接记住这个结论就ok了，当链表的长度超过8的时候，链表就先是变成双向链表，然后是变成红黑树

基于数组的扩容原理图解


if (oldCap > 0) {

if (oldCap >= MAXIMUM_CAPACITY) {

threshold = Integer.MAX_VALUE;

return oldTab;

}

else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

oldCap >= DEFAULT_INITIAL_CAPACITY)

newThr = oldThr << 1; // double threshold

}

扩容的新长度为旧长度左移一位，即原先的两倍

JDK 1.8的高性能rehash算法

DK 1.8以后，为了提升rehash这个过程的性能，不是说简单的用key的hash值对新数组.length取模，取模给大家讲过，性能较低，所以JDK 1.8以后hash寻址这块，统一都是用的这个位操作

n - 1 0000 0000 0000 0000 0000 0000 0000 1111

hash1 1111 1111 1111 1111 0000 1111 0000 0101

&结果 0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）

n - 1 0000 0000 0000 0000 0000 0000 0000 1111

hash2 1111 1111 1111 1111 0000 1111 0001 0101

&结果 0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）

此时，上面两个hash值会出现hash碰撞的问题，使用链表，或者是红黑树来解决

如果数组的长度扩容之后 = 32，重新对每个hash值进行寻址，也就是用每个hash值跟新数组的length - 1进行与操作

n-1 0000 0000 0000 0000 0000 0000 0001 1111

hash1 1111 1111 1111 1111 0000 1111 0000 0101

&结果 0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）

n-1 0000 0000 0000 0000 0000 0000 0001 1111

hash2 1111 1111 1111 1111 0000 1111 0001 0101

&结果 0000 0000 0000 0000 0000 0000 0001 0101 = 21（index = 21的位置）

00101 = 5

10101 = 21

hash2的位置，从原来的5变成了21，规律是什么？

也就是说，JDK 1.8，扩容一定是2的倍数，从16到32到64到128

就可以保证说，每次扩容之后，你的每个hash值要么是停留在原来的那个index的地方，要么是变成了原来的index（5） + oldCap（16） = 21

所以说，这个就是JDK 1.8以后，数组扩容的时候，元素重新寻址的一个过程和原理

hashmap的底层原理

  1. hash算法：为什么要高位和低位做异或运算？

  2. hash寻址：为什么是hash值和数组.length - 1进行与运算？

  3. hash冲突的机制：链表，超过8个以后，红黑树

  4. 扩容机制：数组2倍扩容，重新寻址（rehash），hash & n - 1。 判断二进制结果中是否多出一个bit的1，如果没多，那么就是原来的index，如果多了出来，那么就是index+oldCap，通过这个方式，就避免了rehash的时候，用每个hash对新数组.length取模，取模性能不高，位运算的性能比较高

Java