一、项目背景详细介绍

在学习 数据结构与算法 的过程中，哈希表（Hash Table）是一个非常重要的主题。它为我们提供了平均 O(1) 的时间复杂度来进行插入、删除和查找，是现代编程语言中常用的底层数据结构之一。

在 Java 中，HashMap 是哈希表的典型实现，广泛应用于业务逻辑开发。但其源码复杂，涉及数组、链表、红黑树等多种数据结构，对于初学者来说难度较大。

因此，教学过程中，我们常常设计 简化版 HashMap 来帮助学习者理解其底层原理。上一节我们实现了基于 ArrayList 的版本，而本文将介绍另一种常见实现方式：使用链表数组（Array of LinkedList）来实现通用哈希图算法。

链表数组是一种简单直接的哈希表存储结构：

• 使用数组存放“桶”；

• 每个桶存放一个链表，用来解决哈希冲突；

• 当插入新的键值对时，先通过哈希函数确定桶位置，再在链表中查找是否存在该键，如果存在则更新，否则插入。

这种结构简单易懂，直接反映了哈希表的“数组 + 链表”核心思想，是学习哈希表的绝佳入门案例。

---

二、项目需求详细介绍

本项目的需求如下：

1. 实现一个泛型类 MyHashTable<K, V>

   • 支持任意类型的键和值；

   • 使用数组存储桶；

   • 每个桶是一个链表，用于存储发生哈希冲突的键值对。

2. 支持基本操作

   • 插入（put）

   • 查找（get）

   • 删除（remove）

   • 判断是否包含某个键（containsKey）

   • 获取大小（size）

   • 判断是否为空（isEmpty）

3. 设计哈希函数

   • 使用 hashCode() 和取模运算来定位桶索引；

   • 确保索引为非负数。

4. 扩容

   • 当装载因子超过阈值（如 0.75）时，扩容为原来的 2 倍；

   • 扩容后需重新分配键值对（Rehash）。

5. 测试用例

   • 插入、获取、删除数据；

   • 检查不存在的键；

   • 验证扩容是否成功。

---

三、相关技术详细介绍

为了实现哈希表，我们需要掌握以下技术：

1. 数组和链表的结合

• 使用数组来存储桶，每个桶是一个链表；

• 链表用于存储发生哈希冲突的键值对；

• 优点：结构直观，操作简单。

2. 哈希函数

• 使用对象的 hashCode()；

• 对 capacity 取模，得到桶索引；

• 处理负数：Math.abs(hashCode % capacity)。

3. 链地址法解决冲突

• 当多个键映射到同一个桶时，将它们存放在同一个链表中；

• 插入时若键已存在则更新，否则插入新节点。

4. 装载因子与扩容

• 装载因子 = size / capacity；

• 当超过设定阈值时，进行扩容，避免链表过长，保证 O(1) 平均复杂度。

5. 泛型支持

• 使用 <K, V> 泛型类；

• 支持任意键值类型，增强通用性。

---

四、实现思路详细介绍

1. 定义节点类 Node<K, V>

   • 存储单个键值对；

   • 包含 key、value、next 引用。

2. 初始化桶数组

   • 使用 Node<K, V>[] table 数组；

   • 初始容量设为 16。

3. put 方法

   • 根据哈希函数找到桶索引；

   • 遍历链表：

     • 若存在相同 key，则更新 value；

     • 否则新建节点，插入链表头部（或尾部）。

   • 更新 size；

   • 检查是否需要扩容。

4. get 方法

   • 根据哈希函数找到桶；

   • 遍历链表，若找到 key 则返回 value，否则返回 null。

5. remove 方法

   • 遍历桶中的链表，找到并删除对应节点。

6. 扩容方法

   • 新建数组，容量翻倍；

   • 重新分配所有节点。

---

五、完整实现代码

// 文件：MyHashTable.java
@SuppressWarnings("unchecked")
public class MyHashTable<K, V> {
    // 默认初始容量
    private static final int INITIAL_CAPACITY = 16;
    // 装载因子阈值
    private static final float LOAD_FACTOR = 0.75f;

    // 节点类（链表节点）
    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V> next;

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

    private Node<K, V>[] table; // 桶数组
    private int capacity;
    private int size;

    // 构造方法
    public MyHashTable() {
        this.capacity = INITIAL_CAPACITY;
        this.table = new Node[capacity];
        this.size = 0;
    }

