Hashtable 是 Java 中一个经典的、线程安全的键值对存储数据结构，它是 Java 集合框架的一部分，存在于 java.util 包中。

Hashtable 的核心特性

在开始实现之前，我们先回顾一下 Hashtable 的几个关键特性：

1. 线程安全：Hashtable 的几乎所有公共方法（如 get, put, remove）都使用了 synchronized 关键字，这意味着在任何时刻只有一个线程可以操作 Hashtable，这使得它在多线程环境下是安全的,但也带来了性能开销。
2. 不允许 null 键和 null 值：与后来的 HashMap 不同，Hashtable 严格禁止 null 作为键或值，如果尝试存入 null，会抛出 NullPointerException。
3. 基于哈希表：它内部使用一个数组（称为“桶”或“bucket”）来存储数据，通过键的 hashCode() 计算出一个索引,然后将键值对存放到对应的数组位置。
4. 使用链地址法处理哈希冲突：当不同的键计算出相同的哈希值（即哈希冲突）时，Hashtable 会在该索引位置创建一个链表（在 Java 8 中，当链表长度超过一定阈值时，会转换为红黑树以提高效率），将所有冲突的键值对都存储在这个链表/树中。
5. 迭代器是快速失败的：如果在迭代 Hashtable 的过程中，有其他线程修改了 Hashtable 的结构（不是通过迭代器自身的 remove 方法），迭代器会立即抛出 ConcurrentModificationException。

手动实现一个简化版 Hashtable

为了更好地理解其工作原理，我们将手动实现一个简化版的 Hashtable，这个版本将包含核心功能，但会省略一些高级特性（如红黑树转换、更复杂的扩容逻辑）来保持代码清晰。

1 数据结构定义

我们将创建一个 MyHashtable 类，它内部维护一个 Entry 对象的数组。Entry 是一个静态内部类，用于存储键、值以及指向下一个 Entry 的引用（用于处理哈希冲突的链表）。

