为什么你天天用 Map，却从来没想过它脑子里在想啥？

开篇语

哈喽，各位小伙伴们，你们好呀，我是喵手。运营社区：C站/掘金/腾讯云/阿里云/华为云/51CTO；欢迎大家常来逛逛

  今天我要给大家分享一些自己日常学习到的一些知识点，并以文字的形式跟大家一起交流，互相学习，一个人虽可以走的更快，但一群人可以走的更远。

  我是一名后端开发爱好者，工作日常接触到最多的就是Java语言啦，所以我都尽量抽业余时间把自己所学到所会的，通过文章的形式进行输出，希望以这种方式帮助到更多的初学者或者想入门的小伙伴们，同时也能对自己的技术进行沉淀，加以复盘，查缺补漏。

小伙伴们在批阅的过程中，如果觉得文章不错，欢迎点赞、收藏、关注哦。三连即是对作者我写作道路上最好的鼓励与支持！

摘要

说实话，Map 大概是我们写 Java 代码最常用的集合之一了：缓存、配置、统计、索引……几乎没它不行的场景。但尴尬的是——很多人只是“会用”，却对它的底层结构一知半解：
  HashMap 到底怎么定位下标？为什么 JDK 1.8 要搞个红黑树？ConcurrentHashMap 的锁到底锁在哪儿？LinkedHashMap 凭什么能做 LRU？TreeMap 的红黑树到底红在哪、黑在哪？

今天咱就搞一篇**“从会用到真正懂 Map”**的长文，边聊底层原理，边用实际代码例子串起来，顺带加点吐槽和感情，让这一票知识彻底长在你脑子里。🧠✨

一、别急着上来就怼 HashMap，先把 Map 这个家族看明白

先简单压一压阵地：Map<K, V> 是个键值对容器，用 key 查 value，典型操作就是：

• put(K key, V value)：塞东西
• get(Object key)：拿东西
• remove(Object key)：扔东西
• containsKey(Object key)：在不在
• 还有一堆遍历：keySet()、values()、entrySet() 等。

但真正让人眼花缭乱的是实现类：

• HashMap：无序，速度快，线程不安全，用得最多。
• ConcurrentHashMap：线程安全版，专门干并发场景。
• LinkedHashMap：有顺序（插入顺序或访问顺序），经常用来实现 LRU。
• TreeMap：有序（按 key 排序），底层红黑树，适合各种“区间查询”“范围查找”。

它们的关系可以粗暴一点理解：

如果你只想“快点查”，选 HashMap；
多线程又想“快点查”，选 ConcurrentHashMap；
想“按访问顺序淘汰元素”，选 LinkedHashMap；
想“按大小排序、区间查找”，选 TreeMap。

接下来重点来了——HashMap & ConcurrentHashMap & LinkedHashMap & TreeMap 一条龙捋完。🚀

二、HashMap：从 1.7 到 1.8，它到底经历了什么？

1. 底层结构对比：1.7 vs 1.8

JDK 1.7：数组 + 链表

早年的 HashMap 结构很朴素：

table（数组）: Entry<K,V>[]

每个下标 bucket：单向链表

• 用 hash(key) 定位到数组下标；
• 冲突了就挂链表（头插法）；
• 链表长了会变慢（退化为 O(n) 查找）。

JDK 1.8：数组 + 链表 + 红黑树

1.8 之后，结构升级了：

table: Node<K,V>[]

桶(bucket) 里可能是：
- 单向链表，或
- 红黑树 (TreeNode)，当冲突太多时树化

当某个桶里的元素太多，链表太长，查找退化得太厉害，就把链表转换为红黑树，时间复杂度从 O(n) → O(log n)。

2. 扰动函数 + 索引计算：index = (n - 1) & hash

HashMap 里最容易被忽略的一个小细节，就是扰动函数和下标计算。简单说：

1. 拿到 key.hashCode()；
2. 做个“扰动”混一混高位和低位，减少 hash 冲突；
3. 再用数组长度算 index。

JDK 1.8 里面大概是这么个意思（源码简化版）：

// 扰动函数（简化）
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 计算数组下标
int index = (n - 1) & hash; // n 是 table.length，并且是 2 的幂

为啥用 (n - 1) & hash 这么怪的写法？

