HashMap在get和put时经过哪些步骤?
✔️ 典型解析
✔️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方法来说，一般经过以下几步：
读完文字，我们借助于代码片段捋一捋：
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的骚操作作
1 . 为什么是用 & 而不是用 % :
2 . 为什么用 key.hash ^ (key.hash >> 16)而不是用key.hash:
✔️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 );
}
虽然map.contains(key)，但是 map.get(key)==null，就会导致后面的业务逻辑出现NPE问题。