import java.util.Arrays;
import java.util.Objects;
// 手动实现的简化版 Hashtable
public class MyHashtable<K, V> {
    // 默认初始容量，必须是2的幂次方
    private static final int DEFAULT_INITIAL_CAPACITY = 16;
    // 默认负载因子
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 存储数据的Entry数组
    private Entry<K, V>[] table;
    // Hashtable中实际存储的键值对数量
    private int size;
    // 负载因子，用于决定何时扩容
    private final float loadFactor;
    // 当 size >= threshold 时，进行扩容
    private int threshold;
    // Entry内部类，用于存储键值对，并构成链表
    private static class Entry<K, V> {
        final K key;
        V value;
        Entry<K, V> next; // 指向下一个Entry，用于解决哈希冲突
        Entry(K key, V value, Entry<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
    // 构造函数
    public MyHashtable() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
    public MyHashtable(int initialCapacity, float loadFactor) {
        if (initialCapacity <= 0) {
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        }
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
        }
        // 确保容量是2的幂次方
        int capacity = 1;
        while (capacity < initialCapacity) {
            capacity <<= 1;
        }
        this.loadFactor = loadFactor;
        this.table = new Entry[capacity];
        this.threshold = (int)(capacity * loadFactor);
    }
    // ... 省略其他方法 ...
}

2 put 方法的实现

put 方法是 Hashtable 的核心,它负责添加或更新键值对。

/**
 * 向Hashtable中添加或更新一个键值对
 * @param key   键
 * @param value 值
 * @return      如果键已存在，则返回旧值；如果键不存在，则返回null
 */
public synchronized V put(K key, V value) {
    // 1. 检查key是否为null
    Objects.requireNonNull(key, "MyHashtable does not allow null keys");
    // 2. 计算key的哈希码，并找到对应的桶索引
    int hash = hash(key.hashCode());
    int index = indexFor(hash, table.length);
    // 3. 遍历该索引位置的链表，检查key是否已存在
    for (Entry<K, V> e = table[index]; e != null; e = e.next) {
        // 如果key已存在，则更新value并返回旧值
        if (e.key.equals(key)) {
            V oldValue = e.value;
            e.value = value;
            return oldValue;
        }
    }
    // 4. 如果key不存在，则创建一个新的Entry并添加到链表头部
    // (addEntry方法会处理扩容逻辑)
    addEntry(hash, key, value, index);
    return null;
}
/**
 * 辅助方法：根据哈希码和数组长度计算桶的索引
 */
private int indexFor(int hash, int length) {
    return hash & (length - 1);
}
/**
 * 辅助方法：重新计算哈希值，防止低质量的哈希码影响性能
 */
private int hash(int h) {
    // 这是一个简单的优化，目的是让哈希码的二进制位更分散
    h += (h << 15) ^ 0xffffcd7d;
    h ^= (h >>> 10);
    h += (h << 3);
    h ^= (h >>> 6);
    h += (h << 2) + (h << 14);
    return h ^ (h >>> 16);
}
/**
 * 辅助方法：添加Entry，并在需要时进行扩容
 */
private void addEntry(int hash, K key, V value, int bucketIndex) {
    // 1. 检查是否需要扩容
    if (size >= threshold) {
        resize(2 * table.length);
        // 扩容后，key可能被重新哈希到新的位置，需要重新计算索引
        bucketIndex = indexFor(hash, table.length);
    }
    // 2. 将新Entry添加到链表头部（头插法）
    Entry<K, V> oldEntry = table[bucketIndex];
    table[bucketIndex] = new Entry<>(key, value, oldEntry);
    size++;
}
/**
 * 辅助方法：扩容
 */
private void resize(int newCapacity) {
    Entry<K, V>[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == Integer.MAX_VALUE) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry<K, V>[] newTable = new Entry[newCapacity];
    // 迁移所有Entry到新数组
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}
/**
 * 辅助方法：将旧表中的数据迁移到新表
 */
private void transfer(Entry<K, V>[] newTable) {
    Entry<K, V>[] src = table;
    int newCapacity = newTable.length;
    for (Entry<K, V> e : src) {
        while (e != null) {
            Entry<K, V> next = e.next;
            int index = indexFor(hash(e.key.hashCode()), newCapacity);
            e.next = newTable[index];
            newTable[index] = e;
            e = next;
        }
    }
}

3 get 方法的实现

get 方法根据键来查找对应的值。

/**
 * 根据键获取值
 * @param key 键
 * @return    对应的值，如果键不存在则返回null
 */
public synchronized V get(Object key) {
    // 1. 检查key是否为null
    Objects.requireNonNull(key, "MyHashtable does not allow null keys");
    // 2. 计算哈希和索引
    int hash = hash(key.hashCode());
    int index = indexFor(hash, table.length);
    // 3. 遍历链表查找key
    for (Entry<K, V> e = table[index]; e != null; e = e.next) {
        if (e.key.equals(key)) {
            return e.value; // 找到，返回value
        }
    }
    return null; // 未找到，返回null
}

4 remove 方法的实现

remove 方法根据键来移除键值对。

/**
 * 根据键移除键值对
 * @param key 键
 * @return    被移除的值，如果键不存在则返回null
 */
public synchronized V remove(Object key) {
    // 1. 检查key是否为null
    Objects.requireNonNull(key, "MyHashtable does not allow null keys");
    // 2. 计算哈希和索引
    int hash = hash(key.hashCode());
    int index = indexFor(hash, table.length);
    // 3. 遍历链表查找并移除Entry
    Entry<K, V> prev = table[index];
    Entry<K, V> e = prev;
    while (e != null) {
        Entry<K, V> next = e.next;
        if (e.key.equals(key)) {
            // 找到了，执行移除操作
            size--;
            if (prev == e) {
                // 如果要删除的是链表头节点
                table[index] = next;
            } else {
                // 如果要删除的是中间或尾部节点
                prev.next = next;
            }
            return e.value;
        }
        prev = e;
        e = next;
    }
    return null; // 未找到
}

5 其他辅助方法

public synchronized int size() {
    return size;
}
public synchronized boolean isEmpty() {
    return size == 0;
}
@Override
public synchronized String toString() {
    if (size == 0) {
        return "{}";
    }
    StringBuilder sb = new StringBuilder(size * 2 + 2);
    sb.append('{');
    for (Entry<K, V> e : table) {
        for (; e != null; e = e.next) {
            sb.append(e.key).append('=').append(e.value).append(", ");
        }
    }
    // 移除最后的 ", "
    sb.setLength(sb.length() - 2);
    sb.append('}');
    return sb.toString();
}

完整代码与测试

将以上所有部分组合起来，我们可以得到一个完整的简化版 MyHashtable,并进行测试。

import java.util.Objects;
// ... (将上面的所有代码块合并到这里) ...
class MyHashtableTest {
    public static void main(String[] args) {
        MyHashtable<String, Integer> table = new MyHashtable<>();
        // 测试 put
        table.put("one", 1);
        table.put("two", 2);
        table.put("three", 3);
        table.put("four", 4);
        table.put("five", 5);
        System.out.println("Hashtable after puts: " + table);
        System.out.println("Size: " + table.size()); // 期望: 5
        // 测试 get
        System.out.println("Value for key 'two': " + table.get("two")); // 期望: 2
        System.out.println("Value for key 'nonexistent': " + table.get("nonexistent")); // 期望: null
        // 测试 put (更新已存在的key)
        System.out.println("Updating key 'three' from 3 to 33");
        Integer oldValue = table.put("three", 33);
        System.out.println("Old value: " + oldValue); // 期望: 3
        System.out.println("Hashtable after update: " + table);
        // 测试 remove
        System.out.println("Removing key 'one'");
        Integer removedValue = table.remove("one");
        System.out.println("Removed value: " + removedValue); // 期望: 1
        System.out.println("Hashtable after remove: " + table);
        System.out.println("Size: " + table.size()); // 期望: 4
        // 测试 null key (期望抛出异常)
        try {
            table.put(null, 0);
        } catch (NullPointerException e) {
            System.out.println("Successfully caught NullPointerException for null key: " + e.getMessage());
        }
    }
}

与 java.util.Hashtable 和 HashMap 的对比

通过手动实现一个简化版的 Hashtable,我们深入理解了其底层的核心原理：

1. 数组 + 链表：这是 Hashtable 的基本存储结构。
2. 哈希函数：将键映射到数组的索引位置。
3. 处理冲突：当多个键映射到同一位置时,使用链表来存储它们。
4. 扩容机制：当元素数量超过阈值（容量 * 负载因子）时，创建一个更大的数组,并重新计算所有元素的索引进行迁移。
5. 线程安全：通过 synchronized 关键字保证方法级别的原子性。

这个实现虽然简化了 Hashtable 的一些高级特性（如红黑树），但足以让我们掌握其工作的精髓，理解了 Hashtable，再去学习 HashMap 就会非常容易，因为它们的核心数据结构和算法几乎相同，主要区别在于线程安全和 null 值的处理。