# 哈希表算法全解析：从两数之和到最长连续序列实践

## 引言：哈希表的算法哲学

哈希表以其接近常数时间的查找性能，成为解决查找类问题的利器。从基础的"两数之和"到复杂的"最长连续序列"，哈希表展现了处理查找、去重、聚合等问题的强大能力。本文将系统性地解析哈希表在不同场景下的应用模式，揭示算法设计的核心思想。

## 基础应用：两数之和问题

两数之和问题是哈希表最经典的入门应用，展示了如何用空间换时间，将时间复杂度从O(n²)优化到O(n)。

### 基础实现与优化

```java

// 两数之和：寻找数组中两数之和等于目标值

public class TwoSum {

    

    // 返回两个数的索引

    public static int[] twoSumIndices(int[] nums, int target) {

        Map<Integer, Integer> numMap = new HashMap<>();

        

        for (int i = 0; i < nums.length; i++) {

            int complement = target - nums[i];

            

            // 检查补数是否已存在

            if (numMap.containsKey(complement)) {

                return new int[]{numMap.get(complement), i};

            }

            

            // 将当前数和索引存入哈希表

            numMap.put(nums[i], i);

        }

        

        return new int[]{-1, -1}; // 未找到

    }

    

    // 返回两个数的值

    public static int[] twoSumValues(int[] nums, int target) {

        Set<Integer> numSet = new HashSet<>();

        

        for (int num : nums) {

            int complement = target - num;

            if (numSet.contains(complement)) {

                return new int[]{complement, num};

            }

            numSet.add(num);

        }

        

        return null;

    }

    

    // 处理重复元素的情况

    public static List<int[]> twoSumAllPairs(int[] nums, int target) {

        List<int[]> result = new ArrayList<>();

        Map<Integer, List<Integer>> indexMap = new HashMap<>();

        

        // 构建值和索引列表的映射

        for (int i = 0; i < nums.length; i++) {

            indexMap.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);

        }

        

        for (int i = 0; i < nums.length; i++) {

            int complement = target - nums[i];

            

            if (indexMap.containsKey(complement)) {

                for (int j : indexMap.get(complement)) {

                    if (i < j) { // 避免重复和自配对

                        result.add(new int[]{i, j});

                    }

                }

            }

        }

        

        return result;

    }

}

```

### 变种问题：三数之和

```java

// 三数之和：使用哈希表优化的解法

public class ThreeSumHash {

    

    public static List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> result = new ArrayList<>();

        

        if (nums == null || nums.length < 3) {

            return result;

        }

        

        Arrays.sort(nums); // 排序便于去重

        

        for (int i = 0; i < nums.length - 2; i++) {

            // 跳过重复元素

            if (i > 0 && nums[i] == nums[i - 1]) {

                continue;

            }

            

            int target = -nums[i];

            Set<Integer> seen = new HashSet<>();

            

            for (int j = i + 1; j < nums.length; j++) {

                int complement = target - nums[j];

                

                if (seen.contains(complement)) {

                    result.add(Arrays.asList(nums[i], complement, nums[j]));

                    

                    // 跳过重复的三元组

                    while (j + 1 < nums.length && nums[j] == nums[j + 1]) {

                        j++;

                    }

                }

                seen.add(nums[j]);

            }

        }

        

        return result;

    }

}

```

## 字符串处理：字母异位词分组

哈希表在处理字符串分类和分组问题时表现出色，特别是在字母异位词问题上。

```java

// 字母异位词分组

public class GroupAnagrams {

    

    // 方法1：使用排序后的字符串作为键

    public static List<List<String>> groupAnagrams(String[] strs) {

        Map<String, List<String>> anagramMap = new HashMap<>();

        

        for (String str : strs) {

            // 将字符串排序作为哈希键

            char[] chars = str.toCharArray();

            Arrays.sort(chars);

            String key = new String(chars);

            

            // 分组存储

            anagramMap.computeIfAbsent(key, k -> new ArrayList<>()).add(str);

        }

        

        return new ArrayList<>(anagramMap.values());

    }

    

    // 方法2：使用字符计数作为键（避免排序开销）

    public static List<List<String>> groupAnagramsOptimized(String[] strs) {

        Map<String, List<String>> anagramMap = new HashMap<>();

        

        for (String str : strs) {

            // 使用字符计数作为键

            int[] count = new int[26];

            for (char c : str.toCharArray()) {

                count[c - 'a']++;

            }

            

            // 构建计数字符串作为键

            StringBuilder keyBuilder = new StringBuilder();

            for (int i = 0; i < 26; i++) {

                if (count[i] > 0) {

                    keyBuilder.append((char)('a' + i))

                              .append(count[i]);

                }

            }

            String key = keyBuilder.toString();

            

            // 分组存储

            anagramMap.computeIfAbsent(key, k -> new ArrayList<>()).add(str);

        }

        

        return new ArrayList<>(anagramMap.values());

    }

    

    public static void main(String[] args) {

        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};

        List<List<String>> groups = groupAnagrams(strs);

        

        for (List<String> group : groups) {

            System.out.println(group);

        }

    }

}

```

