HashMap 完整系列详解

HashMap 家族有四个成员，各自适用于不同的场景。

一、HashMap（基础版本）

1.1 核心特性

HashMap = 数组 + 链表 + 红黑树

特点：
- 基于哈希表
- 允许 null 键和 null 值
- 无序（不保证迭代顺序）
- 非线程安全
- 时间复杂度 O(1)

1.2 使用示例

Map<String, Integer> map = new HashMap<>();
map.put("Alice", 20);
map.put("Bob", 25);

// 获取
Integer age = map.get("Alice");

// 遍历
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

二、LinkedHashMap（有序版本）

2.1 核心特性

LinkedHashMap = HashMap + 双向链表

特点：
- 继承 HashMap
- 维护插入顺序或访问顺序
- 可用于实现 LRU 缓存
- 性能略低于 HashMap

2.2 插入顺序

// 默认：插入顺序
Map<String, Integer> map = new LinkedHashMap<>();
map.put("C", 3);
map.put("A", 1);
map.put("B", 2);

// 迭代顺序：C → A → B（插入顺序）
for (String key : map.keySet()) {
    System.out.println(key);
}

2.3 访问顺序

// accessOrder = true：访问顺序
Map<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
map.put("C", 3);
map.put("A", 1);
map.put("B", 2);

// 访问 A
map.get("A");

// 迭代顺序：C → B → A（A 最后访问，移到最后）
for (String key : map.keySet()) {
    System.out.println(key);
}

2.4 LRU 缓存实现

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxCapacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true); // accessOrder = true
        this.maxCapacity = capacity;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxCapacity; // 超过容量移除最旧的
    }
    
    public static void main(String[] args) {
        LRUCache<String, Integer> cache = new LRUCache<>(3);
        cache.put("A", 1);
        cache.put("B", 2);
        cache.put("C", 3);
        
        cache.get("A"); // 访问 A
        cache.put("D", 4); // 超出容量，移除 B（最久未使用）
        
        // 结果：A, C, D
        System.out.println(cache.keySet());
    }
}

三、TreeMap（排序版本）

3.1 核心特性

TreeMap = 红黑树

特点：
- 基于红黑树
- 按键排序（自然顺序或自定义）
- 时间复杂度 O(log n)
- 支持范围查询

3.2 自然排序

// 自然排序（按键的 Comparable）
TreeMap<String, Integer> map = new TreeMap<>();
map.put("C", 3);
map.put("A", 1);
map.put("B", 2);

// 迭代顺序：A → B → C（字典序）
for (String key : map.keySet()) {
    System.out.println(key);
}

3.3 自定义排序

// 自定义比较器
TreeMap<String, Integer> map = new TreeMap<>((a, b) -> b.compareTo(a));
map.put("C", 3);
map.put("A", 1);
map.put("B", 2);

// 迭代顺序：C → B → A（逆序）
for (String key : map.keySet()) {
    System.out.println(key);
}

3.4 范围查询

TreeMap<Integer, String> map = new TreeMap<>();
map.put(1, "One");
map.put(2, "Two");
map.put(3, "Three");
map.put(4, "Four");
map.put(5, "Five");

// subMap：范围查询
Map<Integer, String> sub = map.subMap(2, 5); // [2, 5)
// {2=Two, 3=Three, 4=Four}

// headMap：小于
Map<Integer, String> head = map.headMap(3); // [1, 3)
// {1=One, 2=Two}

// tailMap：大于等于
Map<Integer, String> tail = map.tailMap(3); // [3, 5]
// {3=Three, 4=Four, 5=Five}

// firstKey / lastKey
Integer first = map.firstKey(); // 1
Integer last = map.lastKey();   // 5

// lowerKey / higherKey
Integer lower = map.lowerKey(3); // 2
Integer higher = map.higherKey(3); // 4

// floorKey / ceilingKey
Integer floor = map.floorKey(3); // 3
Integer ceiling = map.ceilingKey(3); // 3

四、WeakHashMap（弱引用版本）

4.1 核心特性

WeakHashMap = HashMap + 弱引用

特点：
- 键是弱引用
- GC 可回收键
- 适用于缓存场景
- 键被回收时自动删除 entry

4.2 弱引用行为

Map<Object, String> map = new WeakHashMap<>();
Object key = new Object();

map.put(key, "Value");
System.out.println(map.size()); // 1

// 断开强引用
key = null;

// GC 后，键被回收，entry 自动删除
System.gc();
System.out.println(map.size()); // 0

4.3 缓存应用

// 元数据缓存
private static final Map<Class<?>, List<Field>> fieldCache = new WeakHashMap<>();

public List<Field> getFields(Class<?> clazz) {
    return fieldCache.computeIfAbsent(clazz, c -> {
        // 反射获取字段（耗时操作）
        return Arrays.asList(c.getDeclaredFields());
    });
}

// 当 Class 被卸载时，缓存自动清理

五、对比总结

5.1 性能对比

5.2 选择建议

// ✅ 一般场景：HashMap
Map<String, Integer> map = new HashMap<>();

// ✅ 需要顺序：LinkedHashMap
Map<String, Integer> map = new LinkedHashMap<>();

// ✅ 需要排序/范围查询：TreeMap
TreeMap<Integer, String> map = new TreeMap<>();

// ✅ 缓存场景：WeakHashMap
Map<Object, String> cache = new WeakHashMap<>();

六、实战场景

6.1 统计词频

// HashMap：统计词频
public Map<String, Integer> countWords(List<String> words) {
    Map<String, Integer> freq = new HashMap<>();
    for (String word : words) {
        freq.merge(word, 1, Integer::sum);
    }
    return freq;
}

// TreeMap：按词排序
public Map<String, Integer> countWordsSorted(List<String> words) {
    Map<String, Integer> freq = new TreeMap<>();
    for (String word : words) {
        freq.merge(word, 1, Integer::sum);
    }
    return freq;
}

6.2 TopK 问题

// TreeMap：TopK
public List<String> topK(Map<String, Integer> freq, int k) {
    TreeMap<Integer, List<String>> sorted = new TreeMap<>();
    
    for (Map.Entry<String, Integer> entry : freq.entrySet()) {
        sorted.computeIfAbsent(entry.getValue(), x -> new ArrayList<>())
            .add(entry.getKey());
    }
    
    List<String> result = new ArrayList<>();
    for (int i = 0; i < k && !sorted.isEmpty(); i++) {
        Map.Entry<Integer, List<String>> last = sorted.pollLastEntry();
        result.addAll(last.getValue());
    }
    
    return result;
}

6.3 时间范围查询

// TreeMap：时间范围查询
TreeMap<Long, Event> events = new TreeMap<>();

// 添加事件
events.put(timestamp1, event1);
events.put(timestamp2, event2);

// 查询某个时间段的事件
Map<Long, Event> range = events.subMap(startTime, endTime);

// 查询最近的事件
Map.Entry<Long, Event> latest = events.lastEntry();

6.4 配置管理

// LinkedHashMap：保持配置顺序
Map<String, String> config = new LinkedHashMap<>();
config.put("db.url", "jdbc:mysql://localhost");
config.put("db.user", "root");
config.put("db.password", "secret");

// 按配置顺序输出
for (Map.Entry<String, String> entry : config.entrySet()) {
    System.out.println(entry.getKey() + "=" + entry.getValue());
}

七、总结

HashMap 家族核心要点：

默认选择 HashMap，需要顺序用 LinkedHashMap，需要排序用 TreeMap。