• 因为 n 是 2 的幂，那么 n-1 的二进制全是 1，比如：

  • 16 = 10000₂ → 16 - 1 = 1111₂

• 与 hash 做 &，相当于只取 hash 的低几位，等价于 hash % n，但位运算更快。

一句话：扰动函数是为了让 hash 分布更均匀，& 是为了更快取模。

3. 扩容机制 & 负载因子：时间 vs 空间的取舍

HashMap 有几个核心参数：

• 初始容量：默认 16
• 负载因子 loadFactor：默认 0.75
• 阈值 threshold = capacity * loadFactor

当 size > threshold 的时候，就会触发扩容（resize），容量变成 原来的 2 倍。

扩容时发生了啥？

JDK 1.8 的扩容做了个非常实用的小优化：

• 扩容前：容量 = oldCap
• 扩容后：容量 = newCap = oldCap * 2

这时对于桶中每个节点，要么留在原索引，要么移动到 index + oldCap。因为：

新 index = hash & (newCap - 1)
旧 index = hash & (oldCap - 1)

而 newCap = oldCap * 2

对同一个 hash 来说，只多出了一位高位参与 & 运算，最终要么保持不变，要么多一个 oldCap。这减少了重算 hash 的开销。

负载因子到底在权衡啥？

• 负载因子越大 → 空间利用率更高，但冲突多，对性能不利；
• 负载因子越小 → 空间浪费一点，但冲突少，性能好。

默认 0.75 是一个折中：工程实践里验证过“还不错”的一个选择。除非你特别清楚自己场景，一般别乱改。

4. 为什么红黑树的阈值是 8？

这个阈值是大家最爱问的问题之一：为啥链表长度达到 8 才树化？为什么不是 7，也不是 10？

粗暴一点说，这是一个概率 + 内存 + 性能的综合工程权衡：

1. 概率层面

   • 理论上，如果 hash 分布均匀，在负载因子 0.75 的情况下，某一个桶里元素超过 8 的概率非常非常低。
   • 也就是说，当链表长度真的超过 8，很大概率说明：这个 hash 值不太均匀 / key 本身分布有问题，这时才有必要上红黑树。

2. 内存 & 实现成本

   • 红黑树的节点比链表节点更“胖”（要存 parent、left、right、color 等），在元素数量少的时候，链表其实更划算。
   • 如果你动不动就树化，那就是为了性能可能还没提升多少，先把内存浪费一通。

3. 避免频繁在“树”和“链表”之间抖来抖去

   • JDK 里还定义了一个 UNTREEIFY_THRESHOLD = 6，当树退化后小于这个值，就从树退回链表。
   • 8 和 6 中间留了个缓冲，避免刚树化就又退回，来回折腾。

综合下来，8 是一个比较折中的经验值：不那么容易触发，但一旦触发，多半是真有问题，值得你为它上红黑树。

5. 一个 HashMap 实战小例子：看得见底层行为

来段简单演示代码，顺带看看冲突、扩容、树化触发点（当然实际运行要看 JDK 实现细节，仅作演示）：

import java.util.HashMap;
import java.util.Map;

public class HashMapDemo {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>(16, 0.75f);

        for (int i = 0; i < 20; i++) {
            map.put(i, "value-" + i);
        }

        System.out.println("size = " + map.size());
        System.out.println("map = " + map);
    }
}

如果你想真的感受扩容和 hash 分布，可以自己写几个 key，让它们的 hashCode() 有意冲突，看看实际表现，会很有感觉。

三、ConcurrentHashMap：从“分段锁”到 CAS + synchronized 的进化

单线程世界很美好，只可惜现实不是。多线程一来，HashMap 直接崩：

• 不是数据覆盖，就是死循环（JDK 1.7 中多线程扩容时可能形成环形链表）
• 所以我们需要一个线程安全的 Map，但又不想锁得太狠——这就是 ConcurrentHashMap 出场的理由。

1. JDK 1.7：Segment 分段锁

1.7 中的 ConcurrentHashMap 底层结构是这样的：

Segment<K,V>[] segments  // 每个 Segment 里有一个小的 HashMap
Segment 继承 ReentrantLock，实现“分段锁”

简单说：

• 整个大 Map 被切成 N 段（默认 16 段）；
• 每一段维护自己的数组 + 链表；
• 对某个 key 的操作，只会锁住对应的 Segment，而不是整个 Map。