## 高级应用：最长连续序列

这是哈希表应用的一个经典难题，需要在O(n)时间内找到未排序数组中的最长连续序列。

### 基础解法与分析

```java

// 最长连续序列问题

public class LongestConsecutiveSequence {

    

    // 方法1：使用哈希表存储所有数字

    public static int longestConsecutive(int[] nums) {

        if (nums == null || nums.length == 0) {

            return 0;

        }

        

        // 将所有数字存入哈希表

        Set<Integer> numSet = new HashSet<>();

        for (int num : nums) {

            numSet.add(num);

        }

        

        int maxLength = 0;

        

        for (int num : numSet) {

            // 只有当num是序列的起点时才进行计数

            if (!numSet.contains(num - 1)) {

                int currentNum = num;

                int currentLength = 1;

                

                // 向后寻找连续数字

                while (numSet.contains(currentNum + 1)) {

                    currentNum++;

                    currentLength++;

                }

                

                maxLength = Math.max(maxLength, currentLength);

            }<"dve.j9k5.org.cn"><"awx.j9k5.org.cn"><"nfg.j9k5.org.cn">

        }

        

        return maxLength;

    }

    

    // 方法2：使用哈希表记录边界信息（更高效）

    public static int longestConsecutiveOptimized(int[] nums) {

        if (nums == null || nums.length == 0) {

            return 0;

        }

        

        // 使用哈希表记录每个数字所在的连续序列长度

        Map<Integer, Integer> boundaryMap = new HashMap<>();

        int maxLength = 0;

        

        for (int num : nums) {

            // 跳过重复数字

            if (boundaryMap.containsKey(num)) {

                continue;

            }

            

            // 获取左右边界序列的长度

            int leftLength = boundaryMap.getOrDefault(num - 1, 0);

            int rightLength = boundaryMap.getOrDefault(num + 1, 0);

            

            // 当前数字连接的序列总长度

            int currentLength = leftLength + rightLength + 1;

            maxLength = Math.max(maxLength, currentLength);

            

            // 更新边界信息

            boundaryMap.put(num, currentLength); // 当前数字标记为已访问

            boundaryMap.put(num - leftLength, currentLength); // 更新左边界

            boundaryMap.put(num + rightLength, currentLength); // 更新右边界

        }

        

        return maxLength;

    }

    

    // 方法3：带路径压缩的并查集解法

    static class UnionFind {

        Map<Integer, Integer> parent = new HashMap<>();

        Map<Integer, Integer> size = new HashMap<>();

        

        public void add(int x) {

            if (parent.containsKey(x)) return;

            

            parent.put(x, x);

            size.put(x, 1);

            

            // 与相邻数字合并

            if (parent.containsKey(x - 1)) {

                union(x, x - 1);

            }

            if (parent.containsKey(x + 1)) {

                union(x, x + 1);

            }

        }

        

        private int find(int x) {

            if (parent.get(x) != x) {

                parent.put(x, find(parent.get(x))); // 路径压缩

            }

            return parent.get(x);

        }

        

        private void union(int x, int y) {

            int rootX = find(x);

            int rootY = find(y);

            

            if (rootX != rootY) {

                // 按秩合并

                if (size.get(rootX) < size.get(rootY)) {

                    parent.put(rootX, rootY);

                    size.put(rootY, size.get(rootY) + size.get(rootX));

                } else {

                    parent.put(rootY, rootX);

                    size.put(rootX, size.get(rootX) + size.get(rootY));

                }

            }

        }

        

        public int getMaxSize() {

            int max = 0;

            for (int s : size.values()) {

                max = Math.max(max, s);

            }

            return max;

        }

    }

    

    public static int longestConsecutiveUnionFind(int[] nums) {

        UnionFind uf = new UnionFind();

        

        for (int num : nums) {

            uf.add(num);

        }

        

        return uf.getMaxSize();

    }

}

```

