设计和实现一个支持键值对存储的微型哈希表（带动态扩容和冲突解决）

题目描述
设计并实现一个微型哈希表，支持基本的键值对存储操作：put(key, value) 插入或更新键值对，get(key) 根据键获取值，remove(key) 删除键值对。该哈希表需具备动态扩容能力，以在数据量增长时保持性能，并采用链地址法解决哈希冲突。

解题过程循序渐进讲解

1. 哈希表核心设计
哈希表是一种通过哈希函数将键映射到数组索引的数据结构，从而实现近似 O(1) 时间复杂度的查找、插入和删除。我们需要解决两个关键问题：

• 哈希函数：将任意键转换为数组范围内的整数索引。这里我们使用简单哈希函数：hash(key) = key.hashCode() % capacity，并对负数取绝对值。
• 冲突解决：当不同键映射到同一索引时，采用链地址法，即每个数组槽位存储一个链表（或数组），存放所有映射到该位置的键值对。

2. 数据结构定义

• 定义一个内部类 Entry 表示键值对节点，包含 key、value 和指向下一个节点的 next 指针（用于链表）。
• 哈希表主体是一个 Entry 数组 table，每个数组元素是链表的头节点。
• 记录当前元素数量 size 和当前数组容量 capacity。
• 设置负载因子（如 0.75），当 size / capacity 超过负载因子时触发扩容。

3. 基本操作实现

• put(key, value)：
  1. 计算索引：index = hash(key) % capacity。
  2. 遍历该索引处的链表：
     • 如果找到相同 key，更新其 value 并返回旧值。
     • 如果未找到，在链表头部插入新 Entry（头插法，O(1) 时间）。
  3. 增加 size，若 size / capacity > loadFactor，则调用扩容函数。
• get(key)：
  1. 计算索引，遍历对应链表查找 key，找到则返回值，否则返回 null。
• remove(key)：
  1. 计算索引，遍历链表找到目标节点，调整链表指针删除节点。
  2. 减少 size，返回被删除的值。

4. 动态扩容机制

• 当负载因子超过阈值时，创建一个两倍大小的新数组。
• 遍历原数组的所有链表节点，对每个节点重新计算在新数组中的索引（因为容量改变，索引可能不同），并将节点插入到新数组对应链表的头部。
• 用新数组替换旧数组。扩容均摊时间复杂度为 O(n)，但可保持操作的平均 O(1) 性能。

5. 边界与细节处理

• 键为 null 的情况：通常哈希表不允许 null 键，可抛出异常或特殊处理。
• 删除操作时需正确处理链表头节点删除和中间节点删除。
• 扩容后，原链表中的节点顺序可能反转（因头插法），但不影响功能。

6. 简单代码框架示例（Java风格）

class MyHashMap<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 = 0, capacity = 16;
    private final float loadFactor = 0.75f;
    
    public MyHashMap() { table = new Entry[capacity]; }
    
    private int hash(K key) { return Math.abs(key.hashCode()) % capacity; }
    
    public void put(K key, V value) {
        int idx = hash(key);
        Entry<K, V> cur = table[idx];
        while (cur != null) {
            if (cur.key.equals(key)) { cur.value = value; return; }
            cur = cur.next;
        }
        Entry<K, V> newEntry = new Entry<>(key, value);
        newEntry.next = table[idx]; // 头插
        table[idx] = newEntry;
        size++;
        if (size > capacity * loadFactor) resize();
    }
    
    public V get(K key) {
        int idx = hash(key);
        Entry<K, V> cur = table[idx];
        while (cur != null) {
            if (cur.key.equals(key)) return cur.value;
            cur = cur.next;
        }
        return null;
    }
    
    public void remove(K key) {
        int idx = hash(key);
        Entry<K, V> cur = table[idx], prev = null;
        while (cur != null) {
            if (cur.key.equals(key)) {
                if (prev == null) table[idx] = cur.next;
                else prev.next = cur.next;
                size--; return;
            }
            prev = cur; cur = cur.next;
        }
    }
    
    private void resize() {
        capacity *= 2;
        Entry<K, V>[] newTable = new Entry[capacity];
        for (Entry<K, V> head : table) {
            while (head != null) {
                Entry<K, V> next = head.next;
                int newIdx = Math.abs(head.key.hashCode()) % capacity;
                head.next = newTable[newIdx]; // 头插到新数组
                newTable[newIdx] = head;
                head = next;
            }
        }
        table = newTable;
    }
}

7. 复杂度分析

• 平均情况：插入、查找、删除均为 O(1)，因链表平均长度受负载因子控制。
• 最坏情况：所有键哈希冲突，链表长度为 n，操作退化为 O(n)。良好哈希函数可避免此情况。
• 空间复杂度：O(capacity + size)。

总结
本设计实现了支持动态扩容和冲突解决的微型哈希表，核心在于链地址法处理冲突、负载因子触发扩容、以及重新哈希迁移数据。这是理解标准哈希表实现的基础，后续可优化为红黑树替代链表（如 Java 8+ HashMap），或引入再哈希、布谷鸟哈希等高级冲突解决方法。