18.2.1 HashMap底层实现原理（JDK7 vs JDK8）
1. HashMap基本概念
1.1 HashMap简介
HashMap是基于哈希表实现的Map接口的非同步实现，允许使用null值和null键，是Java中最常用的集合类之一。
1.2 核心特点
- 基于数组+链表/红黑树实现
- 允许null键和null值
- 非线程安全
- 不保证元素顺序
- 平均时间复杂度O(1)
2. JDK7中的HashMap实现
2.1 数据结构
JDK7中HashMap采用数组+链表的结构，即"拉链法"解决哈希冲突。
// JDK7 HashMap核心数据结构
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V> {
// 默认初始容量16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 存储数据的数组
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
// 实际存储的键值对数量
transient int size;
// 扩容阈值 = capacity * loadFactor
int threshold;
// 负载因子
final float loadFactor;
// Entry节点结构
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next; // 指向下一个节点
int hash; // 缓存的hash值
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
}
}
2.2 JDK7的put操作流程
public class JDK7HashMapPutProcess {
// JDK7 put方法简化实现
public V put(K key, V value) {
// 1. 如果table为空，初始化
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 2. 处理null key
if (key == null)
return putForNullKey(value);
// 3. 计算hash值
int hash = hash(key);
// 4. 计算数组索引
int i = indexFor(hash, table.length);
// 5. 遍历链表，查找是否存在相同key
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value; // 更新value
return oldValue;
}
}
// 6. 添加新节点
addEntry(hash, key, value, i);
return null;
}
// 计算hash值
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// 扰动函数，增加随机性
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
// 计算数组索引
static int indexFor(int h, int length) {
return h & (length-1); // 等价于 h % length，但更高效
}
// 添加新Entry
void addEntry(int hash, K key, V value, int bucketIndex) {
// 检查是否需要扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length); // 扩容为原来的2倍
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
// 创建新Entry，头插法
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e); // 头插法
size++;
}
}
2.3 JDK7的扩容机制
public class JDK7ResizeProcess {
// JDK7扩容方法
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 创建新数组
Entry[] newTable = new Entry[newCapacity];
// 数据迁移
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
// 数据迁移，头插法可能导致环形链表
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next; // 保存下一个节点
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i]; // 头插法
newTable[i] = e;
e = next;
}
}
}
}
2.4 JDK7的问题
public class JDK7Problems {
// 问题1: 头插法导致的环形链表问题
public void demonstrateCircularList() {
// 在多线程环境下，扩容时的头插法可能导致环形链表
// 线程A和线程B同时执行transfer方法
// 可能出现 e1.next = e2, e2.next = e1 的情况
// 导致死循环
}
// 问题2: 链表过长导致性能下降
public void demonstrateLongChain() {
Map<Integer, String> map = new HashMap<>();
// 构造hash冲突的key
for (int i = 0; i < 100000; i++) {
// 假设这些key都hash到同一个桶中
map.put(new BadHashKey(i), "value" + i);
}
// 查找时需要遍历整个链表，时间复杂度O(n)
String value = map.get(new BadHashKey(50000));
}
// 故意设计hash冲突的key
static class BadHashKey {
private int value;
public BadHashKey(int value) {
this.value = value;
}
@Override
public int hashCode() {
return 1; // 所有对象都返回相同的hash值
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
BadHashKey that = (BadHashKey) obj;
return value == that.value;
}
}
}
3. JDK8中的HashMap实现
3.1 数据结构优化
JDK8中HashMap采用数组+链表+红黑树的结构，当链表长度超过阈值时转换为红黑树。
// JDK8 HashMap核心数据结构
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V> {
// 树化阈值：链表长度超过8时转换为红黑树
static final int TREEIFY_THRESHOLD = 8;
// 反树化阈值：红黑树节点少于6时转换为链表
static final int UNTREEIFY_THRESHOLD = 6;
// 最小树化容量：只有数组长度大于64时才会树化
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储数据的数组
transient Node<K,V>[] table;
// Node节点结构
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
// 红黑树节点结构
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 父节点
TreeNode<K,V> left; // 左子节点
TreeNode<K,V> right; // 右子节点
TreeNode<K,V> prev; // 前驱节点
boolean red; // 颜色标识
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
}
3
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
Java面试圣经 文章被收录于专栏
Java面试圣经，带你练透java圣经