好处：

• 并发度最多达到 “segment 数量”；
• 多线程场景下比 Collections.synchronizedMap() 这种粗暴的全局锁快很多。

缺点：

• 结构复杂；
• 扩容时每个 Segment 自己扩，管理起来比较麻烦；
• 读操作虽然基本无锁，但整体设计比较“老”了。

2. JDK 1.8：CAS + synchronized + Node[]

到了 1.8，ConcurrentHashMap 结构大升级，思路更接近 HashMap 1.8：

• 整体就是一个 Node<K,V>[] table，不再有 Segment；
• 使用 CAS + volatile + synchronized 组合拳来保证线程安全。

典型写入逻辑（简化理解版）：

1. 如果 table 还没初始化，用 CAS 初始化；

2. 根据 hash 算 index；

3. 如果这个桶是空的，直接 CAS 放进去；

4. 如果不空：

   • 如果是链表，使用 synchronized 锁住链表头节点，然后插入；
   • 如果是红黑树，锁住树的根节点，然后插入；

5. 在扩容时，使用一个“转发节点”标记正在迁移，线程一起参与搬迁。

来个简单的并发 demo，感受一下使用方式（不是为了性能基准，只是用法展示）：

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CountDownLatch;

public class CHMDemo {
    public static void main(String[] args) throws InterruptedException {
        Map<String, Integer> counter = new ConcurrentHashMap<>();
        int threadCount = 10;
        CountDownLatch latch = new CountDownLatch(threadCount);

        for (int i = 0; i < threadCount; i++) {
            new Thread(() -> {
                for (int j = 0; j < 1000; j++) {
                    // 原子更新计数
                    counter.merge("hit", 1, Integer::sum);
                }
                latch.countDown();
            }).start();
        }

        latch.await();
        System.out.println("hit = " + counter.get("hit")); // 期望值 = 10 * 1000 = 10000
    }
}

多线程场景下，ConcurrentHashMap 是你的首选：读多写少、高并发访问 的场景里它非常好用。

四、LinkedHashMap：两行代码写个 LRU 缓存，香不香？🔥

很多人第一次看到 LRU 缓存实现的时候，惊叹一句：“就这？就这就能做 LRU？！”

1. LinkedHashMap 的结构

LinkedHashMap 的底层其实很简单：

• 它继承了 HashMap；

• 额外维护了一条 双向链表 来记录元素顺序；

• 这个顺序可以是：

  • 插入顺序（默认），或者
  • 访问顺序（accessOrder = true）。

2. LRU 核心：按访问顺序 + 覆盖 removeEldestEntry

直接上代码，看完你会觉得“这玩意儿再不背下来就说不过去了”：

import java.util.LinkedHashMap;
import java.util.Map;

public class LruCache<K, V> extends LinkedHashMap<K, V> {

    private final int capacity;

    public LruCache(int capacity) {
        // accessOrder = true 表示按访问顺序排序
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // 当 size 超过容量时，自动删除最“旧”的那个
        return size() > capacity;
    }

    public static void main(String[] args) {
        LruCache<Integer, String> cache = new LruCache<>(3);
        cache.put(1, "A");
        cache.put(2, "B");
        cache.put(3, "C");

        // 访问一下 1，让 1 变“新”
        cache.get(1);

        // 插入一个新元素，会淘汰掉最久未使用的：键 2
        cache.put(4, "D");

        System.out.println(cache); // 可能输出：{3=C, 1=A, 4=D}
    }
}

这几行代码干了啥？

1. accessOrder = true：每次访问（get / put）都会把当前 entry 移到链表尾部；
2. removeEldestEntry：每次插入后都会被调用，true 就把头部（最老）的 entry 删掉；
3. 一减一加，典型的 LRU 行为就实现了。

所以很多系统里，简单又好用的本地缓存，都是直接拿 LinkedHashMap 加一层封装就搞定了。

五、TreeMap：红黑树这个“秩序狂魔”

如果你需要：

• 按 key 排序；
• 找“大于等于某个 key 的第一个值”；
• 做 “区间查询”（例如查 10 <= key < 20）；

那 TreeMap 基本就是标配了。

1. TreeMap 底层：红黑树

