面试题：让你设计一个 HashMap ，怎么设计？

设计一个 HashMap 是一个经典的面试题，涉及数据结构、算法、并发等多个方面。以下是设计一个简化版 HashMap 的详细思路和实现方案。

1. 需求分析

核心功能

插入键值对：支持插入键值对（key-value pair）。
查找键值对：根据键查找对应的值。
删除键值对：根据键删除对应的键值对。
动态扩容：当存储的元素过多时，自动扩容以保持性能。

非功能需求

高性能：插入、查找、删除操作的时间复杂度接近 O(1)。
内存效率：尽量减少内存浪费。
线程安全（可选）：支持多线程并发访问。

2. 数据结构设计

核心数据结构

数组：用于存储键值对（桶数组）。
链表：用于解决哈希冲突（链地址法）。

键值对节点

class Entry<K, V> {
    K key;
    V value;
    Entry<K, V> next; // 链表的下一个节点

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

3. 核心算法设计

哈希函数

使用 key.hashCode() 计算哈希值。
对哈希值取模，确定桶的位置：int index = hash(key) % capacity;

解决哈希冲突

链地址法：将哈希冲突的键值对存储在链表中。

动态扩容

当元素数量超过负载因子（load factor）时，扩容桶数组。
扩容后重新哈希所有键值对。

4. 详细实现

初始化

public class MyHashMap<K, V> {
    private static final int DEFAULT_CAPACITY = 16; // 默认容量
    private static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认负载因子

    private Entry<K, V>[] table; // 桶数组
    private int size; // 元素数量
    private int capacity; // 桶数组容量
    private float loadFactor; // 负载因子

    public MyHashMap() {
        this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    public MyHashMap(int capacity, float loadFactor) {
        this.capacity = capacity;
        this.loadFactor = loadFactor;
        this.table = new Entry[capacity];
    }
}

插入键值对

public void put(K key, V value) {
    if (key == null) {
        throw new IllegalArgumentException("Key cannot be null");
    }

    // 检查是否需要扩容
    if (size >= capacity * loadFactor) {
        resize();
    }

    // 计算桶的位置
    int index = hash(key) % capacity;

    // 插入到链表头部
    Entry<K, V> entry = new Entry<>(key, value);
    entry.next = table[index];
    table[index] = entry;
    size++;
}

private int hash(K key) {
    return key.hashCode() & 0x7FFFFFFF; // 取正数
}

private void resize() {
    capacity *= 2; // 扩容为原来的两倍
    Entry<K, V>[] newTable = new Entry[capacity];

    // 重新哈希所有键值对
    for (Entry<K, V> entry : table) {
        while (entry != null) {
            int index = hash(entry.key) % capacity;
            Entry<K, V> next = entry.next;
            entry.next = newTable[index];
            newTable[index] = entry;
            entry = next;
        }
    }

    table = newTable;
}

查找键值对

public V get(K key) {
    if (key == null) {
        throw new IllegalArgumentException("Key cannot be null");
    }

    // 计算桶的位置
    int index = hash(key) % capacity;

    // 遍历链表
    Entry<K, V> entry = table[index];
    while (entry != null) {
        if (entry.key.equals(key)) {
            return entry.value;
        }
        entry = entry.next;
    }

    return null; // 未找到
}

删除键值对

public void remove(K key) {
    if (key == null) {
        throw new IllegalArgumentException("Key cannot be null");
    }

    // 计算桶的位置
    int index = hash(key) % capacity;

    // 遍历链表
    Entry<K, V> prev = null;
    Entry<K, V> entry = table[index];
    while (entry != null) {
        if (entry.key.equals(key)) {
            if (prev == null) {
                table[index] = entry.next; // 删除链表头部
            } else {
                prev.next = entry.next; // 删除链表中间或尾部
            }
            size--;
            return;
        }
        prev = entry;
        entry = entry.next;
    }
}

5. 关键问题与解决方案

1. 哈希冲突

解决方案：使用链地址法（链表）解决冲突。

2. 动态扩容

解决方案：当元素数量超过负载因子时，扩容桶数组并重新哈希。

3. 性能优化

解决方案：
- 使用高效的哈希函数。
- 在链表中插入新节点时，插入到链表头部（O(1)）。

4. 线程安全（可选）

解决方案：
- 使用 synchronized 关键字实现线程安全。
- 使用 ConcurrentHashMap 的分段锁机制。

6. 示例测试

public class Main {
    public static void main(String[] args) {
        MyHashMap<String, Integer> map = new MyHashMap<>();
        map.put("apple", 1);
        map.put("banana", 2);
        map.put("cherry", 3);

        System.out.println(map.get("banana")); // 输出: 2

        map.remove("banana");
        System.out.println(map.get("banana")); // 输出: null
    }
}