每日算法 — 使用java实现哈希表：链地址法与开放寻址冲突解决

算法背景

哈希表（Hash Table）是一种通过哈希函数将键映射到表中位置来实现快速查找的数据结构。理想情况下，查找、插入和删除操作的时间复杂度均为 O(1)。然而，当不同的键映射到同一位置时，就会发生冲突（Collision）。解决冲突是哈希表设计的核心问题。

常见的冲突解决策略有两种：链地址法（Separate Chaining）和开放寻址法（Open Addressing）。Java中的 HashMap 底层采用链地址法（JDK 8后链表长度超过阈值会转为红黑树），而 ThreadLocal 则使用开放寻址法。

核心思路

链地址法：每个哈希桶维护一个链表（或红黑树），所有映射到同一位置的键值对都存储在该链表中。查找时需要遍历链表。

开放寻址法：所有键值对都存储在哈希表数组本身中。当发生冲突时，按照某种探测序列（线性探测、二次探测、双重哈希）寻找下一个空闲位置。

Java实现

import java.util.ArrayList;
import java.util.List;

/**
 * 自定义哈希表实现
 * 采用链地址法解决冲突，支持动态扩容
 */
public class CustomHashMap<K, V> {

    // 默认初始容量
    private static final int DEFAULT_CAPACITY = 16;
    // 负载因子阈值
    private static final float LOAD_FACTOR = 0.75f;

    // 哈希桶数组，每个桶是一个链表
    private Node<K, V>[] buckets;
    private int size;
    private int capacity;
    private int threshold; // 扩容阈值

    /**
     * 链表节点
     */
    private static class Node<K, V> {
        final K key;
        V value;
        Node<K, V> next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    @SuppressWarnings("unchecked")
    public CustomHashMap() {
        this.capacity = DEFAULT_CAPACITY;
        this.threshold = (int) (capacity * LOAD_FACTOR);
        this.buckets = new Node[capacity];
        this.size = 0;
    }

    /**
     * 哈希函数：将key映射到数组下标
     */
    private int hash(K key) {
        if (key == null) return 0;
        int h = key.hashCode();
        // 扰动函数：让高位也参与运算，减少冲突
        return (h ^ (h >>> 16)) & (capacity - 1);
    }

    /**
     * 放入键值对
     */
    public void put(K key, V value) {
        int index = hash(key);
        Node<K, V> head = buckets[index];

        // 查找是否已存在该key
        Node<K, V> curr = head;
        while (curr != null) {
            if (curr.key.equals(key)) {
                curr.value = value; // 更新值
                return;
            }
            curr = curr.next;
        }

        // 头插法插入新节点
        Node<K, V> newNode = new Node<>(key, value);
        newNode.next = head;
        buckets[index] = newNode;
        size++;

        // 检查是否需要扩容
        if (size > threshold) {
            resize();
        }
    }

    /**
     * 根据key获取value
     */
    public V get(K key) {
        int index = hash(key);
        Node<K, V> curr = buckets[index];

        while (curr != null) {
            if (curr.key.equals(key)) {
                return curr.value;
            }
            curr = curr.next;
        }
        return null;
    }

    /**
     * 删除键值对
     */
    public V remove(K key) {
        int index = hash(key);
        Node<K, V> curr = buckets[index];
        Node<K, V> prev = null;

        while (curr != null) {
            if (curr.key.equals(key)) {
                V oldValue = curr.value;
                if (prev == null) {
                    buckets[index] = curr.next;
                } else {
                    prev.next = curr.next;
                }
                size--;
                return oldValue;
            }
            prev = curr;
            curr = curr.next;
        }
        return null;
    }

