Hashtable是怎么实现的？

`Hashtable` 是 Java 早期提供的哈希表实现（JDK 1.0 就有），底层是**数组 + 链表**的结构，并且是**线程安全**的。 ## 1. 底层结构 * **数组**：存放 Entry（键值对）引用，数组下标由 `hash(key)` 计算得到。 * **链表**：解决哈希冲突（拉链法），同一个槽位的元素用链表连接。 * **线程安全**：所有公有方法基本都用 `synchronized` 修饰。 结构示意： ``` table[] 数组 [0] → Entry(key1, value1) → Entry(key2, value2) … [1] → Entry(key3, value3) ... ``` ## 2. 核心实现原理 ### 2.1 hash 计算 `Hashtable` 会先调用 `key.hashCode()`，然后做一个扰动运算，再对数组长度取模： ```java int index = (hash & 0x7FFFFFFF) % table.length; ``` （注意它会取正数，防止负索引） ### 2.2 put 方法 ```java public synchronized V put(K key, V value) { if (value == null) { throw new NullPointerException(); // value 不能为 null } Entry<?,?> tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; // 遍历链表，看是否已存在 for (Entry<K,V> e = (Entry<K,V>) tab[index] ; e != null ; e = e.next) { if (e.hash == hash && e.key.equals(key)) { V old = e.value; e.value = value; // 覆盖 return old; } } // 新插入 addEntry(hash, key, value, index); return null; } ``` 特点： * 用 `synchronized` 包住整个方法，保证线程安全。 * key 可以为 null（只能有一个），但 value 不能为 null。 * 采用头插法，把新元素插在链表最前面。 ### 2.3 get 方法 ```java public synchronized V get(Object key) { Entry<?,?> tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) { if (e.hash == hash && e.key.equals(key)) { return (V)e.value; } } return null; } ``` 同样是同步方法，按哈希槽位查找，然后遍历链表比对 key。 ### 2.4 扩容机制 * **触发条件**：当元素个数 > `threshold`（`threshold = capacity * loadFactor`）。 * **方式**：扩容为原容量的 2 倍 + 1，然后重新计算每个元素的槽位（rehash）。 * **特点**：rehash 成本高，且整个过程中会加锁，扩容期间所有访问都会阻塞。 ## 3. 特点与问题 ### 优点 * 线程安全（方法级 `synchronized`）。 * 实现简单，JDK 早期就可用。 ### 缺点 * 并发性能差（整个表锁）。 * 扩容时性能开销大。 * key 允许为 `null`（最多一个），value 不允许为 `null`。 ## 4. 与 HashMap 对比 | 对比项 | Hashtable | HashMap | | -------------- | --------- | ---------------------------- | | 线程安全 | 是（方法级锁） | 否（需外部同步或用 ConcurrentHashMap） | | key 是否可 null | 可一个 null | 可一个 null | | value 是否可 null | 否 | 可多个 null | | 初始容量 | 11 | 16 | | 扩容倍数 | 2n+1 | 2n | | 效率 | 慢 | 快 | | 出现版本 | JDK 1.0 | JDK 1.2 |