Java数据结构：Map与Set

一、Map与Set核心

1.1 Set 集合

- 继承自Collection，存储单个唯一元素
- 核心特性：无序、无下标、元素不可重复
- 本质：底层基于Map实现，只使用Key做去重
- 适用：去重、判重、唯一ID存储

1.2 Map 映射

- 独立接口，不继承Collection，存储Key-Value键值对
- 核心特性：Key唯一、Value可重复，通过Key快速查Value
- 适用：映射关系、缓存、配置、字典、统计计数

一区别

- Set管唯一，只存单个值，用来去重
- Map管映射，存键值对，用来快速查找



二、Set 常用实现类与底层原理

2.1 HashSet

- 底层：HashMap，哈希表结构
- 特点：无序、高效增删查、允许null
- 线程不安全
- 去重依赖：hashCode() + equals()

2.2 LinkedHashSet

- 底层：LinkedHashMap，哈希表+双向链表
- 特点：保留插入顺序，性能略低于HashSet

2.3 TreeSet

- 底层：TreeMap，红黑树
- 特点：自动排序（自然序/比较器）
- 元素必须实现Comparable或传入Comparator

Set 基础代码示例



Set<String> set = new HashSet<>();
set.add("Java");
set.add("Python");
set.add("Java"); // 重复，自动忽略
System.out.println(set.contains("Java")); // true
set.remove("Python");
// 遍历
for (String s : set) {
System.out.println(s);
}




三、Map 常用实现类与底层原理

3.1 HashMap

- 底层：JDK1.8+ 数组+链表+红黑树
- 特点：Key唯一、无序、高效、允许1个nullKey、多个nullValue
- 线程不安全，并发推荐ConcurrentHashMap

3.2 LinkedHashMap

- 底层：HashMap+双向链表
- 特点：保持插入顺序/访问顺序，适合缓存LRU场景

3.3 TreeMap

- 底层：红黑树
- 特点：Key自动排序，支持范围查找

3.4 Hashtable

- 线程安全，方法全synchronized，性能低，已淘汰

Map 基础代码示例



Map<String, Integer> map = new HashMap<>();
map.put("张三", 95);
map.put("李四", 88);
map.put("张三", 100); // 覆盖旧值
// 获取
System.out.println(map.get("张三")); // 100
// 判断
System.out.println(map.containsKey("李四")); // true




四、Map 四种遍历方式（面试高频）



// 1. keySet遍历（先取Key再取Value）
for (String key : map.keySet()) {
System.out.println(key + ":" + map.get(key));
}

// 2. entrySet遍历（推荐，效率最高）
for (Map.Entry<String, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + ":" + entry.getValue());
}

// 3. Iterator迭代器
Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<String, Integer> entry = iterator.next();
}

// 4. forEach（JDK8+）
map.forEach((k, v) -> System.out.println(k + ":" + v));




五、去重与排序核心机制

5.1 唯一性保证

- Set：依赖元素hashCode()与equals()
- Map：Key依赖hashCode()与equals()
- 自定义对象必须重写这两个方法，否则去重失效

5.2 排序机制

- TreeSet/TreeMap：自然排序（Comparable）或比较器排序（Comparator）
- LinkedHashSet/LinkedHashMap：保持插入顺序



六、时间复杂度对比

集合 查找 插入 删除 底层
HashSet/HashMap O(1) O(1) O(1) 哈希表
TreeSet/TreeMap O(logN) O(logN) O(logN) 红黑树



七、使用场景选择

选Set

- 列表去重
- 判断元素是否存在
- 存储唯一标识（UUID、手机号、IP）
- 交集/并集/差集运算

选Map

- ID关联对象（用户ID→User）
- 统计词频、计数
- 缓存、配置项
- 字典映射（中英互译）





总结

- Set = 去重工具，底层靠Map，查存在最快
- Map = 映射工具，Key唯一，按Key检索O(1)
- 无序选Hash系列，有序选Linked系列，排序选Tree系列
- 日常开发优先HashMap/HashSet，并发用ConcurrentHashMap

本文覆盖Java Map与Set的核心知识点，代码可直接复制运行，适合学习笔记与面试复习。

需要我帮你补充自定义对象存入Set/Map重写hashCode和equals的完整示例吗？