【Java集合篇】HashMap 在 get 和 put 时经过哪些步骤

本文介绍: 因为 & 是基于内存的二进制直接运算，比转成十进制的取模快的多。以下运算等价:

在这里插入图片描述

HashMap在get和put时经过哪些步骤?

✔️ 典型解析
✔️get方法
✔️put方法
✔️ 拓展知识仓

✔️ 典型解析

对于HashMap来说，底层是基于散列算法实现，散列算法分为散列再探测和拉链式。HashMap 则使用了拉链式的散列算法，即采用数组+链表/红黑树来解决hash冲突，数组是HashMap的主体，链表主要用来解决哈希冲突。这个数组是Entry类型，它是HashMap的内部类，每一个Entry包含一个keyvalue键值对。

✔️get方法

对于get方法来说，会先查找桶，如果hash值相同并且key值相同，则返回该node节点，如果不同，则当node.next!=null时，判断是红黑树还是链表，之后根据相应方法进行查找。

直接看一个Demo吧，帮助理解。

import java.util.HashMap;  
import java.util.Map;  

// 定义一个HashMap类，该类继承了HashMap类 
public class ComplexHashMap<K, V> extends HashMap<K, V> {  
	  // 定义默认的初始容量和加载因子  
    private static final int DEFAULT_INITIAL_CAPACITY = 16;
      
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
     // 定义树化操作的阈值   
    private static final int MAX_TREEIFY_THRESHOLD = 8;
      // 定义存储红黑树根节点的数组    
    private Entry<K, V>[] treeRoots;
    // 定义树化操作的阈值  
    private int treeifyThreshold;  
  
    public ComplexHashMap() {  
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);  
    }  
  
    public ComplexHashMap(int initialCapacity, float loadFactor) {
    	// 调用父类的构造函数进行初始化，传入初始容量和加载因子参数   
        super(initialCapacity, loadFactor);  
        treeRoots = new Entry[DEFAULT_INITIAL_CAPACITY];
         // 计算树化操作的阈值，该值等于初始容量乘以加载因子    
        treeifyThreshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);  
    }  
  	
  	// 重写父类的rehash方法，用于在需要时重新哈希键值对并可能进行树化操作  
    @Override  
    protected void rehash(int newCapacity) {  
        super.rehash(newCapacity);  
        if (newCapacity > treeifyThreshold && size > MAX_TREEIFY_THRESHOLD) {  
            for (Entry<K, V> entry : this.entrySet()) {  
                K key = entry.getKey();  
                if (containsKey(key)) {  
                    put(key, entry.getValue());  
                }  
            }  
            treeify();  
        }  
    }  
  	// 定义一个私有方法treeify用于将map中的元素根据键进行排序并重新组织成红黑树结构以提升查询效率。
    private void treeify() {  
        Entry<K, V>[] newTreeRoots = new Entry[size()];  
        for (Entry<K, V> entry : this.entrySet()) {  
            K key = entry.getKey();  
            int index = Math.abs(key.hashCode()) % newTreeRoots.length;  
            if (newTreeRoots[index] == null) {  
                newTreeRoots[index] = new Entry<>(key, entry.getValue());  
            } else {  
                Entry<K, V> current = newTreeRoots[index];  
                while (true) {  
                    int comparison = current.key.compareTo(key);  
                    if (comparison == 0) {  
                        current.value = entry.getValue(); // replace value if different key with same hashcode found  
                        break;  
                    } else if (comparison < 0) {  
                        if (current.left == null) {  
                            current.left = new Entry<>(key, entry.getValue());  
                            break;  
                        } else {  
                            current = current.left;  
                        }  
                    } else { // comparison > 0  
                        if (current.right == null) {  
                            current.right = new Entry<>(key, entry.getValue());  
                            break;  
                        } else {  
                            current = current.right;  
                        }  
                    }  
                } 
            }   
        } 
        treeRoots = newTreeRoots; 
    }    
}

✔️put方法

对于put方法来说，一般经过以下几步：

1 . 如果数组没有被初始化，先初始化数组

2 . 首先通过定位到要 put 的 key 在哪个桶中，如果该桶中没有元素，则将该要 put的 entry 放置在该桶中

3 . 如果该桶中已经有元素，则遍历该桶所属的链表:
    a . 如果该链表已经树化，则执行红黑树的插入流程

    b . 如果仍然是链表，则执行链表的插入流程，如果插入后链表的长度大于等于8，并目桶数组的容量大于等于64，则执行链表的树化流程

    c . 注意: 在上面的步骤中，如果元素和要put的元素相同，则直接替换

