04_Map接口规范与实现类深度分析
约 7227 字大约 24 分钟
2025-11-17
概述
Map接口是Java集合框架中用于存储键值对(key-value)映射关系的接口。Map中的键(key)是唯一的,每个键最多可以映射到一个值(value)。Map接口不直接继承Collection接口,而是独立存在的,但它与Collection一样,是Java集合框架中的重要组成部分。
核心特征
- 键值对存储:以键值对(
key-value)的形式存储数据 - 键唯一性:每个键只能映射到一个值,键不允许重复
- 值可重复:不同的键可以映射到相同的值
- 查找高效:提供高效的键查找机制
- 视图操作:支持获取键集、值集和键值对集的视图
Map接口定义
public interface Map<K, V> {
// 基本操作
int size();
boolean isEmpty();
boolean containsKey(Object key);
boolean containsValue(Object value);
V get(Object key);
V put(K key, V value);
V remove(Object key);
// 批量操作
void putAll(Map<? extends K, ? extends V> m);
void clear();
// 视图操作
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
// 内部接口Entry
interface Entry<K, V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
// Java 8+ 方法
public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K, V>> comparingByKey() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getKey().compareTo(c2.getKey());
}
public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K, V>> comparingByValue() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getValue().compareTo(c2.getValue());
}
}
// 相等性和哈希码
boolean equals(Object o);
int hashCode();
// Java 8+ 方法
default V getOrDefault(Object key, V defaultValue) {
V v;
return (((v = get(key)) != null) || containsKey(key)) ? v : defaultValue;
}
default void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
throw new ConcurrentModificationException(ise);
}
action.accept(k, v);
}
}
// 其他Java 8+默认方法...
}主要实现类对比
HashMap/LinkedHashMap/TreeMap特性对比表
| 特性 | HashMap | LinkedHashMap | TreeMap |
|---|---|---|---|
| 底层实现 | 哈希表(数组+链表/红黑树) | 哈希表+双向链表 | 红黑树 |
| 存储结构 | 数组+链表/红黑树 | 数组+链表/红黑树+双向链表 | 红黑树 |
| 插入顺序 | 不保证 | 保证 | 不保证(按排序) |
| 元素排序 | 无序 | 插入顺序或访问顺序 | 自然排序或自定义排序 |
| 查找性能 | O(1) 平均 | O(1) 平均 | O(log n) |
| 插入性能 | O(1) 平均 | O(1) 平均 | O(log n) |
| 删除性能 | O(1) 平均 | O(1) 平均 | O(log n) |
| 线程安全 | 否 | 否 | 否 |
| 允许null键/值 | 是(1个null键) | 是(1个null键) | 否(null键) |
| 内存占用 | 中等 | 较高 | 较高 |
| 适用场景 | 快速查找、键值映射 | 需要顺序访问的映射 | 需要排序的映射 |
| 初始容量 | 16 | 16 | 无 |
| 负载因子 | 0.75 | 0.75 | 无 |
HashMap实现原理
HashMap入门级使用示例
下面是一个简单的HashMap使用示例,展示最基础的创建、添加、获取、遍历等操作:
public class HashMapBasicExample {
public static void main(String[] args) {
// 创建一个HashMap集合
HashMap<String, Integer> scores = new HashMap<>();
// 添加键值对
scores.put("张三", 85);
scores.put("李四", 92);
scores.put("王五", 78);
scores.put("赵六", 95);
System.out.println("添加元素后: " + scores);
// 输出类似: {张三=85, 李四=92, 王五=78, 赵六=95}
// 如果键已存在,put方法会返回旧值并覆盖
Integer oldScore = scores.put("李四", 98);
System.out.println("李四的旧分数: " + oldScore); // 输出: 92
System.out.println("更新后: " + scores);
// 输出类似: {张三=85, 李四=98, 王五=78, 赵六=95}
// 获取指定键的值
Integer zhangsanScore = scores.get("张三");
System.out.println("张三的分数: " + zhangsanScore); // 输出: 85
// 获取不存在的键,返回null
Integer sunqiScore = scores.get("孙七");
System.out.println("孙七的分数: " + sunqiScore); // 输出: null
// 使用getOrDefault避免空指针
Integer sunqiScore2 = scores.getOrDefault("孙七", 0);
System.out.println("孙七的分数(默认): " + sunqiScore2); // 输出: 0
// 判断是否包含指定的键
boolean hasZhangsan = scores.containsKey("张三");
System.out.println("包含张三: " + hasZhangsan); // 输出: true
// 判断是否包含指定的值
boolean hasScore85 = scores.containsValue(85);
System.out.println("包含分数85: " + hasScore85); // 输出: true
// 获取键的集合
Set<String> names = scores.keySet();
System.out.println("所有学生: " + names);
// 输出类似: [张三, 李四, 王五, 赵六]
// 获取值的集合
Collection<Integer> allScores = scores.values();
System.out.println("所有分数: " + allScores);
// 输出类似: [85, 98, 78, 95]
// 遍历HashMap的四种方式
// 1. 使用keySet遍历
System.out.println("\n方式一:使用keySet遍历");
for (String name : scores.keySet()) {
System.out.println(name + ": " + scores.get(name));
}
// 2. 使用entrySet遍历(推荐,更高效)
System.out.println("\n方式二:使用entrySet遍历");
for (Map.Entry<String, Integer> entry : scores.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
// 3. 使用Lambda表达式遍历(Java 8及以上)
System.out.println("\n方式三:使用Lambda表达式遍历");
scores.forEach((name, score) -> {
System.out.println(name + ": " + score);
});
// 4. 使用values遍历(只遍历值)
System.out.println("\n方式四:只遍历值");
for (Integer score : scores.values()) {
System.out.println("分数: " + score);
}
// 删除元素
Integer removedScore = scores.remove("王五");
System.out.println("\n删除的分数: " + removedScore); // 输出: 78
System.out.println("删除后: " + scores);
// 输出类似: {张三=85, 李四=98, 赵六=95}
// 获取集合大小
System.out.println("集合大小: " + scores.size()); // 输出: 3
// 清空集合
scores.clear();
System.out.println("清空后: " + scores); // 输出: {}
System.out.println("集合是否为空: " + scores.isEmpty()); // 输出: true
}
}基本结构
HashMap的底层实现经历了从JDK 7到JDK 8的重大变化。JDK 8中,HashMap采用数组+链表+红黑树的结构,当链表长度超过阈值(默认为8)时,会将链表转换为红黑树以提高查找效率。
HashMap在不同JDK版本的实现对比
JDK 7 与 JDK 8+ HashMap实现对比
| 特性 | JDK 7 HashMap | JDK 8+ HashMap |
|---|---|---|
| 基本结构 | 数组 + 链表 | 数组 + 链表 + 红黑树 |
| 链表插入方式 | 头插法(先将新节点的next指向原头节点,再将新节点设为头节点) | 尾插法(直接追加到链表末尾) |
| 扩容时重新计算哈希 | 是的,每次扩容都需要重新计算所有元素的哈希值 | 否,利用位运算优化,仅需判断高位是否为1 |
| 查找时间复杂度 | 最坏O(n) | 最坏O(log n)(红黑树优化) |
| 新增常量 | 无 | TREEIFY_THRESHOLD=8, UNTREEIFY_THRESHOLD=6, MIN_TREEIFY_CAPACITY=64 |
| 内部节点类 | Entry<K,V> | Node<K,V>(链表节点)和TreeNode<K,V>(红黑树节点) |
| 并发安全性 | 非线程安全,可能导致环形链表 | 非线程安全,但避免了环形链表问题 |
详细差异分析
1. 数据结构优化
// JDK 7 中的链表节点
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
// ...
}
// JDK 8 中的链表节点
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
// ...
}
// JDK 8 中的红黑树节点
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; // 颜色标记
// ...
}2. 哈希冲突解决方法改进
JDK 7:仅使用链地址法,所有哈希冲突的元素都存储在同一个链表中JDK 8+:结合链地址法和红黑树,当链表长度超过8且数组长度大于等于64时,将链表转换为红黑树
3. 头插法 vs 尾插法
// JDK 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); // 头插法
if (size++ >= threshold) {
resize(2 * table.length);
}
}
// JDK 8 尾插法伪代码
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
// 在putVal方法中使用尾插法4. 扩容优化
JDK 7:- 重新计算所有元素的哈希值
- 重新计算索引位置
- 采用头插法可能导致链表顺序反转
- 多线程环境下可能形成环形链表
JDK 8+:- 利用扩容前的哈希值和旧容量进行位运算
- 新索引要么是原索引,要么是原索引+旧容量
- 使用尾插法保持链表原有顺序
- 避免了多线程环境下的环形链表问题(但仍非线程安全)
5. 性能提升
- 查找效率:链表转红黑树后,查找时间复杂度从
O(n)优化到O(log n) - 扩容效率:位运算优化减少了计算量
- 内存使用:
JDK 8+在节点设计上更加紧凑
为什么要在JDK 8中引入红黑树?
- 性能优化:当哈希冲突严重时,长链表的查找性能会退化
- 避免极端情况:恶意构造哈希值可能导致
O(n)的查找复杂度(但在实践中基本不会发生) - 更平衡的数据结构:红黑树提供了稳定的
O(log n)性能
为什么阈值设为8?
- 基于泊松分布的统计数据,链表长度达到8的概率非常低(约
0.00000006) - 平衡了时间和空间成本
- 长度为
8是性能优化的临界点
public class HashMap<K, V> extends AbstractMap<K, V>
implements Map<K, V>, Cloneable, Serializable {
// 序列化版本ID
private static final long serialVersionUID = 362498820763181265L;
// 默认初始容量 (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 Set<Map.Entry<K,V>> entrySet;
// 元素个数
transient int size;
// 结构修改次数
transient int modCount;
// 阈值,当size>=threshold时,进行扩容
int threshold;
// 负载因子
final float loadFactor;
// 构造函数
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
// 验证参数
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
}数据节点定义
// 普通节点
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;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
// 红黑树节点
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; // 节点颜色
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
// 其他红黑树相关方法...
}HashMap的put过程
HashMap的put操作是其最核心的方法之一,JDK 8中的实现如下:
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未初始化或为空,初始化table
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已存在,直接更新value
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);
// 6. 如果链表长度超过阈值,转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 7. 如果在链表中找到相同的key,更新value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 8. key已存在,更新value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount; // 增加修改计数
// 9. 如果size超过阈值,进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}哈希值计算和索引确定
HashMap中哈希值的计算非常巧妙,目的是减少哈希冲突:
// 计算哈希值
static final int hash(Object key) {
int h;
// 1. 如果key为null,哈希值为0
// 2. 否则,先获取key的hashCode(),然后将高16位与低16位异或,增加哈希值的随机性
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 计算数组索引:使用与运算替代取模运算,提高效率
// 要求数组长度必须是2的幂
int index = (n - 1) & hash;HashMap的扩容机制
当HashMap的元素数量超过阈值(容量*负载因子)时,会触发扩容操作,将容量扩大为原来的两倍:
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;
}
// 将容量扩大为原来的两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 创建新数组
@SuppressWarnings({"rawtypes","unchecked"})
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 { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引 + oldCap
else {
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;
}LinkedHashMap实现原理
基本结构
LinkedHashMap继承自HashMap,在HashMap的基础上,通过维护一个双向链表来记录元素的插入顺序或访问顺序。
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
// 双向链表的头节点(最早插入的元素)
transient LinkedHashMap.Entry<K,V> head;
// 双向链表的尾节点(最近插入的元素)
transient LinkedHashMap.Entry<K,V> tail;
// 访问顺序模式:true表示按照访问顺序排序,false表示按照插入顺序排序
final boolean accessOrder;
// 构造函数
public LinkedHashMap() {
super();
accessOrder = false; // 默认按插入顺序
}
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
// 其他构造函数...
}节点定义
LinkedHashMap的节点继承自HashMap.Node,并增加了双向链表的引用:
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}维护双向链表的核心方法
LinkedHashMap通过重写HashMap中的钩子方法来维护双向链表:
// 在节点访问后调用(get操作时)
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// 如果是访问顺序模式且访问的不是尾节点
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
// 在节点插入后调用(put操作时)
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
// 如果需要删除最老的元素(由removeEldestEntry方法决定)
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
// 在节点删除后调用(remove操作时)
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}实现LRU缓存示例
LinkedHashMap可以很容易地实现LRU(最近最少使用)缓存:
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
public LRUCache(int capacity) {
// 第三个参数设置为true,表示按照访问顺序排序
super(capacity, 0.75f, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
// 当缓存大小超过容量时,删除最老的元素
return size() > capacity;
}
public static void main(String[] args) {
// 创建容量为3的LRU缓存
LRUCache<String, Integer> cache = new LRUCache<>(3);
// 添加元素
cache.put("A", 1);
cache.put("B", 2);
cache.put("C", 3);
System.out.println("初始缓存: " + cache);
// 输出: {A=1, B=2, C=3}
// 访问元素,会将其移到链表末尾(最近使用)
cache.get("A");
System.out.println("访问A后: " + cache);
// 输出: {B=2, C=3, A=1}
// 添加新元素,会删除最久未使用的元素B
cache.put("D", 4);
System.out.println("添加D后: " + cache);
// 输出: {C=3, A=1, D=4}
// 再次访问元素,会将其移到链表末尾
cache.get("C");
System.out.println("访问C后: " + cache);
// 输出: {A=1, D=4, C=3}
// 添加新元素,会删除最久未使用的元素A
cache.put("E", 5);
System.out.println("添加E后: " + cache);
// 输出: {D=4, C=3, E=5}
}
}TreeMap实现原理
基本结构
TreeMap底层基于红黑树(Red-Black Tree)实现,能够保证元素按照键的自然顺序或自定义顺序进行排序。
public class TreeMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
// 红黑树的根节点
private transient Entry<K,V> root;
// 元素数量
private transient int size = 0;
// 结构修改次数
private transient int modCount = 0;
// 比较器,如果为null则使用键的自然顺序
private final Comparator<? super K> comparator;
// 构造函数
public TreeMap() {
comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
// 红黑树节点定义
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
// 构造函数和方法...
}
// 其他方法...
}排序机制
TreeMap支持两种排序方式:
- 自然排序:键类实现
Comparable接口,并重写compareTo()方法 - 自定义排序:在构造
TreeMap时传入Comparator接口的实现
查找与修改操作
// 获取元素
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
// 获取节点
final Entry<K,V> getEntry(Object key) {
// 如果提供了比较器,使用比较器查找
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
// 添加元素
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}TreeMap排序和范围查询示例
public class TreeMapExample {
public static void main(String[] args) {
// 创建TreeMap(自然排序)
NavigableMap<Integer, String> map = new TreeMap<>();
// 添加元素
map.put(3, "Three");
map.put(1, "One");
map.put(5, "Five");
map.put(2, "Two");
map.put(4, "Four");
System.out.println("自然排序结果: " + map);
// 输出: {1=One, 2=Two, 3=Three, 4=Four, 5=Five}
// 范围查询
System.out.println("小于3的元素: " + map.headMap(3));
// 输出: {1=One, 2=Two}
System.out.println("大于等于3的元素: " + map.tailMap(3));
// 输出: {3=Three, 4=Four, 5=Five}
System.out.println("2到4之间的元素: " + map.subMap(2, 5));
// 输出: {2=Two, 3=Three, 4=Four}
// 导航方法
System.out.println("小于3的最大键: " + map.lowerKey(3)); // 2
System.out.println("小于等于3的最大键: " + map.floorKey(3)); // 3
System.out.println("大于等于3的最小键: " + map.ceilingKey(3)); // 3
System.out.println("大于3的最小键: " + map.higherKey(3)); // 4
// 降序视图
NavigableMap<Integer, String> descendingMap = map.descendingMap();
System.out.println("降序视图: " + descendingMap);
// 输出: {5=Five, 4=Four, 3=Three, 2=Two, 1=One}
// 自定义比较器(降序)
NavigableMap<String, Integer> customMap = new TreeMap<>(Comparator.reverseOrder());
customMap.put("apple", 10);
customMap.put("banana", 5);
customMap.put("orange", 8);
System.out.println("\n自定义降序结果: " + customMap);
// 输出: {orange=8, banana=5, apple=10}
// 复合比较器示例
NavigableMap<Person, String> personMap = new TreeMap<>(
Comparator.comparing(Person::getAge)
.thenComparing(Person::getName));
personMap.put(new Person("Alice", 25), "Employee");
personMap.put(new Person("Bob", 30), "Manager");
personMap.put(new Person("Charlie", 25), "Developer");
System.out.println("\n按年龄和姓名排序的人员: ");
personMap.forEach((k, v) -> System.out.println(k + ": " + v));
// 输出按年龄排序,同年龄按姓名排序
}
static class Person {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() { return name; }
public int getAge() { return age; }
@Override
public String toString() {
return name + "(" + age + ")";
}
}
}Map选择指南
选择决策流程图
场景演示
public class MapSelectionDemo {
public static void main(String[] args) {
// 场景1:快速查询,无需顺序
Map<String, String> hashMap = new HashMap<>();
hashMap.put("user1", "Alice");
hashMap.put("user2", "Bob");
System.out.println("快速查询场景: " + hashMap);
// 场景2:需要保持插入顺序
Map<String, String> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("step1", "准备材料");
linkedHashMap.put("step2", "开始制作");
linkedHashMap.put("step3", "完成");
System.out.println("保持插入顺序场景: " + linkedHashMap);
// 场景3:需要按键排序
Map<Integer, String> treeMap = new TreeMap<>();
treeMap.put(3, "第三章");
treeMap.put(1, "第一章");
treeMap.put(2, "第二章");
System.out.println("按键排序场景: " + treeMap);
// 场景4:缓存实现(LRU)
Map<String, Object> lruCache = new LinkedHashMap<String, Object>(16, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<String, Object> eldest) {
return size() > 5; // 缓存容量为5
}
};
for (int i = 1; i <= 10; i++) {
lruCache.put("key" + i, "value" + i);
}
System.out.println("LRU缓存场景: " + lruCache); // 保留最近访问的5个元素
// 场景5:线程安全的高并发场景
Map<String, String> concurrentMap = new ConcurrentHashMap<>();
concurrentMap.put("counter", "0");
System.out.println("并发场景: " + concurrentMap);
// 场景6:枚举键场景
Map<DayOfWeek, String> enumMap = new EnumMap<>(DayOfWeek.class);
enumMap.put(DayOfWeek.MONDAY, "星期一");
enumMap.put(DayOfWeek.TUESDAY, "星期二");
System.out.println("枚举键场景: " + enumMap);
}
}Map接口核心总结(零基础友好版)
HashMap使用常见误区和注意事项
1. 忽略键的hashCode和equals方法实现
- 误区:使用自定义对象作为键时,不重写
hashCode和equals方法 - 正确做法:必须重写这两个方法,确保相同的对象有相同的
hashCode,且equals返回true
2. 初始容量设置不合理
- 误区:不设置初始容量,导致频繁扩容
- 正确做法:预估存储元素数量,设置合理初始容量(通常设置为
预期元素数量 / 0.75 + 1)
3. 在遍历过程中直接修改集合
- 误区:使用普通遍历方式直接修改
HashMap - 正确做法:使用
entrySet遍历,或使用迭代器的remove方法,或使用Java 8+的removeIf方法
4. 认为HashMap是线程安全的
- 误区:在多线程环境中直接使用
HashMap - 正确做法:多线程环境使用
ConcurrentHashMap或Collections.synchronizedMap
5. 键或值使用null
- 误区:在所有情况下都允许
null键或null值 - 正确做法:
HashMap允许一个null键和多个null值TreeMap不允许null键ConcurrentHashMap不允许null键和null值- 建议尽量避免使用
null,以防止空指针异常
6. 频繁的哈希冲突
- 误区:不关注哈希函数的质量
- 正确做法:确保自定义键的
hashCode方法分布均匀,减少哈希冲突
// 示例:自定义对象作为键时的正确实现
class Person {
private String name;
private int age;
// 构造方法、getter和setter省略
@Override
public int hashCode() {
return Objects.hash(name, 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);
}
}Map接口核心总结(零基础友好版)
Map集合的核心特点
Map是一种键值对集合,就像现实生活中的字典或通讯录,通过"键"可以快速找到对应的"值"。主要特点:
- 键值对存储:每个元素包含两个部分 - 键(
Key)和值(Value) - 键唯一性:同一个
Map中不能有重复的键,但值可以重复 - 快速查找:通过键可以在常数时间内(
O(1))找到对应的值
HashMap vs TreeMap vs LinkedHashMap 选择指南
| 集合类型 | 主要特点 | 适用场景 |
|---|---|---|
| HashMap | 无序,查询速度快 | 主要用于快速查询,不关心顺序 |
| TreeMap | 按键排序,实现了SortedMap接口 | 需要按键的自然顺序或自定义顺序排序 |
| LinkedHashMap | 维护插入顺序 | 需要保持元素插入顺序的同时又要快速查询 |
实际应用中的小技巧
HashMap初始化容量:如果知道大概需要存储多少键值对,可以在创建时指定容量和加载因子
// 预计存储1000个键值对,设置初始容量为1000*2=2000(避免频繁扩容)
Map<String, Object> map = new HashMap<>(2000);- 遍历方式选择:
- 只需要键:使用
keySet()遍历 - 只需要值:使用
values()遍历 - 需要同时使用键和值:使用
entrySet()遍历(推荐,性能更好)
- 只需要键:使用
- 避免空指针异常:使用
getOrDefault()方法获取值
// 安全地获取值,如果键不存在则返回默认值
Integer count = map.getOrDefault("key", 0);- 键的选择:
- 最好使用不可变类型作为键(如
String、Integer等),因为它们的hashCode和equals方法是固定的 - 如果使用自定义对象作为键,必须正确实现
equals()和hashCode()方法,确保相同的对象有相同的hashCode,且equals返回true
- 最好使用不可变类型作为键(如
- 线程安全问题:
HashMap不是线程安全的,多线程环境下可以使用ConcurrentHashMap- 避免使用
Hashtable,它是线程安全的但性能较低
学习建议
- 先掌握
Map的基本操作:添加、获取、遍历、删除键值对 - 理解
HashMap的工作原理:哈希表、哈希冲突、扩容机制 - 学会根据需求选择合适的
Map实现类 - 掌握自定义对象作为键时的注意事项
Map接口小结
面试知识点
HashMap的工作原理:- 底层结构(数组+链表/红黑树)
- 哈希冲突解决方法(链地址法)
- 扩容机制(容量翻倍,重新哈希)
- 树化阈值(
8)和去树化阈值(6)
HashMapvsLinkedHashMapvsTreeMap:- 性能特点
- 存储结构
- 排序特性
- 适用场景
hashCode()和equals()的重要性:- 两者必须保持一致
- 如何正确实现
- 常见错误实现
- 线程安全的
Map实现:HashtableCollections.synchronizedMap()ConcurrentHashMapCopyOnWriteArraySet
LinkedHashMap实现LRU缓存:- 访问顺序模式
removeEldestEntry方法- 实现原理
最佳实践
- 初始容量选择:
- 预估元素数量,设置合适的初始容量
- 计算公式:初始容量 = 预计元素数量 / 负载因子
- 正确实现键的
hashCode()和equals():- 使用
Objects.hash()生成hashCode - 确保
equals()方法考虑所有关键属性 - 保证两者逻辑一致
- 使用
- 线程安全处理:
- 读多写少:
CopyOnWriteArraySet - 高并发:
ConcurrentHashMap - 低并发:
Collections.synchronizedMap()
- 读多写少:
- 避免使用
Hashtable:- 性能较差
- 已被更现代的实现取代
- 利用Java 8+新特性:
forEach方法遍历compute/computeIfAbsent/computeIfPresent方法merge方法
- 选择合适的实现类:
- 快速查询:
HashMap - 保持顺序:
LinkedHashMap - 按键排序:
TreeMap - 并发环境:
ConcurrentHashMap
- 快速查询:
小结
Map接口是Java集合框架中用于存储键值对的重要接口,本章节详细介绍了其主要实现类(HashMap、LinkedHashMap、TreeMap)的底层原理、性能特征和适用场景。在实际开发中,我们需要根据具体需求选择合适的Map实现,并注意正确实现键类的hashCode()和equals()方法。
通过本章节的学习,我们深入理解了Map接口及其实现类的设计思想和使用方法,这对于编写高效、可靠的Java程序至关重要。