TreeMap 的底层是红黑树（Red-Black Tree），一个近似平衡的二叉搜索树。它主要遵守这几条规则（简化版）：

1. 每个节点要么是红色，要么是黑色；
2. 根节点是黑色；
3. 红节点不能连续（红节点的子节点必须是黑色）；
4. 从任意节点到其所有叶子节点的路径上，黑节点数量相同。

这些规则保证了：树的高度是 O(log n)，查找、插入、删除都不会退化到链表那种鬼样子。

2. TreeMap 小实战：做个“分段收费表”

比如我们有一个“分段收费规则”：

• 0 ~ 99：基础会员
• 100 ~ 499：高级会员
• 500 ~ +∞：至尊会员

用 TreeMap<Integer, String> 表示门槛到等级的映射：

import java.util.NavigableMap;
import java.util.TreeMap;

public class TreeMapDemo {
    public static void main(String[] args) {
        NavigableMap<Integer, String> levelMap = new TreeMap<>();

        levelMap.put(0, "基础会员");
        levelMap.put(100, "高级会员");
        levelMap.put(500, "至尊会员");

        System.out.println(getLevel(levelMap, 50));   // 基础会员
        System.out.println(getLevel(levelMap, 300));  // 高级会员
        System.out.println(getLevel(levelMap, 1000)); // 至尊会员
    }

    public static String getLevel(NavigableMap<Integer, String> levelMap, int score) {
        // floorEntry：找到小于等于 score 的最大 key
        Map.Entry<Integer, String> entry = levelMap.floorEntry(score);
        return entry != null ? entry.getValue() : "无等级";
    }
}

这类“区间映射”的场景用 TreeMap 特别顺手，红黑树的有序特性帮了大忙。

六、到底什么时候该选谁？一句一句掰开说

说了这么多理论，最后回到最现实的问题：我到底该用哪个 Map？

你可以按下面这几条“土办法”来选：

1. 单线程 or 只在局部使用？

   • 选 HashMap，好用又快。

2. 多线程共享、读多写少？

   • 选 ConcurrentHashMap。
   • 如果还需要做复杂的组合操作，可以配合 compute / merge 等方法。

3. 需要“最近最少使用”淘汰策略？

   • 选 LinkedHashMap，加上 accessOrder=true + removeEldestEntry，一个 LRU 搞定。

4. 需要按 key 排序、或者做范围查询？

   • 选 TreeMap。
   • 典型场景：排行榜、分段规则、配置信息按范围取等。

5. 对内存非常敏感、key 极度稀疏？

   • 适当调整 HashMap / ConcurrentHashMap 的初始容量和负载因子，别让它疯狂扩容。

七、最后碎碎念：真正会用 Map 的人，是会“选 + 懂 + 调”的人

很多人觉得集合就是“API 背熟就完了”，但是真正拉开水平差距的，往往是这些底层细节：

• 你知不知道 index = (n - 1) & hash 背后的小心思？
• 你知不知道 HashMap 树化为什么要到 8？
• 你知不知道 ConcurrentHashMap 1.7 的 Segment 和 1.8 的 CAS + synchronized 差在哪？
• 你知不知道 LinkedHashMap 实现 LRU 真就那几行？
• 你知不知道 TreeMap 的红黑树可以帮你轻松搞定各种区间规则？

当你不再把这些东西当成“黑盒子”，而是能一边写代码一边腔调十足地说一句：

“这个 Map 我是挑过的，底层啥结构我心里有数。”

那你对 Java 集合的掌控力，已经悄悄上了一个台阶了。

所以，回到最开始那个问题——你天天在用 Map，却真的想过它脑子里在想啥吗？
要不，下一次写代码的时候，咱就试着“带着理解去选择”，而不是随手一个 new HashMap<>() 糊上去？😉

… …

文末

好啦，以上就是我这期的全部内容，如果有任何疑问，欢迎下方留言哦，咱们下期见。

… …

学习不分先后，知识不分多少；事无巨细，当以虚心求教；三人行，必有我师焉！！！

wished for you successed ！！！

⭐️若喜欢我，就请关注我叭。

⭐️若对您有用，就请点赞叭。
⭐️若有疑问，就请评论留言告诉我叭。

版权声明：本文由作者原创，转载请注明出处，谢谢支持！