## 实时数据处理：LRU缓存机制

哈希表与双向链表的结合可以实现高效的LRU缓存。

```java

// LRU缓存实现：哈希表+双向链表

public class LRUCache {

    

    // 双向链表节点

    class DLinkedNode {

        int key;

        int value;

        DLinkedNode prev;

        DLinkedNode next;

        

        DLinkedNode() {}

        DLinkedNode(int key, int value) {

            this.key = key;

            this.value = value;

        }

    }

    

    private Map<Integer, DLinkedNode> cache = new HashMap<>();

    private int capacity;

    private DLinkedNode head, tail;

    

    public LRUCache(int capacity) {

        this.capacity = capacity;

        // 使用伪头部和伪尾部节点

        head = new DLinkedNode();

        tail = new DLinkedNode();

        head.next = tail;

        tail.prev = head;

    }

    

    public int get(int key) {

        DLinkedNode node = cache.get(key);

        if (node == null) {

            return -1;

        }

        // 如果key存在，先移动到头部

        moveToHead(node);

        return node.value;

    }

    

    public void put(int key, int value) {

        DLinkedNode node = cache.get(key);

        

        if (node == null) {

            // 如果key不存在，创建新节点

            DLinkedNode newNode = new DLinkedNode(key, value);

            cache.put(key, newNode);

            addToHead(newNode);

            

            if (cache.size() > capacity) {

                // 如果超出容量，删除尾部节点

                DLinkedNode tail = removeTail();

                cache.remove(tail.key);

            }

        } else {

            // 如果key存在，更新值并移动到头部

            node.value = value;

            moveToHead(node);

        }

    }

    

    private void addToHead(DLinkedNode node) {

        node.prev = head;

        node.next = head.next;

        head.next.prev = node;

        head.next = node;

    }

    

    private void removeNode(DLinkedNode node) {

        node.prev.next = node.next;

        node.next.prev = node.prev;

    }

    

    private void moveToHead(DLinkedNode node) {

        removeNode(node);

        addToHead(node);

    }<"zsf.j9k5.org.cn"><"qzx.j9k5.org.cn"><"dvb.j9k5.org.cn">

    

    private DLinkedNode removeTail() {

        DLinkedNode res = tail.prev;

        removeNode(res);

        return res;

    }

}

```

## 模式识别：重复元素检测

哈希表在检测重复元素方面有天然优势。

```java

// 各种重复元素检测问题

public class DuplicateDetection {

    

    // 检测数组是否有重复元素

    public static boolean containsDuplicate(int[] nums) {

        Set<Integer> seen = new HashSet<>();

        for (int num : nums) {

            if (!seen.add(num)) {

                return true;

            }

        }

        return false;

    }

    

    // 寻找重复数（数组长度为n+1，元素范围1-n）

    public static int findDuplicate(int[] nums) {

        // 使用Floyd判圈算法（快慢指针）

        int slow = nums[0];

        int fast = nums[0];

        

        // 第一阶段：寻找相遇点

        do {

            slow = nums[slow];

            fast = nums[nums[fast]];

        } while (slow != fast);

        

        // 第二阶段：寻找环入口

        int ptr1 = nums[0];

        int ptr2 = slow;

        while (ptr1 != ptr2) {

            ptr1 = nums[ptr1];

            ptr2 = nums[ptr2];

        }

        

        return ptr1;

    }

    

    // 寻找数组中重复两次的元素

    public static List<Integer> findDuplicates(int[] nums) {

        List<Integer> result = new ArrayList<>();

        

        for (int i = 0; i < nums.length; i++) {

            int index = Math.abs(nums[i]) - 1;

            if (nums[index] < 0) {

                result.add(Math.abs(nums[i]));

            } else {

                nums[index] = -nums[index];

            }

        }

        

        // 恢复原数组

        for (int i = 0; i < nums.length; i++) {

            nums[i] = Math.abs(nums[i]);

        }

        

        return result;

    }

}

```

## 性能优化与实战技巧

