HashMap 源码分析及面试题

HashMap概述

定义和特点

HashMap是Java集合框架中最常用的Map实现类，基于哈希表实现，提供了快速的键值对存储和检索功能。

主要特点：

• 允许null键和null值
• 非线程安全
• 不保证元素的插入顺序
• 基于哈希表实现，平均时间复杂度为O(1)
• 默认初始容量为16，负载因子为0.75

继承关系

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

时间复杂度分析

操作	平均时间复杂度	最坏时间复杂度
get	O(1)	O(n) / O(log n)
put	O(1)	O(n) / O(log n)
remove	O(1)	O(n) / O(log n)

注：JDK1.8引入红黑树后，最坏情况下时间复杂度从O(n)优化为O(log n)

底层数据结构

JDK1.7：数组 + 链表

数组索引    链表结构
[0] -----> Node1 -> Node2 -> Node3 -> null
[1] -----> null
[2] -----> Node4 -> Node5 -> null
[3] -----> Node6 -> null
...

特点：

• 使用数组存储桶（bucket）
• 每个桶使用链表解决哈希冲突
• 链表过长时查询效率降低（O(n)）

JDK1.8：数组 + 链表 + 红黑树

数组索引    数据结构
[0] -----> Node1 -> Node2 -> Node3 -> null (链表长度 < 8)
[1] -----> 红黑树根节点 (链表长度 >= 8 且数组长度 >= 64)
[2] -----> Node4 -> Node5 -> null
[3] -----> Node6 -> null
...

优化点：

• 当链表长度 >= 8 且数组长度 >= 64 时，链表转换为红黑树
• 当红黑树节点数 <= 6 时，红黑树退化为链表
• 红黑树查询时间复杂度为O(log n)

核心源码分析

重要字段

public class HashMap<K,V> extends AbstractMap<K,V> {
    // 默认初始容量 16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    // 默认负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    // 链表转红黑树的阈值
    static final int TREEIFY_THRESHOLD = 8;
    
    // 红黑树转链表的阈值
    static final int UNTREEIFY_THRESHOLD = 6;
    
    // 转红黑树时数组的最小长度
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    // 存储数据的数组
    transient Node<K,V>[] table;
    
    // 当前存储的键值对数量
    transient int size;
    
    // 扩容阈值 = capacity * loadFactor
    int threshold;
    
    // 负载因子
    final float loadFactor;
    
    // 修改次数，用于fail-fast机制
    transient int modCount;
}

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;           // 颜色
}

hash函数实现

static final int hash(Object key) {
    int h;
    // key为null时hash值为0
    // 否则使用key的hashCode()的高16位和低16位进行异或运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

设计思想：

• 高16位和低16位异或，增加随机性
• 减少哈希冲突，提高分布均匀性
• 保持高效性，只进行一次异或运算

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<K,V>[] tab; Node<K,V> p; int n, i;
    
    // 1. 如果table为空或长度为0，进行初始化
    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. 如果key已存在，记录该节点
        if (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)
                        treeifyBin(tab, hash);
                    break;
                }
                // 找到相同的key
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        // 6. 如果key已存在，更新value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    
    ++modCount;
    // 7. 检查是否需要扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

put方法执行流程：

1. 计算key的hash值
2. 根据hash值和数组长度计算索引：(n-1) & hash
3. 如果该位置为空，直接插入新节点
4. 如果该位置有节点：
   • 检查第一个节点是否匹配
   • 如果是红黑树，使用红黑树插入
   • 如果是链表，遍历链表查找或插入
5. 插入后检查链表长度，必要时转换为红黑树
6. 检查是否需要扩容

