Java 集合框架核心：Map 与 Set 深度解析

Map 详解

Map 存储 (key, value) 键值对。TreeMap 底层是红黑树，支持排序但无法插入 null key；HashMap 底层是哈希表，查找快且允许 null key。

public static void main(String[] args) {
    Map<String, Integer> map = new TreeMap<>(); // 红黑树 O(logN)
    map.put("push", 3);
    
    // 获取与默认值
    Integer val = map.getOrDefault("bbb", 99999);
    
    // 遍历 Key、Value 或 Entry
    Set<String> keys = map.keySet();
    for (Map.Entry<String, Integer> entry : map.entrySet()) {
        System.out.println(entry.getKey() + ": " + entry.getValue());
    }
}

Set 详解

Set 仅存储 key，天然去重。TreeSet 有序，HashSet 无序。两者在 null 处理上与对应的 Map 一致。

public static void main(String[] args) {
    Set<String> set = new TreeSet<>();
    set.add("hello");
    set.add("world");
    // 迭代器遍历
    Iterator<String> it = set.iterator();
    while (it.hasNext()) {
        System.out.println(it.next());
    }
}

哈希表机制

哈希表通过哈希函数将 Key 映射到数组下标，理想情况下查找复杂度为 O(1)。但哈希冲突不可避免，需合理设计哈希函数并控制负载因子。

负载因子调节

负载因子 = 填入元素个数 / 哈希表长度。过高会导致冲突激增，因此当超过阈值（如 0.75）时需扩容，重新计算节点位置。

冲突解决策略

1. 闭散列（开放定址）：冲突后探测下一个空位（线性探测或二次探测）。缺点是对空间利用率要求高，易产生聚集。
2. 开散列（链地址法）：每个数组槽位挂一个链表。Java 的 HashMap 即采用此方式，结合数组 + 链表 + 红黑树，平衡了性能与内存。

自定义哈希桶实现

以下是一个简化的开散列哈希表实现，展示了头插法与扩容逻辑。

package Demo1;
import java.util.Arrays;

public class HashBuck {
    public class Node {
        public int key;
        public int val;
        public Node next;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    public Node[] array;
    public int usedSize;
    public static final float DEFAULT_LOAD_FACTOR = 0.75f;

    public HashBuck() {
        array = new Node[10];
    }

    public void put(int key, int value) {
        int index = key % array.length;
        Node node = new Node(key, value);
        Node cur = array[index];
        
        // 检查是否存在
        while (cur != null) {
            if (cur.key == key) {
                cur.val = value;
                return;
            }
            cur = cur.next;
        }
        
        // 头插法
        node.next = array[index];
        array[index] = node;
        usedSize++;
        
        // 触发扩容
        if (doLoadFactor() > DEFAULT_LOAD_FACTOR) {
            resize();
        }
    }

    private void resize() {
        Node[] newArray = new Node[2 * array.length];
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while (cur != null) {
                Node tmp = cur.next;
                int newIndex = cur.key % newArray.length;
                cur.next = newArray[newIndex];
                newArray[newIndex] = cur;
                cur = tmp;
            }
        }
        array = newArray;
    }

    private float doLoadFactor() {
        return usedSize * 1.0f / array.length;
    }

    public int get(int key) {
        int index = key % array.length;
        Node cur = array[index];
        while (cur != null) {
            if (cur.key == key) return cur.val;
            cur = cur.next;
        }
        return -1;
    }
}

HashMap 源码关键点

实际开发中需注意 HashMap 线程不安全（早期版本头插法导致死循环），ConcurrentHashMap 才是线程安全方案。此外，当链表长度超过 8 且数组长度大于 64 时，链表会转换为红黑树以提升极端情况下的查找效率。

常见面试题实战

掌握 Map/Set 后，可尝试解决以下经典问题：

1. 只出现一次的数字：利用 Set 去重特性或异或运算。
2. 宝石与石头：统计字符频率，适合用 Map。
3. 前 K 个高频单词：结合 HashMap 统计词频，再用 PriorityQueue（小根堆）筛选 Top K。

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String s : words) {
            map.put(s, map.getOrDefault(s, 0) + 1);
        }
        
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>((o1, o2) -> {
            if (!o1.getValue().equals(o2.getValue())) {
                return o1.getValue() - o2.getValue();
            }
            return o2.getKey().compareTo(o1.getKey());
        });
        
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else if (entry.getValue() > minHeap.peek().getValue()) {
                minHeap.poll();
                minHeap.offer(entry);
            }
        }
        
        List<String> result = new ArrayList<>();
        while (!minHeap.isEmpty()) {
            result.add(minHeap.poll().getKey());
        }
        Collections.reverse(result);
        return result;
    }
}

理解这些底层原理，能帮助我们在面对复杂业务场景时，更准确地选择数据结构，写出高性能的代码。