### 哈希函数选择与冲突处理

```java

// 自定义哈希函数示例

public class CustomHashFunction {

    

    // 字符串的哈希函数（多项式滚动哈希）

    public static int polynomialHash(String s, int base, int mod) {

        long hash = 0;

        long power = 1;

        

        for (int i = 0; i < s.length(); i++) {

            hash = (hash + (s.charAt(i) - 'a' + 1) * power) % mod;

            power = (power * base) % mod;

        }

        

        return (int) hash;

    }

    

    // 数组的哈希函数

    public static int arrayHash(int[] arr) {

        int hash = 0;

        int prime = 31; // 常用质数

        

        for (int num : arr) {

            hash = hash * prime + num;

        }

        

        return hash;

    }

}

// 处理哈希冲突的链地址法实现

public class SeparateChainingHashTable<K, V> {

    

    private static class Entry<K, V> {

        K key;

        V value;

        Entry<K, V> next;

        

        Entry(K key, V value) {

            this.key = key;

            this.value = value;

        }

    }

    

    private Entry<K, V>[] table;

    private int capacity;

    private int size;

    

    @SuppressWarnings("unchecked")

    public SeparateChainingHashTable(int capacity) {

        this.capacity = capacity;

        this.table = new Entry[capacity];

        this.size = 0;

    }

    

    private int hash(K key) {

        return Math.abs(key.hashCode()) % capacity;

    }

    

    public void put(K key, V value) {

        int index = hash(key);

        Entry<K, V> entry = table[index];

        

        // 查找是否已存在

        while (entry != null) {

            if (entry.key.equals(key)) {

                entry.value = value; // 更新值

                return;

            }

            entry = entry.next;

        }

        

        // 插入新节点到链表头部

        Entry<K, V> newEntry = new Entry<>(key, value);

        newEntry.next = table[index];

        table[index] = newEntry;

        size++;

    }

    

    public V get(K key) {

        int index = hash(key);

        Entry<K, V> entry = table[index];

        

        while (entry != null) {

            if (entry.key.equals(key)) {

                return entry.value;

            }

            entry = entry.next;

        }

        

        return null;

    }

}

```

### 内存优化技巧

```java

// 使用原始类型避免装箱开销

public class PrimitiveHashMap {

    

    // 使用数组模拟哈希表处理整数

    public static class IntHashSet {

        private boolean[] present;

        private int offset; // 处理负数

        

        public IntHashSet(int min, int max) {

            this.offset = -min;

            this.present = new boolean[max - min + 1];

        }

        

        public void add(int value) {

            present[value + offset] = true;

        }

        

        public boolean contains(int value) {

            return present[value + offset];

        }

    }

    

    // 位图实现超大整数集合

    public static class BitmapSet {

        private long[] bits;

        

        public BitmapSet(int maxValue) {

            // 每个long可以存储64个标志位

            this.bits = new long[(maxValue >> 6) + 1];

        }

        

        public void add(int value) {

            int index = value >> 6; // value / 64

            int bit = value & 63;   // value % 64

            bits[index] |= (1L << bit);

        }

        

        public boolean contains(int value) {

            int index = value >> 6;

            int bit = value & 63;

            return (bits[index] & (1L << bit)) != 0;

        }

    }

}

```

## 总结：哈希表的算法思维

哈希表不仅是数据结构，更是一种算法思维。从两数之和到最长连续序列，我们看到了哈希表在解决问题时的通用模式：

1. **查找优化**：将线性查找优化为常数时间查找

2. **状态记录**：记录已访问元素或中间结果

3. **分组聚合**：根据特定键值进行数据分组

4. **边界维护**：在复杂问题中维护关键边界信息

掌握哈希表的关键在于：

- 理解哈希函数的设计原理

- 掌握冲突处理策略

- 根据问题特点选择合适的哈希结构

- 权衡时间与空间复杂度

在实际应用中，哈希表经常与其他数据结构（如链表、堆、树）结合，形成更复杂的复合结构。通过不断练习和思考，哈希表思维可以内化为解决复杂问题的直觉能力，在算法设计和系统优化中发挥重要作用。

记住，优秀算法的核心在于找到问题的本质，并选择合适的数据结构来高效表达和操作问题空间。哈希表正是这种思想的完美体现——通过建立映射关系，将复杂问题转化为简单查找。