哈希表原理与应用

引言

哈希表是最常用的数据结构之一，提供O(1)的查找、插入和删除操作。本文深入讲解哈希表原理和经典应用。

一、哈希表基础

1.1 哈希表原理

// 简单哈希表实现
public class SimpleHashMap<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 size;
    private static final int DEFAULT_CAPACITY = 16;
    
    @SuppressWarnings("unchecked")
    public SimpleHashMap() {
        table = new Entry[DEFAULT_CAPACITY];
    }
    
    // 哈希函数
    private int hash(K key) {
        return Math.abs(key.hashCode() % table.length);
    }
    
    // 插入
    public void put(K key, V value) {
        int index = hash(key);
        Entry<K, V> newEntry = new Entry<>(key, value);
        
        if (table[index] == null) {
            table[index] = newEntry;
        } else {
            Entry<K, V> current = table[index];
            while (true) {
                if (current.key.equals(key)) {
                    current.value = value;
                    return;
                }
                if (current.next == null) {
                    current.next = newEntry;
                    break;
                }
                current = current.next;
            }
        }
        size++;
    }
    
    // 查找
    public V get(K key) {
        int index = hash(key);
        Entry<K, V> current = table[index];
        
        while (current != null) {
            if (current.key.equals(key)) {
                return current.value;
            }
            current = current.next;
        }
        
        return null;
    }
}

1.2 哈希冲突解决

1. 链地址法（Chaining）

1 2	// HashMap使用的方法 // 每个桶存储一个链表（JDK 8+可能转为红黑树）

2. 开放寻址法（Open Addressing）

// 线性探测
int index = hash(key);
while (table[index] != null) {
    index = (index + 1) % table.length;
}

二、哈希表经典题目

2.1 两数之和（LeetCode 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[]{};
}

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

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

2.3 最长连续序列（LeetCode 128）

public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        set.add(num);
    }
    
    int maxLength = 0;
    
    for (int num : set) {
        if (!set.contains(num - 1)) {
            int currentNum = num;
            int currentLength = 1;
            
            while (set.contains(currentNum + 1)) {
                currentNum++;
                currentLength++;
            }
            
            maxLength = Math.max(maxLength, currentLength);
        }
    }
    
    return maxLength;
}