哈希算法题目：设计一个支持动态扩容的哈希表（使用链地址法）

题目描述：设计一个哈希表，支持插入（put）、删除（remove）和查找（get）操作。该哈希表应使用链地址法解决哈希冲突，并支持动态扩容和缩容以维持高效的性能。当哈希表中的元素数量超过负载因子阈值时，自动扩容（例如，扩容为原大小的两倍）；当元素数量过少时，自动缩容以节省空间。

解题步骤：

1. 理解基本组件：

   • 哈希表由一个固定大小的数组（桶数组）组成，每个数组位置是一个桶（bucket）。
   • 每个桶是一个链表（或列表），用于存储键值对。当多个键哈希到同一索引时，将它们链接在同一个桶中。
   • 负载因子（load factor）定义为元素总数除以桶数组大小。例如，负载因子阈值设为0.75，当超过时触发扩容。

2. 初始化哈希表：

   • 设置初始桶数组大小（如16）、负载因子阈值（如0.75）和当前元素计数（初始为0）。
   • 创建桶数组，每个桶初始化为空链表。

3. 哈希函数设计：

   • 使用键的哈希码（通过键的hashCode方法获取）对桶数组大小取模，得到索引：index = key.hashCode() % bucketArray.length。
   • 注意：取模操作应处理负数哈希码，例如使用 (key.hashCode() & 0x7fffffff) % bucketArray.length 确保索引非负。

4. 插入操作（put）：

   • 计算键的索引，定位到对应桶。
   • 遍历桶链表：
     • 如果找到相同键，更新其值并返回。
     • 如果未找到，在链表末尾添加新键值对。
   • 增加元素计数，检查当前负载因子（元素计数/桶数组大小）是否超过阈值。如果超过，调用扩容方法。

5. 查找操作（get）：

   • 计算键的索引，遍历对应桶链表，比较键是否相等。找到则返回值，否则返回null。

6. 删除操作（remove）：

   • 计算键的索引，遍历桶链表找到该键，从链表中移除键值对。
   • 减少元素计数，检查是否需要缩容（例如，负载因子低于0.25且桶数组大小大于初始大小）。如果需要，调用缩容方法。

7. 动态扩容：

   • 当负载因子超过阈值时，创建新桶数组（大小为原数组两倍）。
   • 遍历原桶数组的每个桶，重新计算每个键值对在新数组中的索引（因为数组大小改变，取模结果可能变化）。
   • 将键值对移动到新桶数组的对应桶中。
   • 更新哈希表的桶数组引用为新数组。

8. 动态缩容：

   • 当负载因子过低（如低于0.25）且桶数组大小大于初始大小时，创建新桶数组（大小为原数组一半）。
   • 类似扩容，重新哈希所有键值对到新数组。
   • 缩容可避免空间浪费，但需谨慎设置阈值以防止频繁扩容缩容。

9. 复杂度分析：

   • 平均情况下，插入、查找、删除的时间复杂度为O(1)，假设哈希函数均匀分布键。
   • 最坏情况（所有键哈希到同一桶）为O(n)，但通过动态调整大小可降低概率。

示例代码框架（Java）：

class MyHashMap {
    private ListNode[] buckets;
    private int size;
    private double loadFactor = 0.75;
    private static final int INIT_CAPACITY = 16;

    public MyHashMap() {
        buckets = new ListNode[INIT_CAPACITY];
        size = 0;
    }

    public void put(int key, int value) {
        // 实现插入逻辑，包括扩容检查
    }

    public int get(int key) {
        // 实现查找逻辑
    }

    public void remove(int key) {
        // 实现删除逻辑，包括缩容检查
    }

    private void rehash(int newCapacity) {
        // 实现重新哈希逻辑
    }
}

通过以上步骤，哈希表能在保持高效操作的同时自适应数据量变化。