get方法详解

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

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    
    // 1. 检查table是否为空，计算索引位置
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        
        // 2. 检查第一个节点
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        
        // 3. 如果有后续节点
        if ((e = first.next) != null) {
            // 如果是红黑树，使用红黑树查找
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            
            // 如果是链表，遍历查找
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

resize扩容方法

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    if (oldCap > 0) {
        // 如果已达到最大容量，不再扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 容量和阈值都扩大2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1;
    }
    // ... 初始化逻辑
    
    threshold = newThr;
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    
    if (oldTab != null) {
        // 遍历旧数组，重新分配元素
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                
                // 如果只有一个节点，直接重新计算位置
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                
                // 如果是红黑树，分割红黑树
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                
                // 如果是链表，分割链表
                else {
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    
                    do {
                        next = e.next;
                        // 根据hash值的特定位判断新位置
                        if ((e.hash & oldCap) == 0) {
                            // 保持原位置
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            // 移动到原位置+oldCap
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    
                    // 将分割后的链表放入新数组
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

扩容机制特点：

• 扩容时机：size > threshold
• 扩容大小：原容量的2倍
• 元素重新分布：利用hash值的特定位判断新位置
• 优化：避免重新计算hash值，提高扩容效率

JDK版本差异

JDK1.7 vs JDK1.8 主要区别

特性	JDK1.7	JDK1.8
数据结构	数组+链表	数组+链表+红黑树
插入方式	头插法	尾插法
hash计算	4次位运算+5次异或	1次位运算+1次异或
扩容时机	插入前检查	插入后检查
线程安全问题	可能形成环形链表	避免了环形链表

详细对比

1. 数据结构优化

JDK1.7问题：

• 链表过长时查询效率低（O(n)）
• 极端情况下退化为链表

JDK1.8优化：

• 引入红黑树，最坏情况下时间复杂度O(log n)
• 动态转换：链表 ↔ 红黑树

2. 插入方式改进

JDK1.7头插法问题：

// 头插法可能导致环形链表
void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e); // 新节点指向原头节点
}

JDK1.8尾插法优势：

• 避免环形链表问题
• 保持插入顺序
• 扩容时更安全

3. hash函数优化

JDK1.7：

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

JDK1.8：

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

优化效果：

• 减少计算量，提高性能
• 保持良好的散列特性

性能分析与优化

负载因子分析

为什么默认负载因子是0.75？

1. 空间与时间的平衡

   • 负载因子过小：浪费空间，但冲突少
   • 负载因子过大：节省空间，但冲突多

2. 泊松分布理论

   • 当负载因子为0.75时，链表长度超过8的概率约为0.00000006
   • 这是一个理论和实践的最佳平衡点

初始容量设置建议

// 如果预知存储元素数量，建议设置合适的初始容量
// 初始容量 = 预期元素数量 / 负载因子 + 1
int expectedSize = 1000;
int initialCapacity = (int) (expectedSize / 0.75f) + 1;
Map<String, String> map = new HashMap<>(initialCapacity);

性能优化建议

1. 合理设置初始容量

   • 避免频繁扩容
   • 减少内存重新分配

2. 选择合适的key类型

   • 重写hashCode()和equals()方法
   • 保证hash值分布均匀

3. 避免hash冲突

   • 使用质量好的hash函数
   • 避免使用容易冲突的key

4. 并发场景使用ConcurrentHashMap

   • HashMap非线程安全
   • 多线程环境使用专门的并发集合

常见面试题

基础概念类

Q1: HashMap的底层实现原理是什么？

答案： HashMap基于哈希表实现，使用数组存储桶（bucket），通过hash函数将key映射到数组索引。JDK1.8中采用"数组+链表+红黑树"的结构：

• 数组：存储桶的容器
• 链表：解决hash冲突
• 红黑树：当链表长度>=8且数组长度>=64时，链表转换为红黑树，提高查询效率

Q2: 为什么HashMap不是线程安全的？

答案：

1. 数据竞争：多线程同时修改可能导致数据不一致
2. 扩容问题：JDK1.7中可能形成环形链表导致死循环
3. size计数：并发修改size字段可能不准确
4. fail-fast机制：并发修改会抛出ConcurrentModificationException

Q3: HashMap和HashTable的区别？

答案：

特性	HashMap	HashTable
线程安全	非线程安全	线程安全（synchronized）
null值	允许null键和值	不允许null键和值
继承关系	继承AbstractMap	继承Dictionary
初始容量	16	11
扩容方式	2倍扩容	2倍+1扩容
性能	高	低（同步开销）

Q4: HashMap和ConcurrentHashMap的区别？

答案：

• 线程安全：ConcurrentHashMap是线程安全的，HashMap不是
• 锁机制：ConcurrentHashMap使用分段锁（JDK1.7）或CAS+synchronized（JDK1.8）
• 性能：ConcurrentHashMap在并发环境下性能更好
• null值：ConcurrentHashMap不允许null键和值

源码实现类

Q5: HashMap的put过程是怎样的？

答案：

1. 计算key的hash值：hash(key)
2. 根据hash值计算数组索引：(n-1) & hash
3. 检查该位置是否为空：
   • 为空：直接插入新节点
   • 不为空：处理hash冲突
4. 处理hash冲突：
   • 检查第一个节点是否匹配
   • 如果是红黑树，使用红黑树插入
   • 如果是链表，遍历链表查找或插入到尾部
5. 检查链表长度，>=8时转换为红黑树
6. 插入后size++，检查是否需要扩容

Q6: HashMap的扩容机制是什么？

答案： 扩容时机：当size > threshold时触发扩容

扩容过程：

1. 创建新数组，容量为原来的2倍
2. 重新计算threshold
3. 遍历旧数组，重新分配所有元素
4. 利用(e.hash & oldCap) == 0判断元素新位置：
   • 等于0：保持原位置
   • 不等于0：移动到原位置+oldCap

优化点：

• 避免重新计算hash值
• 保持链表顺序，避免环形链表

Q7: 为什么链表长度超过8要转红黑树？

答案：

1. 性能考虑：链表查询时间复杂度O(n)，红黑树O(log n)
2. 概率分析：根据泊松分布，负载因子0.75时链表长度超过8的概率极小
3. 平衡考虑：红黑树节点占用空间更大，只在必要时转换
4. 动态调整：当红黑树节点<=6时退化为链表

Q8: HashMap如何解决hash冲突？

答案： HashMap使用链地址法解决hash冲突：

1. 链表：相同hash值的元素形成链表
2. 红黑树：链表过长时转换为红黑树
3. hash函数优化：使用高低位异或增加随机性
4. 扩容：通过扩容减少冲突概率

性能优化类

Q9: HashMap在什么情况下会出现死循环？

答案： 仅在JDK1.7中存在，JDK1.8已修复。

产生原因：

1. 多线程并发扩容
2. 头插法导致链表顺序颠倒
3. 形成环形链表
4. get操作时无限循环

示例场景：

// 线程1和线程2同时扩容
// 原链表：A -> B -> null
// 扩容后可能形成：A -> B -> A（环形链表）

JDK1.8解决方案：

• 使用尾插法
• 保持链表顺序
• 避免环形链表

Q10: 如何减少HashMap的hash冲突？

答案：

1. 选择好的hash函数：

   // 重写hashCode方法，保证分布均匀
   @Override
   public int hashCode() {
       return Objects.hash(field1, field2, field3);
   }
   

2. 合理设置初始容量：

   // 避免频繁扩容
   int capacity = (int) (expectedSize / 0.75f) + 1;
   Map<K, V> map = new HashMap<>(capacity);
   

3. 使用质量好的key：

   • 避免使用容易冲突的key
   • 保证hashCode和equals的一致性

4. 考虑使用其他Map实现：

   • LinkedHashMap：保持插入顺序
   • TreeMap：基于红黑树，有序

实际应用类

Q11: HashMap可以存储null值吗？

答案： 可以，HashMap允许一个null键和多个null值：

Map<String, String> map = new HashMap<>();
map.put(null, "value1");     // 允许null键
map.put("key1", null);       // 允许null值
map.put("key2", null);       // 允许多个null值

System.out.println(map.get(null));  // 输出：value1

注意事项：

• null键的hash值为0，存储在数组索引0位置
• ConcurrentHashMap不允许null键和值
• HashTable不允许null键和值

Q12: 自定义对象作为HashMap的key需要注意什么？

答案： 必须正确重写hashCode()和equals()方法：

public class Person {
    private String name;
    private int age;
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Person person = (Person) obj;
        return age == person.age && Objects.equals(name, person.name);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

重要原则：

1. 一致性：equals相等的对象必须有相同的hashCode
2. 稳定性：对象的hashCode在其生命周期内不应改变
3. 分布性：hashCode应该尽可能分布均匀

Q13: HashMap的遍历方式有哪些？性能如何？

答案：

Map<String, String> map = new HashMap<>();

// 1. 遍历键值对（推荐）
for (Map.Entry<String, String> entry : map.entrySet()) {
    String key = entry.getKey();
    String value = entry.getValue();
}

// 2. 遍历键
for (String key : map.keySet()) {
    String value = map.get(key);  // 额外的查找开销
}

// 3. 遍历值
for (String value : map.values()) {
    // 只能获取值，无法获取对应的键
}

// 4. 使用Iterator
Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<String, String> entry = iterator.next();
    // 可以安全删除元素
    iterator.remove();
}

// 5. Java 8 Stream API
map.entrySet().stream()
   .filter(entry -> entry.getValue().length() > 5)
   .forEach(entry -> System.out.println(entry.getKey()));

性能对比：

1. entrySet()遍历：最高效，只需一次遍历
2. keySet()遍历：需要额外的get()调用，性能较差
3. values()遍历：适合只需要值的场景

Q14: HashMap在多线程环境下会出现什么问题？

答案：

1. 数据不一致：

   // 线程1
   map.put("key", "value1");
   
   // 线程2
   map.put("key", "value2");
   
   // 最终结果不确定
   

2. size计数错误：

   // 并发put操作可能导致size计数不准确
   // 实际元素数量与size()返回值不一致
   

3. 无限循环（JDK1.7）：

   • 并发扩容导致环形链表
   • get操作陷入死循环

4. ConcurrentModificationException：

   for (String key : map.keySet()) {
       map.put("newKey", "newValue");  // 抛出异常
   }
   

解决方案：

• 使用ConcurrentHashMap
• 使用Collections.synchronizedMap()
• 外部同步控制

总结

HashMap是Java中最重要的集合类之一，理解其实现原理对于Java开发者至关重要：

核心要点

1. 数据结构：数组+链表+红黑树的混合结构
2. hash算法：高低位异或，提高分布均匀性
3. 冲突解决：链地址法，链表转红黑树优化
4. 扩容机制：2倍扩容，巧妙的元素重分布算法
5. 版本演进：JDK1.8相比1.7有重大优化

使用建议

1. 合理设置初始容量，避免频繁扩容
2. 正确实现hashCode和equals，确保key的正确性
3. 多线程环境使用ConcurrentHashMap
4. 遍历时使用entrySet()，性能最优
5. 避免在遍历时修改集合，防止异常

面试重点

• 底层实现原理和数据结构
• put/get方法的执行流程
• 扩容机制和hash冲突解决
• JDK版本差异和优化点
• 线程安全问题和解决方案
• 性能优化和最佳实践

掌握这些知识点，不仅能够在面试中游刃有余，更能在实际开发中正确高效地使用HashMap。