    /**
     * 扩容：容量翻倍，重新哈希所有元素
     */
    @SuppressWarnings("unchecked")
    private void resize() {
        Node<K, V>[] oldBuckets = buckets;
        capacity *= 2;
        threshold = (int) (capacity * LOAD_FACTOR);
        buckets = new Node[capacity];
        size = 0;

        // 重新插入所有元素
        for (Node<K, V> head : oldBuckets) {
            while (head != null) {
                put(head.key, head.value);
                head = head.next;
            }
        }
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 主函数：测试与演示
     */
    public static void main(String[] args) {
        CustomHashMap<String, Integer> map = new CustomHashMap<>();

        // 插入测试
        String[] keys = {"apple", "banana", "cherry", "date", "elderberry"};
        int[] values = {100, 200, 300, 400, 500};

        System.out.println("=== 插入操作 ===");
        for (int i = 0; i < keys.length; i++) {
            map.put(keys[i], values[i]);
            System.out.printf("put(%s, %d)%n", keys[i], values[i]);
        }
        System.out.println("当前大小: " + map.size());

        // 查询测试
        System.out.println("\n=== 查询操作 ===");
        for (String key : keys) {
            System.out.printf("get(%s) = %d%n", key, map.get(key));
        }

        // 更新测试
        System.out.println("\n=== 更新操作 ===");
        map.put("apple", 150);
        System.out.println("更新后 get(apple) = " + map.get("apple"));

        // 删除测试
        System.out.println("\n=== 删除操作 ===");
        map.remove("banana");
        System.out.println("删除banana后大小: " + map.size());
        System.out.println("get(banana) = " + map.get("banana"));

        // 冲突测试：大量数据
        System.out.println("\n=== 扩容测试 ===");
        CustomHashMap<Integer, String> intMap = new CustomHashMap<>();
        for (int i = 0; i < 100; i++) {
            intMap.put(i, "value_" + i);
        }
        System.out.println("插入100个元素后大小: " + intMap.size());
        System.out.println("get(50) = " + intMap.get(50));
        System.out.println("get(99) = " + intMap.get(99));
    }
}

开放寻址法实现（线性探测）

/**
 * 开放寻址法哈希表（线性探测）
 */
class OpenAddressingHashMap<K, V> {
    private static final int DEFAULT_CAPACITY = 16;
    private static final float LOAD_FACTOR = 0.75f;
    private static final Object TOMBSTONE = new Object(); // 墓碑标记

    private Entry<K, V>[] table;
    private int size;
    private int capacity;
    private int threshold;

    @SuppressWarnings("unchecked")
    private static class Entry<K, V> {
        K key;
        V value;
        boolean active; // 是否为有效条目

        Entry(K key, V value) {
            this.key = key;
            this.value = value;
            this.active = true;
        }
    }

    @SuppressWarnings("unchecked")
    public OpenAddressingHashMap() {
        this.capacity = DEFAULT_CAPACITY;
        this.threshold = (int) (capacity * LOAD_FACTOR);
        this.table = new Entry[capacity];
    }

    private int hash(K key) {
        if (key == null) return 0;
        int h = key.hashCode();
        return (h ^ (h >>> 16)) & (capacity - 1);
    }

    public void put(K key, V value) {
        if (size >= threshold) resize();

        int index = hash(key);
        int i = 0;
        int tombstoneIndex = -1;

        while (true) {
            int probeIndex = (index + i) & (capacity - 1);
            Entry<K, V> entry = table[probeIndex];

            if (entry == null) {
                // 找到空位
                int insertIndex = (tombstoneIndex != -1) ? tombstoneIndex : probeIndex;
                table[insertIndex] = new Entry<>(key, value);
                size++;
                return;
            }

            if (!entry.active) {
                if (tombstoneIndex == -1) tombstoneIndex = probeIndex;
            } else if (entry.key.equals(key)) {
                entry.value = value; // 更新
                return;
            }

            i++;
        }
    }

    public V get(K key) {
        int index = hash(key);
        int i = 0;

        while (i < capacity) {
            int probeIndex = (index + i) & (capacity - 1);
            Entry<K, V> entry = table[probeIndex];

            if (entry == null) return null;
            if (entry.active && entry.key.equals(key)) return entry.value;

            i++;
        }
        return null;
    }

    @SuppressWarnings("unchecked")
    private void resize() {
        Entry<K, V>[] oldTable = table;
        capacity *= 2;
        threshold = (int) (capacity * LOAD_FACTOR);
        table = new Entry[capacity];
        size = 0;

        for (Entry<K, V> entry : oldTable) {
            if (entry != null && entry.active) {
                put(entry.key, entry.value);
            }
        }
    }
}

复杂度分析

应用场景

• 缓存系统：LRU缓存、数据库查询缓存的核心数据结构
• 去重统计：快速判断元素是否已存在
• 符号表：编译器中变量名到地址的映射
• 字符串匹配：Rabin-Karp算法利用滚动哈希加速匹配

总结

本文从零实现了一个基于链地址法的哈希表，涵盖了哈希函数设计、冲突解决、动态扩容等核心机制，并展示了开放寻址法的线性探测实现。理解哈希表的内部原理，有助于更好地使用Java标准库中的 HashMap 和 HashSet，也能在遇到性能瓶颈时做出正确的调优决策。