Map

字数: 0 字 时长: 0 分钟

1. Map

Map 用于保存：

Key → Value
键值对

它和 List、Set 最大的区别是：

List / Set
    ↓
保存单个元素


Map
    ↓
保存 Key 和 Value

Map 的核心特点：

• Key 不能重复
• Value 可以重复
• 通过 Key 查找对应的 Value
• 同一个 Key 再次 put()，会覆盖原来的 Value

例如：

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

map.put(
        "张无忌",
        "zhangwuji"
);

map.put(
        "赵敏",
        "zhaomin"
);

可以理解：

张无忌 → zhangwuji

赵敏 → zhaomin

常见实现：

Map
├── HashMap
├── LinkedHashMap
└── TreeMap

三者最主要的区别：

HashMap
    ↓
不保证遍历顺序


LinkedHashMap
    ↓
可以维护插入顺序 / 访问顺序


TreeMap
    ↓
按照 Key 排序

1.1 HashMap

HashMap 是最常用的 Map 实现之一。

它通过：

Key
    ↓
hash
    ↓
定位对应位置

来实现较快的：

查询

添加

删除

基本使用：

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

// 添加
map.put(
        "张无忌",
        "zhangwuji"
);

map.put(
        "周芷若",
        "zhouzhiruo"
);

map.put(
        "赵敏",
        "zhaomin"
);

// 查询
String value =
        map.get(
                "张无忌"
        );

// 修改
map.put(
        "张无忌",
        "zhangsanfeng"
);

// 删除
map.remove(
        "赵敏"
);

// 遍历
for (
        Map.Entry<String, String>
                entry :
                map.entrySet()
) {

    System.out.println(
            entry.getKey()
                    + " → "
                    + entry.getValue()
    );
}

1.1.1 HashMap 的特点

主要特点：

Key 不能重复

Value 可以重复

不保证遍历顺序

允许一个 null Key

允许多个 null Value

查询、添加、删除通常较快

如果重复加入同一个 Key：

map.put(
        "张无忌",
        "zhangwuji"
);

map.put(
        "张无忌",
        "zhangsanfeng"
);

最终：

张无忌 → zhangsanfeng

原来的 Value 会被覆盖。

1.1.2 容量和负载因子

HashMap 有两个比较重要的概念：

容量
Capacity


负载因子
Load Factor

常见默认负载因子：

0.75

当元素达到一定数量后：

容量不足
    ↓
触发扩容
    ↓
重新组织内部数据

HashMap 的：

hash 原理

put / get

扩容

负载因子

红黑树

JDK 7 / JDK 8 差异

后面在 HashMap.md 中单独整理。

---

1.2 LinkedHashMap

LinkedHashMap 是：

HashMap

的子类。

它可以简单理解为：

HashMap + 双向链表。

HashMap
    ↓
负责保存和查找数据


双向链表
    ↓
负责维护元素顺序

因此它既拥有类似 HashMap 的键值查找能力，又能够维护确定的遍历顺序。

1.2.1 LinkedHashMap 基本使用

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

map.put(
        "张无忌",
        "zhangwuji"
);

map.put(
        "赵敏",
        "zhaomin"
);

map.put(
        "周芷若",
        "zhouzhiruo"
);

for (
        Map.Entry<String, String>
                entry :
                map.entrySet()
) {

    System.out.println(
            entry.getKey()
                    + " → "
                    + entry.getValue()
    );
}

按照默认的插入顺序遍历：

张无忌 → zhangwuji

赵敏 → zhaomin

周芷若 → zhouzhiruo

而 HashMap：

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

不保证按照：

put() 的插入顺序

进行遍历。

1.2.2 LinkedHashMap 的特点

主要特点：

Key 不能重复

基于 HashMap

额外使用双向链表维护顺序

默认维护插入顺序

也可以维护访问顺序

所以可以简单记：

HashMap
    ↓
不关心顺序


LinkedHashMap
    ↓
HashMap + 顺序

LinkedHashMap 还可以配置：

accessOrder

按照访问顺序维护元素。

这种能力可以用于实现：

LRU 缓存

相关内容后面放到 Map.md 或缓存部分再展开。

---

1.3 TreeMap

TreeMap 是一个：

可以按照 Key 自动排序的 Map。

它实现了：

NavigableMap

而 NavigableMap 又继承：

SortedMap

底层使用：

红黑树

保存键值对。

因此：

TreeMap
    ↓
Key 唯一
    ↓
根据 Key 排序

1.3.1 TreeMap 基本使用

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

map.put(
        "周芷若",
        "zhouzhiruo"
);

map.put(
        "张无忌",
        "zhangwuji"
);

map.put(
        "赵敏",
        "zhaomin"
);

// 查询
String value =
        map.get(
                "张无忌"
        );

// 修改
map.put(
        "张无忌",
        "newzhangwuji"
);

// 删除
map.remove(
        "周芷若"
);

// 遍历
for (
        Map.Entry<String, String>
                entry :
                map.entrySet()
) {

    System.out.println(
            entry.getKey()
                    + " → "
                    + entry.getValue()
    );
}

1.3.2 TreeMap 自动排序

例如：

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

map.put(
        "c",
        "cat"
);

map.put(
        "a",
        "apple"
);

map.put(
        "b",
        "banana"
);

for (
        Map.Entry<String, String>
                entry :
                map.entrySet()
) {

    System.out.println(
            entry.getKey()
                    + ": "
                    + entry.getValue()
    );
}

输出：

a: apple
b: banana
c: cat

可以看到：

插入顺序

c → a → b

最终遍历顺序：

a → b → c

因为 TreeMap 会按照：

Key 的自然顺序

进行排序。

1.3.3 TreeMap 的排序方式

TreeMap 支持两种排序方式：

自然排序
Comparable

或者：

自定义排序
Comparator

例如：

Map<Integer, String> map =
        new TreeMap<>(
                Comparator.reverseOrder()
        );

map.put(
        1,
        "A"
);

map.put(
        3,
        "C"
);

map.put(
        2,
        "B"
);

System.out.println(
        map
);

结果：

{3=C, 2=B, 1=A}

所以可以简单记：

TreeMap
    ↓
红黑树
    ↓
按照 Key 排序
    ↓
Comparable / Comparator

---

2. 小结

三个常见 Map 实现：

实现	底层特点	顺序	主要用途
HashMap	哈希表	不保证顺序	普通键值存储
LinkedHashMap	哈希表 + 双向链表	插入 / 访问顺序	需要保持顺序
TreeMap	红黑树	Key 排序	需要按照 Key 排序

可以直接这样选：

普通 Map
    ↓
HashMap


需要保持插入顺序
    ↓
LinkedHashMap


需要按照 Key 排序
    ↓
TreeMap

一句话概括：

Map 保存的是唯一 Key 到 Value 的映射；HashMap 追求普通键值查找，LinkedHashMap 在此基础上维护顺序，TreeMap 则按照 Key 进行排序。