Hashtable实现原理

定义与基本原理定义Hashtable 是一个基于哈希表Hash Table实现的 Map 接口它将键Key映射到值Value。它的核心特点是线程安全不允许 null 键或 null 值。核心原理Hashtable 的底层数据结构是 数组 链表即“拉链法”解决哈希冲突。哈希函数通过 Key 的 hashCode() 计算哈希值再通过取模运算%确定元素在数组中的索引位置。冲突解决当两个 Key 的哈希值映射到同一个数组索引时Hashtable 会在该索引位置维护一个链表将新元素追加到链表中。扩容机制当元素数量超过阈值容量 × 负载因子时数组会自动扩容通常是原容量的 2 倍 1并重新分配所有元素的位置Rehash。继承体系HashtableK,V是一种key-value结构它继承自DictionaryK,V实现了MapK,V接口、Cloneable接口及Serializable接口。源码剖析类定义与成员变量// 继承 Dictionary 类这是一个过时的抽象类实现了 Map, Cloneable, Serializable 接口 public class HashtableK,V extends DictionaryK,V implements MapK,V, Cloneable, java.io.Serializable { // 哈希表的核心数组存储 Entry 节点 protected transient Entry?,?[] table; // 元素总数 protected transient int count; // 扩容阈值 protected transient int threshold; // 负载因子 protected transient float loadFactor; // 修改次数用于 Fail-Fast 机制 protected transient int modCount 0; }构造函数1.最核心的构造函数负责实际的初始化工作public Hashtable(int initialCapacity, float loadFactor) { if (initialCapacity 0) throw new IllegalArgumentException(Illegal Capacity: initialCapacity); if (loadFactor 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException(Illegal Load: loadFactor); if (initialCapacity0) initialCapacity 1; this.loadFactor loadFactor; table new Entry?,?[initialCapacity]; threshold (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE 1); }关键点参数校验确保初始容量和负载因子是有效的。初始化数组创建了Entry数组这是Hashtable存储数据的基础。计算阈值threshold是判断Hashtable是否需要扩容的关键指标其值为容量 * 负载因子。2.无参构造函数这是最常用的构造函数。如果不指定任何参数Hashtable会使用默认的初始容量和负载因子。public Hashtable() { this(11, 0.75f); }关键点默认初始容量11。选择11这个质数是为了在使用取余法计算哈希索引时能让数据分布得更均匀减少哈希冲突。默认负载因子0.75f。这是一个在时间和空间成本之间取得平衡的折中值。3.指定初始容量的构造函数当我们预估了Hashtable中大概会存放多少元素时可以使用这个构造函数来避免频繁的扩容操作提升性能。public Hashtable(int initialCapacity) { this(initialCapacity, 0.75f); }关键点它使用我们指定的initialCapacity但负载因子仍采用默认值0.75f。4.根据已有 Map 初始化的构造函数当我们需要用一个已经存在的Map来创建一个新的Hashtable时这个构造函数非常方便。public Hashtable(Map? extends K, ? extends V t) { this(Math.max(2*t.size(), 11), 0.75f); putAll(t); }关键点智能容量它会将新Hashtable的初始容量设置为t.size()的两倍和11之间的较大值。这样做是为了给新集合留出足够的空间避免在调用putAll(t)时立即触发扩容。复制数据初始化后它会调用putAll(t)将传入Map中的所有键值对复制到新的Hashtable中。5.“包级私有”package-private的构造方法这是一个为了解决Properties类Hashtable的子类在初始化时的一个特殊需求的构造方法。Hashtable(Void dummy) {}关键点访问权限它没有public修饰符。这意味着它只能在java.util包内部被访问。参数接收一个Void类型的参数通常传null这只是一个占位符用于区分构造函数签名。逻辑方法体是空的什么都不做。作用这个构造函数的存在完全是为了服务于java.util.Properties类。继承关系Properties类继承自Hashtable。Properties的特殊性Properties类主要用于处理配置文件键值对都是字符串。虽然它继承自Hashtable但在 JDK 的实现中Properties实际上维护了自己的底层存储结构通常是ConcurrentHashMap而不是使用父类Hashtable中的table数组。避免浪费当创建一个Properties对象时如果调用Hashtable的默认构造函数会初始化一个容量为 11 的Entry数组 (table new Entry?,?[11])。但由于Properties根本不使用这个数组这块内存分配就是纯粹的浪费。Properties类在初始化时会显式调用这个特殊的父类构造函数// 在 java.util.Properties 源码中 private Properties(Properties defaults, int initialCapacity) { // 调用 Hashtable 的空构造函数跳过 Hashtable 的数组初始化 super((Void) null); // Properties 使用自己的 ConcurrentHashMap 作为底层存储 map new ConcurrentHashMap(initialCapacity); this.defaults defaults; }核心方法put()这是 Hashtable 最核心的写入操作留心synchronized关键字的使用。public synchronized V put(K key, V value) { // 1. 确保 value 不为 nullHashTable 不允许 null 值 if (value null) { throw new NullPointerException(); } // 2. 计算 key 的哈希值 // 注意这里直接使用 key.hashCode()没有像 HashMap 那样做高位异或扰动 int hash key.hashCode(); // 3. 计算数组索引 // 使用 0x7FFFFFFF 确保哈希值为正数然后对数组长度取模 int index (hash 0x7FFFFFFF) % table.length; // 4. 遍历链表检查 key 是否已存在 for (Entry?,? e (Entry?,?)table[index] ; e ! null ; e e.next) { // 如果 key 相等哈希相同且 equals 为 true则更新旧值 if ((e.hash hash) e.key.equals(key)) { V old (V)e.value; e.value value; return old; } } // 5. 如果 key 不存在执行插入操作头插法 addEntry(hash, key, value, index); return null; }关键点线程安全方法上直接加了synchronized这意味着同一时间只有一个线程能执行put操作这是 Hashtable 线程安全的根本原因也是其性能瓶颈所在。索引计算使用取模运算%这在性能上略低于 HashMap 的位运算。扩容机制rehash()当count threshold时触发。protected void rehash() { int oldCapacity table.length; Entry?,?[] oldMap table; // 1. 新容量 旧容量 * 2 1 // 注意HashMap 是扩容为 2 的幂而 HashTable 是 2n1目的是取质数减少冲突 int newCapacity (oldCapacity 1) 1; Entry?,?[] newMap new Entry?,?[newCapacity]; modCount; // 2. 重新计算阈值 threshold (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE 1); table newMap; // 3. 重新分配元素 for (int i 0 ; i oldCapacity ; i) { for (EntryK,V old (EntryK,V)oldMap[i] ; old ! null ; ) { EntryK,V e old; old old.next; int index (e.hash 0x7FFFFFFF) % newCapacity; e.next (EntryK,V)newMap[index]; newMap[index] e; } } }常用操作Hashtable 的使用非常简单符合标准 Map 的接口规范操作方法说明添加/修改put(K key, V value)插入键值对若 Key 存在则覆盖 Value。获取get(Object key)根据 Key 获取 Value找不到返回 null。删除remove(Object key)删除指定 Key 的映射。大小size()返回集合中键值对的数量。判空isEmpty()判断集合是否为空。遍历entrySet()/keySet()返回集合视图用于迭代遍历。Hashtable 与 HashMap 对比特性HashTableHashMap线程安全是 (全表锁synchronized)否 (多线程下不安全)Null 键/值不允许 (抛出NullPointerException)允许 (1个 null 键多个 null 值)底层结构数组 链表数组 链表 红黑树 (JDK 1.8)初始容量1116扩容规则old * 2 1(趋向质数)old 1(2 的幂次方)哈希计算直接使用hashCode()二次哈希高位异或 位运算迭代器Enumeration(非 Fail-Fast)Iterator(Fail-Fast)性能较低 (锁竞争严重)较高 (无锁单线程最优)详细解析数据结构差异红黑树HashMap在 JDK 1.8 引入了红黑树。当链表长度超过 8 且数组长度超过 64 时链表会转为红黑树查找时间复杂度从 O(n) 降为 O(log⁡n) 。Hashtable始终只有链表如果哈希冲突严重性能会显著下降。扩容与效率HashMap的容量是 2 的幂16, 32, 64...这使得它在计算索引时可以使用位运算(n-1) hash代替取模运算效率更高。Hashtable使用2n1扩容且必须使用取模运算计算开销稍大。Fail-Fast 机制HashMap的迭代器是快速失败的。如果在遍历过程中结构被修改非通过迭代器自身的 remove 方法会立即抛出ConcurrentModificationException。Hashtable的Enumeration不是快速失败的这在并发环境下可能导致不可预知的行为。优缺点总结与替代方案优点线程安全在早期的 Java 版本中它是多线程环境下唯一的选择。简单API 简单无需额外配置即可在多线程中使用。缺点性能低下由于synchronized锁住的是整个 Hashtable 对象在高并发场景下所有线程都在抢一把锁导致吞吐量急剧下降。功能陈旧不支持红黑树优化不支持 null 值扩容机制也不如 HashMap 高效。替代方案单线程环境首选HashMap。它的性能最好功能最全。多线程环境绝对不要使用Hashtable。首选ConcurrentHashMap。在 JDK 1.7 中它使用分段锁Segment锁粒度更细。在 JDK 1.8 中它放弃了 Segment采用CAS synchronized锁住链表/红黑树的头节点并发性能远高于 Hashtable。备选Collections.synchronizedMap(new HashMap())。这虽然也是全表锁但比 Hashtable 稍微灵活一点可以包装任何 Map不过性能依然不如 ConcurrentHashMap。