当前位置：首页 > news >正文

HashMap源码分析：put与get方法详解

news 2025/7/10 11:09:47

引言

HashMap是Java集合框架中最重要且最常用的数据结构之一，它提供了高效的键值对存储和检索功能。本文将深入分析HashMap的核心方法——put和get的源码实现，帮助开发者更好地理解HashMap的内部工作机制。

HashMap基本结构

在深入方法分析之前，我们先了解HashMap的基本结构：

- HashMap基于哈希表实现，使用数组+链表+红黑树（JDK8+）的结构
- 默认初始容量为16，负载因子为0.75
- 当链表长度超过8且数组长度大于64时，链表会转换为红黑树

put方法源码分析

put方法入口

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

put方法调用了putVal方法，其中`hash(key)`计算了key的哈希值。

hash方法

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

hash方法通过将key的hashCode高16位与低16位进行异或运算，增加了哈希值的随机性，减少了哈希冲突。

putVal方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;// 步骤1：如果table为空或长度为0，则进行resize初始化if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 步骤2：计算索引位置，如果该位置为空，直接创建新节点if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;// 步骤3：节点已存在，判断是否为相同keyif (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 步骤4：判断是否为树节点else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 步骤5：处理链表情况else {for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);// 链表长度超过8，转换为红黑树if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}// 找到相同key的节点if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 步骤6：key已存在，替换valueif (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;// 步骤7：检查是否超过阈值，需要扩容if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}

putVal方法的主要步骤：

1. 检查并初始化table数组
2. 计算索引位置，如果该位置为空，直接创建新节点
3. 如果该位置已有节点，判断是否为相同key
4. 如果是树节点，调用树节点的插入方法
5. 如果是链表，遍历链表查找相同key或插入到链表末尾
6. 如果找到相同key，替换value
7. 检查是否需要扩容

get方法源码分析

get方法入口

public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}

get方法同样先计算key的哈希值，然后调用getNode方法。

getNode方法

final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;// 步骤1：table不为空且长度大于0且索引位置有节点if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {// 步骤2：检查第一个节点是否匹配if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;// 步骤3：检查后续节点if ((e = first.next) != null) {// 步骤4：如果是树节点，调用树查找if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);// 步骤5：遍历链表查找do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;
}

getNode方法的主要步骤：

1. 检查table数组是否初始化且索引位置是否有节点
2. 检查第一个节点是否匹配
3. 如果有后续节点，继续查找
4. 如果是树节点，调用树查找方法
5. 如果是链表，遍历链表查找匹配节点