哈希表代码题分析解决指南

---

哈希表（Hash Table）

一、是什么？
哈希表是一种基于键值对(Key-Value) 的数据结构，通过哈希函数将键(key)映射到存储位置(bucket)，实现高效的数据存取。在Java中主要通过HashMap、HashSet等类实现。

二、解决什么问题

1. 高效查找：解决数组/链表查找效率低(O(n))的问题，提供平均O(1)的查找性能
2. 快速去重：利用键的唯一性实现数据去重
3. 关系映射：建立两个数据集之间的关联关系
4. 频率统计：高效统计元素出现频率

三、核心方法（Java HashMap）

// 基础操作
map.put(key, value);    // 插入/更新
map.get(key);           // 获取
map.containsKey(key);   // 检查存在
map.remove(key);        // 删除

// JDK8+新方法
map.getOrDefault(key, defaultValue);  // 安全获取
map.computeIfAbsent(key, k -> newValue); // 不存在时计算
map.merge(key, value, (oldVal, newVal) -> mergeFunction); // 合并值

四、应用场景

• 两数之和/三数之和类问题
• 字符串字符统计/分组（如字母异位词分组）
• 缓存实现（如LRU Cache）
• 数据索引与快速检索
• 避免重复计算（记忆化搜索）

五、Java示例：字母异位词分组

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(map.values());
}

六、重要注意事项

1. 哈希冲突：不同键映射到同一位置（Java使用链表+红黑树解决）
2. 键对象要求：作为键的对象必须正确实现hashCode()和equals()
3. 初始容量：预估数据量设置初始容量避免频繁扩容
4. 并发安全：HashMap非线程安全，多线程用ConcurrentHashMap
5. 遍历顺序：HashMap不保证遍历顺序，需要有序用LinkedHashMap

解决哈希表代码题的分析框架

步骤1：识别问题类型

步骤2：设计键(Key)策略

问题类型	键设计策略	示例问题
元素直接作为键	使用元素本身	两数之和
元素转换后作为键	排序/编码/哈希	字母异位词分组
组合键	拼接多个特征	二维坐标点统计
前缀特征	使用前缀和/累积值	和为K的子数组
状态压缩	使用位图表示状态	状态记录问题

步骤3：选择合适的数据结构

需求	Java实现类	特点
基础键值存储	HashMap	通用键值对存储
需要去重的集合	HashSet	基于HashMap实现，只存储键
需要保持插入顺序	LinkedHashMap	维护插入顺序的双向链表
需要排序	TreeMap	基于红黑树实现有序映射
线程安全环境	ConcurrentHashMap	分段锁实现的并发安全Map
缓存淘汰策略(LRU)	LinkedHashMap	重写removeEldestEntry方法实现

步骤4：处理边界情况

1. 空值处理：考虑key为null的情况（HashMap允许一个null key）
2. 哈希冲突：当冲突较多时性能下降（Java 8+当桶>8时转为红黑树）
3. 大数据量：设置合理的初始容量避免频繁扩容
4. 哈希攻击：防止恶意构造大量哈希冲突的键（使用随机哈希种子）

步骤5：优化与复杂度分析

典型问题解决模式

模式1：查找补数（如两数之和）

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    return new int[0];
}

模式2：频率统计（如Top K高频元素）

public int[] topKFrequent(int[] nums, int k) {
    // 1. 频率统计
    Map<Integer, Integer> freqMap = new HashMap<>();
    for (int num : nums) {
        freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
    }
    
    // 2. 使用优先队列获取TopK
    PriorityQueue<Map.Entry<Integer, Integer>> pq = 
        new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
    
    for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
        pq.offer(entry);
        if (pq.size() > k) pq.poll();
    }
    
    // 3. 构造结果
    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) {
        result[i] = pq.poll().getKey();
    }
    return result;
}

模式3：状态记录（如最长无重复子串）

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> map = new HashMap<>();
    int maxLen = 0, start = 0;
    for (int end = 0; end < s.length(); end++) {
        char c = s.charAt(end);
        if (map.containsKey(c)) {
            // 更新起点位置
            start = Math.max(start, map.get(c) + 1);
        }
        map.put(c, end);
        maxLen = Math.max(maxLen, end - start + 1);
    }
    return maxLen;
}

总结：哈希表解题思维导图

核心解决思路：

1. 识别：判断问题是否适合哈希表解决（查找/映射/统计/去重）
2. 设计：精心设计键(Key)的表达方式
3. 选择：根据需求选择合适的哈希表实现
4. 处理：考虑边界情况和特殊输入
5. 优化：利用Java特性和新API优化性能

通过系统化的分析框架，可以高效解决90%以上的哈希表相关算法问题。在实际编码时，要特别注意键的设计和哈希冲突的处理，这是哈希表问题优化的核心所在。