4 . 校验是新增 KV 还是替换老的KV，如果是后者，则设置 callback 扩展(LinkedHashMap 的 LRU 即通过此实现)

5 . 校验 ++size 是否超过 threshold ，如果超过，则执行扩容流程 (见下会分解~)

读完文字，我们借助于代码片段捋一捋：

import java.util.HashMap;  
import java.util.Map;  

/**
*   @author xinbaobaba
*   一个简单的Demo，帮助理解HashMap在put操作时的基本步骤
*/  
public class HashMapPutExample {  
    public static void main(String[] args) {  
        // 创建一个新的HashMap对象  
        Map<String, Integer> map = new HashMap<>();  
  
        // 添加键值对到HashMap中  
        map.put("Alice", 25);  
        map.put("Bob", 30);  
        map.put("Charlie", 35);  
  
        // 输出原始HashMap的状态  
        System.out.println("Before modification:");  
        for (Map.Entry<String, Integer> entry : map.entrySet()) {  
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());  
        }  
  
        // 修改一个键对应的值  
        map.put("Alice", 30);  
  
        // 输出修改后的HashMap的状态  
        System.out.println("nAfter modification:");  
        for (Map.Entry<String, Integer> entry : map.entrySet()) {  
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());  
        }  
    }  
}

输出结果如下：

Before modification:  
Key: Alice, Value: 25  
Key: Bob, Value: 30  
Key: Charlie, Value: 35  
  
After modification:  
Key: Alice, Value: 30  
Key: Bob, Value: 30  
Key: Charlie, Value: 35

✔️ 拓展知识仓

✔️ HashMap如何定位key

先通过 (table.length - 1) & (key.hashCode ^ (key.hashCode >> 16)) 定位到 key 位于哪个table 中，然后再通过key.equals(rowKey)来判断两个key是否相同，综上，是先通过hashCode 和 equals 来定位 KEY 的。

源码如下：

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
	// ...省略
	if ((p = tab[i = (n - 1) & hash]) == null) {
		tab[i] = newNode(hash, key, value, null);
	} else {
		Node<K,V> e; K k;
		// 这里会通过equals判断
		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);
		}
	// ...省略
	return null:
	}
}

所以，在使用 HashMap 的时候，尽量用String 和 Enum 等已经实现过 hashCode和equals方法的官方库类，如果一定要自己的类，就一定要实现 hashCode和 equals 方法。

✔️ HashMap定位tablelndex的骚操作作

通过源码发现，hashMap 定位 tablelndex 的时候，是通过 (table.length - 1)& (key.hashCode ^ (key.hashCode >> 16)) ，而不是常规的key.hashCode % (table.length)呢?

1 . 为什么是用 & 而不是用 % :

答：因为 & 是基于内存的二进制直接运算，比转成十进制的取模快的多。以下运算等价: X % 2^n = X & (2^n - 1) 。这也是 hashMap 每次扩容都要到2^n的原因之一

2 . 为什么用 key.hash ^ (key.hash >> 16)而不是用key.hash:

答：这是因为增加了扰动计算，使得 hash分布的尽可能均匀。因为 hashCode 是 int 类型，虽然能映射40亿左右的空间，但是，HashMap 的table.length毕竟不可能有那么大，所以为了使 hash%table.length 之后，分布的尽可能均匀，就需要对实例的hashCode的值进行扰动，说白了，就是将hashCode的高16和低16位，进行异或使得hashCode的值更加分散一点。

✔️HashMap的key为null时，没有hashCode是如何存储的?

HashMap 对 key=null 的 case 做了特殊的处理，key值为 null 的 kv 对，总是会放在数组的第一个元素中，如下源码所示:

private V putForNulKey(V value) {
	for (Entry<K,V> e = table[0]; e != null; e = e.next)  {
		if (e.key == null) {
			V oldValue = e.value;
			e.value = value;
			e.recordAccess(this);
			return oldValue;
		}
	}
	
	modCount++;
	addEntry(0,null, value, 0);
	return null;
}


private V getForNul1Key()  {
	for (Entry<K,V> e = table[0]; e != null; e = e.next)  {
		if (e.key == null)
			return e.value;
	}
	return null;
}

✔️ HashMap的value可以为null吗? 有什么优缺点讷?

HashMap的kev和value都可以为null，优点很明显，不会因为调用者的粗心操作就抛出NPE这种RuntimeException，但是缺点也很隐蔽，就像下面的代码一样:

//调用远程RPC方法，获取map
Map<String，Object> map = remoteMethod.queryMap();
//如果包含对应key，则进行业务处理
if(map.contains(KEY)) {
	String value = (string)map.get(KEY);
	System.out.printIn(value );
}