背景介绍
在理解Java容器中Map的源码之前，我们需要先了解Map的基本概念。Map是一种键值对的数据结构，它可以存储多个键值对，每个键值对由一个唯一的键和对应的值组成。在Java中，Map接口是用来定义Map的基本操作的，而具体的实现类有很多，如HashMap、LinkedHashMap、TreeMap等。
Map的源码分析有助于我们深入了解Java集合类的底层实现原理，从而更好地使用和优化Map的操作。
HashMap的源码分析
HashMap是常用的Map实现类，它使用哈希表来存储键值对。下面我们来分析HashMap的源码。
- HashMap的数据结构：
class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
static class Node implements Map.Entry {
final int hash; // 键的哈希值
final K key; // 键
V value; // 值
Node next; // 下一个节点
}
}
- HashMap的初始化大小和负载因子：
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) // 最大容量限制
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity); // 计算扩容阈值
}
- HashMap的put方法：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; // 哈希表
Node 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);
else {
Node 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)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) // 链表转红黑树的阈值
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) // 判断键是否相同
break;
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold) // 判断是否需要扩容
resize();
afterNodeInsertion(evict);
return null;
}
ConcurrentHashMap的源码分析
ConcurrentHashMap是线程安全的HashMap实现类，它通过分段锁（Segment）来实现并发访问，提高了并发性能。
- ConcurrentHashMap的数据结构：
class ConcurrentHashMap extends AbstractMap implements ConcurrentMap, Serializable {
static final class Node implements Map.Entry {
final int hash; // 键的哈希值
final K key; // 键
volatile V val; // 值
volatile Node next; // 下一个节点
}
static final class Segment extends ReentrantLock implements Serializable {
transient volatile ConcurrentHashMap.Node[] table; // 哈希表
transient int count; // 元素数量
}
}
- ConcurrentHashMap的put方法：
public V put(K key, V value) {
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null)
throw new NullPointerException();
int hash = spread(key.hashCode()); // 计算哈希值
int binCount = 0;
for (ConcurrentHashMap.Node[] tab = table;;) {
ConcurrentHashMap.Node f;
int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // 计算插入位置
if (casTabAt(tab, i, null, new ConcurrentHashMap.Node(hash, key, value, null)))
break;
}
else if ((fh = f.hash) == MOVED) // 判断是否扩容
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) { // 锁节点
if (tabAt(tab, i) == f) {
if (fh >= 0) { // 链表处理
binCount = 1;
for (ConcurrentHashMap.Node e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key || (ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
ConcurrentHashMap.Node pred = e;
if ((e = e.next) == null) {
pred.next = new ConcurrentHashMap.Node(hash, key, value, null);
break;
}
}
}
else if (f instanceof TreeBin) { // 红黑树处理
ConcurrentHashMap.Node p;
binCount = 2;
if ((p = ((TreeBin)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD) // 链表转红黑树的阈值
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount); // 更新元素数量
return null;
}
总结
源码分析可以帮助我们深入了解Java容器中Map的实现原理和底层数据结构，有助于我们更好地使用和优化Map的操作。通过分析HashMap和ConcurrentHashMap的源码，我们可以了解到它们的数据结构、初始化过程以及put操作的实现原理。这些知识对于我们在实际开发中选择适当的Map实现类、合理设置参数以及优化Map的性能都很重要。