一、什么是 Map在 Java 集合体系中Map 是键值对Key-Value结构的集合。特点Key唯一Value可以重复通过Key 快速查找 Value示例MapString,Integer map new HashMap(); map.put(Tom,18); map.put(Jerry,20); System.out.println(map.get(Tom));数据结构Key - Value Tom - 18 Jerry- 20二、Map 集合体系结构Java 中 Map 的主要实现类Map │ ├── HashMap │ ├── LinkedHashMap │ └── WeakHashMap │ ├── TreeMap │ ├── Hashtable │ └── Properties │ └── ConcurrentHashMap常用实现类实现类特点HashMap最常用线程不安全LinkedHashMap有序TreeMap按 key 排序Hashtable线程安全过时ConcurrentHashMap高并发线程安全三、HashMap 底层数据结构JDK8 HashMap 结构数组 链表 红黑树结构示意数组 table │ ├── Node - Node - Node │ ├── Node - Node │ └── Node - 红黑树每个数组元素称为bucket桶四、HashMap 的核心属性源码简化transient NodeK,V[] table; transient int size; int threshold; final float loadFactor 0.75f;解释属性作用table存储数据数组size元素数量threshold扩容阈值loadFactor负载因子五、HashMap 的 put() 原理核心流程put(key,value) │ 计算 hash │ 计算数组下标 │ table[index] │ 是否为空 │ │ 为空 不为空 │ │ 直接插入 发生 hash 冲突 │ 链表 / 红黑树源码流程public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }核心步骤1 计算 hashhash key.hashCode() ^ (hash 16)目的减少 hash 冲突2 计算数组索引index (n - 1) hash例如n 16 index hash % 16使用位运算更快3 处理 hash 冲突三种情况1 数组为空 2 链表 3 红黑树流程数组 │ ├─ Node │ ├─ Node - Node - Node │ └─ Node - 红黑树六、HashMap 扩容机制重点默认容量16负载因子0.75扩容阈值threshold capacity * loadFactor默认16 * 0.75 12当size 12触发扩容。扩容流程1 创建新数组 2 容量变为原来2倍 3 重新计算hash 4 数据迁移扩容前16扩容后32七、JDK7 vs JDK8 HashMapJDK7结构数组 链表插入方式头插法示例A - B - C问题多线程扩容可能形成环形链表导致CPU 100%JDK8结构数组 链表 红黑树插入方式尾插法解决死循环问题八、为什么引入红黑树如果 Hash 冲突严重链表长度过长时间复杂度O(n)JDK8 优化链表 - 红黑树时间复杂度O(log n)红黑树转换条件链表长度 8并且数组长度 64源码TREEIFY_THRESHOLD 8 MIN_TREEIFY_CAPACITY 64流程链表长度 8 │ 数组长度 64 │ 优先扩容 │ 数组长度 64 │ 转红黑树九、Hash 冲突解决方式Hash 冲突两个 key hash 相同解决方式1 拉链法Java数组 链表示例index3 3 - A - B - C2 开放地址法Redis例如线性探测十、HashMap 为什么容量是 2 的幂例如16 32 64 128原因计算 index(n - 1) hash例如16 - 1111位运算效率高hash % 16等价于hash 15十一、HashMap 是否线程安全答案不安全问题1 数据覆盖A线程 put B线程 put可能size错误2 JDK7 死循环扩容时链表反转可能形成环形链表十二、ConcurrentHashMap 原理用于高并发环境JDK7 实现结构Segment HashEntry示意Segment │ ├── HashEntry ├── HashEntrySegment类似锁锁粒度Segment锁默认16段锁JDK8 实现重大优化结构数组 链表 红黑树和 HashMap 类似Node[]但是CAS synchronized插入流程1 CAS 插入 2 如果失败 3 synchronized优点锁粒度更小十三、HashMap 面试高频问题1 HashMap 底层结构数组 链表 红黑树2 为什么链表长度是 8 才变红黑树原因1 查询效率2 空间消耗3 性能平衡统计结果链表长度超过8概率极低3 为什么数组长度必须是2的幂原因(n-1) hash可以替代hash % n效率更高。4 HashMap 扩容什么时候触发条件size capacity * loadFactor默认16 * 0.75 125 HashMap 允许 null 吗HashMapkey 可以为 null value 可以为 nullHashtable不允许 null十四、Map 常用方法map.put(key,value) map.get(key) map.remove(key) map.containsKey(key) map.containsValue(value) map.keySet() map.values() map.entrySet()遍历方式entrySet推荐for(Map.EntryString,Integer entry : map.entrySet()){ System.out.println(entry.getKey() entry.getValue()); }效率最高。十五、总结Java Map 核心知识Map结构 │ HashMap │ 数组 链表 红黑树 │ hash算法 │ 扩容机制 │ 红黑树优化 │ ConcurrentHashMap并发控制
Java Map 集合深度解析（HashMap / ConcurrentHashMap 原理详解）
一、什么是 Map在 Java 集合体系中Map 是键值对Key-Value结构的集合。特点Key唯一Value可以重复通过Key 快速查找 Value示例MapString,Integer map new HashMap(); map.put(Tom,18); map.put(Jerry,20); System.out.println(map.get(Tom));数据结构Key - Value Tom - 18 Jerry- 20二、Map 集合体系结构Java 中 Map 的主要实现类Map │ ├── HashMap │ ├── LinkedHashMap │ └── WeakHashMap │ ├── TreeMap │ ├── Hashtable │ └── Properties │ └── ConcurrentHashMap常用实现类实现类特点HashMap最常用线程不安全LinkedHashMap有序TreeMap按 key 排序Hashtable线程安全过时ConcurrentHashMap高并发线程安全三、HashMap 底层数据结构JDK8 HashMap 结构数组 链表 红黑树结构示意数组 table │ ├── Node - Node - Node │ ├── Node - Node │ └── Node - 红黑树每个数组元素称为bucket桶四、HashMap 的核心属性源码简化transient NodeK,V[] table; transient int size; int threshold; final float loadFactor 0.75f;解释属性作用table存储数据数组size元素数量threshold扩容阈值loadFactor负载因子五、HashMap 的 put() 原理核心流程put(key,value) │ 计算 hash │ 计算数组下标 │ table[index] │ 是否为空 │ │ 为空 不为空 │ │ 直接插入 发生 hash 冲突 │ 链表 / 红黑树源码流程public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }核心步骤1 计算 hashhash key.hashCode() ^ (hash 16)目的减少 hash 冲突2 计算数组索引index (n - 1) hash例如n 16 index hash % 16使用位运算更快3 处理 hash 冲突三种情况1 数组为空 2 链表 3 红黑树流程数组 │ ├─ Node │ ├─ Node - Node - Node │ └─ Node - 红黑树六、HashMap 扩容机制重点默认容量16负载因子0.75扩容阈值threshold capacity * loadFactor默认16 * 0.75 12当size 12触发扩容。扩容流程1 创建新数组 2 容量变为原来2倍 3 重新计算hash 4 数据迁移扩容前16扩容后32七、JDK7 vs JDK8 HashMapJDK7结构数组 链表插入方式头插法示例A - B - C问题多线程扩容可能形成环形链表导致CPU 100%JDK8结构数组 链表 红黑树插入方式尾插法解决死循环问题八、为什么引入红黑树如果 Hash 冲突严重链表长度过长时间复杂度O(n)JDK8 优化链表 - 红黑树时间复杂度O(log n)红黑树转换条件链表长度 8并且数组长度 64源码TREEIFY_THRESHOLD 8 MIN_TREEIFY_CAPACITY 64流程链表长度 8 │ 数组长度 64 │ 优先扩容 │ 数组长度 64 │ 转红黑树九、Hash 冲突解决方式Hash 冲突两个 key hash 相同解决方式1 拉链法Java数组 链表示例index3 3 - A - B - C2 开放地址法Redis例如线性探测十、HashMap 为什么容量是 2 的幂例如16 32 64 128原因计算 index(n - 1) hash例如16 - 1111位运算效率高hash % 16等价于hash 15十一、HashMap 是否线程安全答案不安全问题1 数据覆盖A线程 put B线程 put可能size错误2 JDK7 死循环扩容时链表反转可能形成环形链表十二、ConcurrentHashMap 原理用于高并发环境JDK7 实现结构Segment HashEntry示意Segment │ ├── HashEntry ├── HashEntrySegment类似锁锁粒度Segment锁默认16段锁JDK8 实现重大优化结构数组 链表 红黑树和 HashMap 类似Node[]但是CAS synchronized插入流程1 CAS 插入 2 如果失败 3 synchronized优点锁粒度更小十三、HashMap 面试高频问题1 HashMap 底层结构数组 链表 红黑树2 为什么链表长度是 8 才变红黑树原因1 查询效率2 空间消耗3 性能平衡统计结果链表长度超过8概率极低3 为什么数组长度必须是2的幂原因(n-1) hash可以替代hash % n效率更高。4 HashMap 扩容什么时候触发条件size capacity * loadFactor默认16 * 0.75 125 HashMap 允许 null 吗HashMapkey 可以为 null value 可以为 nullHashtable不允许 null十四、Map 常用方法map.put(key,value) map.get(key) map.remove(key) map.containsKey(key) map.containsValue(value) map.keySet() map.values() map.entrySet()遍历方式entrySet推荐for(Map.EntryString,Integer entry : map.entrySet()){ System.out.println(entry.getKey() entry.getValue()); }效率最高。十五、总结Java Map 核心知识Map结构 │ HashMap │ 数组 链表 红黑树 │ hash算法 │ 扩容机制 │ 红黑树优化 │ ConcurrentHashMap并发控制