    // 计算索引
    private int getIndex(K key) {
        return Math.abs(key.hashCode() % capacity);
    }

    // 插入或更新
    public void put(K key, V value) {
        int index = getIndex(key);
        Node<K, V> head = table[index];

        // 遍历链表，看是否存在相同 key
        Node<K, V> current = head;
        while (current != null) {
            if (current.key.equals(key)) {
                current.value = value; // 更新
                return;
            }
            current = current.next;
        }

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

        if ((float) size / capacity > LOAD_FACTOR) {
            resize();
        }
    }

    // 获取值
    public V get(K key) {
        int index = getIndex(key);
        Node<K, V> current = table[index];
        while (current != null) {
            if (current.key.equals(key)) {
                return current.value;
            }
            current = current.next;
        }
        return null;
    }

    // 删除键值对
    public void remove(K key) {
        int index = getIndex(key);
        Node<K, V> current = table[index];
        Node<K, V> prev = null;

        while (current != null) {
            if (current.key.equals(key)) {
                if (prev == null) {
                    table[index] = current.next;
                } else {
                    prev.next = current.next;
                }
                size--;
                return;
            }
            prev = current;
            current = current.next;
        }
    }

    // 是否包含某个键
    public boolean containsKey(K key) {
        return get(key) != null;
    }

    // 当前大小
    public int size() {
        return size;
    }

    // 是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 扩容
    private void resize() {
        int newCapacity = capacity * 2;
        Node<K, V>[] newTable = new Node[newCapacity];

        // 重新哈希所有节点
        for (int i = 0; i < capacity; i++) {
            Node<K, V> current = table[i];
            while (current != null) {
                Node<K, V> next = current.next;
                int newIndex = Math.abs(current.key.hashCode() % newCapacity);
                current.next = newTable[newIndex];
                newTable[newIndex] = current;
                current = next;
            }
        }
        table = newTable;
        capacity = newCapacity;
    }

    // 测试方法
    public static void main(String[] args) {
        MyHashTable<String, Integer> map = new MyHashTable<>();
        map.put("apple", 1);
        map.put("banana", 2);
        map.put("orange", 3);

        System.out.println("apple -> " + map.get("apple"));
        System.out.println("banana -> " + map.get("banana"));
        System.out.println("orange -> " + map.get("orange"));

        System.out.println("包含 banana? " + map.containsKey("banana"));
        map.remove("banana");
        System.out.println("删除后包含 banana? " + map.containsKey("banana"));

        System.out.println("当前大小: " + map.size());
        System.out.println("是否为空: " + map.isEmpty());
    }
}

六、代码详细解读

1. Node 类

   • 每个 Node 存储一个键值对；

   • next 指向下一个节点，用于构建链表。

2. put 方法

   • 计算桶索引；

   • 遍历链表，如果存在相同 key，则更新 value；

   • 否则创建新节点，插入链表头部。

3. get 方法

   • 遍历链表，查找对应 key，返回值。

4. remove 方法

   • 遍历链表，找到目标节点，调整前后节点引用，实现删除。

5. resize 方法

   • 容量翻倍；

   • 将所有节点重新分配到新数组。

---

七、项目详细总结

本文实现了一个基于 链表数组 的通用哈希图（类似 HashMap），支持插入、查找、删除、扩容等功能。其实现方式与 Java 标准库 HashMap 的底层思想一致：数组 + 链表。

优点：

• 代码简洁，容易理解；

• 支持泛型，通用性强；

• 保持了 HashMap 的核心原理。

缺点：

• 没有支持线程安全；

• 没有实现链表过长时转红黑树优化。

---

八、项目常见问题及解答

问题1：为什么使用链表解决冲突？
答：链表插入和删除方便，不需要移动元素，适合存储冲突键值对。

问题2：哈希冲突多时怎么办？
答：需要扩容，降低装载因子；高级实现可转为红黑树。

问题3：是否支持 null 键？
答：目前实现未特殊处理 null，可以扩展设计一个专门槽位存放 null。

问题4：扩容是否昂贵？
答：扩容时需要重新哈希所有元素，代价较高，但扩容不频繁，所以平均摊销代价仍然 O(1)。

---

九、扩展方向与性能优化

1. 支持 null 键与 null 值；

2. 链表转红黑树，提高高冲突场景下的效率；

3. 线程安全版本，支持并发操作；

4. 自定义负载因子；

5. 开放寻址法 实现对比。