跳到主要内容

哈希表

问题​

Java 中哈希表相关的常见算法题有哪些？

答案​

哈希表（HashMap/HashSet）是面试最高频的数据结构之一，核心思想是用空间换时间，将 O(n)O(n) 查找降为 O(1)O(1)。

两数之和（LeetCode 1）​

HashMap 一次遍历
public int[] twoSum(int[] nums, int target) {
    // key: 数值, value: 索引
    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];
}

字母异位词分组（LeetCode 49）​

排序后作为 key 分组
public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strs) {
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        String key = new String(arr);  // 排序后的字符串作为 key
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(map.values());
}

最长连续序列（LeetCode 128）​

HashSet 去重 + 向右扩展
public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) set.add(num);
    
    int maxLen = 0;
    for (int num : set) {
        // 只从序列起点开始计数（前一个数不在集合中）
        if (!set.contains(num - 1)) {
            int cur = num, len = 1;
            while (set.contains(cur + 1)) {
                cur++;
                len++;
            }
            maxLen = Math.max(maxLen, len);
        }
    }
    return maxLen;  // 时间 O(n)
}

常见哈希表技巧​

技巧说明典型题目
频次计数统计字符/数字出现次数字母异位词、前 K 高频元素
前缀和 + HashMap记录前缀和首次出现位置和为 K 的子数组
双指针 + HashSet去重判断无重复字符的最长子串
映射关系建立一对一映射同构字符串、单词规律

和为 K 的子数组（LeetCode 560）​

前缀和 + HashMap
public int subarraySum(int[] nums, int k) {
    // key: 前缀和, value: 出现次数
    Map<Integer, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0, 1);  // 前缀和为 0 出现 1 次
    int sum = 0, count = 0;
    for (int num : nums) {
        sum += num;
        // 如果存在前缀和 = sum - k，说明中间这段子数组和为 k
        count += prefixCount.getOrDefault(sum - k, 0);
        prefixCount.merge(sum, 1, Integer::sum);
    }
    return count;
}

常见面试问题​

Q1: HashMap 和 HashSet 的区别？​

答案：

  • HashMap 存键值对 <K, V>，HashSet 只存键（底层就是 HashMap<E, Object>）
  • 面试算法中，需要记录映射关系用 HashMap，只需判断存在性用 HashSet

Q2: 哈希冲突如何处理？​

答案：

详见 HashMap 源码解析。JDK 8 使用链地址法：数组 + 链表 + 红黑树，链表长度 > 8 且数组长度 ≥ 64 时转红黑树。

Q3: 前缀和 + HashMap 的核心思路？​

答案：

遍历数组维护前缀和 sum，用 HashMap 记录每个前缀和出现的次数。当前前缀和为 sum，如果之前存在前缀和 sum - k，说明中间一段子数组的和为 k。时间 O(n)O(n)，空间 O(n)O(n)。

相关链接​