HashTable源码解析

简介

HashTable 是一个古老的（JDK1.0 时就已存在）线程安全的容器，其核心方法都是 synchronized 修饰的。

相反 HashMap 不是线程安全的。

HashTable与HashMap对比

二者继承体系

HashTable

HashMap

从图中可以对比得出，二者都是源于 Map 接口，都实现了 Cloneable 和 Serializable接口，二者都可以克隆和序列化。

但 HashMap 的父类是 AbstractMap，HashTable父类是 Dictionary。

Dictionary 类是一个已经被废弃的类（见其源码中的注释）。父类被废弃，自然其子类 Hashtable 也用的比较少了。

elments() & contains()

HashTable 比 HashMap 多提供了 elments() 和 contains() 两个方法。

• elments() 方法继承自父类 Dictionnary。

  • elements() 方法用于返回此 Hashtable 中的 value 的枚举。

• contains() 方法判断该 Hashtable 中是否包含传入的 value。

  • 它的作用与 containsValue() 一致。
  • 事实上，containsValue() 就只是调用了一下 contains() 方法。

  // 判断HashTable中是否存在value，存在返回true，否则返回false
  public synchronized boolean contains(Object value) {if (value == null) {throw new NullPointerException();}Entry tab[] = table;for (int i = tab.length ; i-- > 0 ;) {for (Entry e = tab[i] ; e != null ; e = e.next) {if (e.value.equals(value)) {return true;}}}return false;
  }public boolean containsValue(Object value) {return contains(value);
  }
  

key 和 value 是否可以为 null

• HashTable 不允许 key 或者 value 为 null。

      public synchronized V put(K key, V value) {// value不能为null，否则抛出空指针异常if (value == null) {throw new NullPointerException();}// Makes sure the key is not already in the hashtable.Entry tab[] = table;// key不可以为null，因为当key为null时候，null调用hashCode()会报空指针异常int hash = key.hashCode();int index = (hash & 0x7FFFFFFF) % tab.length;@SuppressWarnings("unchecked")Entry entry = (Entry)tab[index];for(; entry != null ; entry = entry.next) {if ((entry.hash == hash) && entry.key.equals(key)) {V old = entry.value;entry.value = value;return old;}}addEntry(hash, key, value, index);return null;}
  

• HashMap 允许存在一个 key 为 null 的 Entry，但是 value 为 null 的 Entry 的个数没有限制。

  	static final int hash(Object key) {int h;// 如果key为null那么哈希值为0return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
  

线程安全

• Hashtable 是 线程安全 的，它的每个方法中都加入了 synchronized 关键字。在多线程并发的环境下，可以直接使用 Hashtable，不需要自己为它的方法实现同步。
• HashMap 是 线程不安全 的，在多线程并发的环境下，可能会产生死锁等问题。使用 HashMap 时就必须要自己增加同步处理。

虽然 HashMap 不是线程安全的，但是它的效率会比 Hashtable 要好很多。这样设计是合理的。在我们的日常使用当中，大部分时间是单线程操作的。HashMap 把这部分操作解放出来了。当需要多线程操作的时候可以使用线程安全的 ConcurrentHashMap。

ConcurrentHashMap 也是线程安全的，它的效率比 Hashtable 要高好多倍。因为 ConcurrentHashMap 使用了分段锁，并不对整个数据进行锁定。

初始容量和扩容大小

• Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+12n+12n+1。
• HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 222 倍。

创建时，如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小。也就是说 Hashtable 会尽量使用素数、奇数。而 HashMap 则总是使用 2 的幂作为哈希表的大小。

之所以会有这样的不同，是因为 Hashtable 和 HashMap 设计时的侧重点不同。

• Hashtable 的侧重点是哈希的结果更加均匀，使得哈希冲突减少。当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀。
• 而 HashMap 则更加关注 hash 的计算效率问题。在取模计算时，如果模数是 2 的幂，那么我们可以直接使用位运算来得到结果，效率要大大高于做除法。HashMap 为了加快 hash 的速度，将哈希表的大小固定为了 2 的幂。

当然这引入了哈希分布不均匀的问题，所以 HashMap 为解决这问题，又对 hash 算法做了一些改动。这从而导致了 Hashtable 和 HashMap 的计算 hash 值的方法不同。

hash值

为了得到元素的位置，首先需要根据元素的 key 计算出一个 hash值，然后再用这个 hash 值来计算得到最终的位置。

Hashtable 直接使用对象的 hashCode。hashCode 是 JDK 根据对象的地址或者字符串或者数字算出来的 int 类型的数值。然后再使用除留余数法来获得最终的位置。

在计算元素的位置时需要进行一次除法运算，而除法运算是比较耗时的。

HashMap 为了提高计算效率，将哈希表的大小固定为了 2 的幂，这样在取模预算时，不需要做除法，只需要做位运算。位运算比除法的效率要高很多。

HashMap 的效率虽然提高了，但是 hash 冲突却也增加了。因为它得出的 hash 值的低位相同的概率比较高。

为了解决这个问题，HashMap 重新根据 hashcode 计算 hash 值后，又对 hash 值做了一些运算来打散数据。使得取得的位置更加分散，从而减少了 hash 冲突。当然了，为了高效，HashMap 只做了一些简单的位处理。从而不至于把使用 2 的幂次方带来的效率提升给抵消掉。

源码解析

属性

    // 底层的Entry[]数组private transient Entry[] table;// 元素(Entry节点)个数private transient int count;// 扩容阈值 (判断是否需要扩容 threshold = 哈希表长度 * 加载因子)private int threshold;// 加载因子private float loadFactor;/** Java中的一种fail-fast(快速失败)机制，每次添加或删除元素(修改不会)modCount都会+1，* 然后使用迭代器遍历时会先讲modCount的值赋给expectedModCount，然后在遍历的时候会检查两者是否还相同* (不相同说明在遍历期间有其他线程添加或者删除了元素，这时就会抛出ConcurrentModificationException异常)*/private transient int modCount = 0;

内部类Entry

    private static class Entry implements Map.Entry {// key的hash值final int hash;final K key;V value;// 产生hash冲突时要形成链表，next节点Entry next;		protected Entry(int hash, K key, V value, Entry next) {this.hash = hash;this.key =  key;this.value = value;this.next = next;}// ...}

构造方法

双参构造方法

   	/** @param initialCapacity：初始化容量* @param loadFactor：加载因子* 就是根据传入的初始容量构造一个Entry数组，然后计算扩容阈值。*/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);// 传入的初始容量为0，赋值为1if (initialCapacity==0)initialCapacity = 1;this.loadFactor = loadFactor;// 初始化Entry数组赋值给table// 直接根据传入的initialCapacity大小创建tabletable = new Entry[initialCapacity];/** MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;* 阈值 = 数组长度 * 加载因子，这里跟INF - 7取一个min。*/threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);}

其它构造器，调用的还是上面的双参构造方法。

	// 传入初始容量，调用的还是上面的双参构造器，加载因子默认为0.75。public Hashtable(int initialCapacity) {this(initialCapacity, 0.75f);}// 空参构造器，默认的初始容量为11，加载因子为0.75。public Hashtable() {this(11, 0.75f);}// 传入一个Map，默认的初始容量为max(2 * t.size(), 11)，加载因子为0.75。public Hashtable(Map t) {this(Math.max(2*t.size(), 11), 0.75f);putAll(t);}

小总结

• 这里跟 HashMap 的区别就是，HashMap 调用无参构造器时，不会初始化 Entry 数组（懒加载），只会为加载因子赋值为0.75，只有第一次 put 时才会创建 Entry 数组，且默认的数组长度为 16。
• HashTable 调用无参构造器时，就直接创建一个长度为 11 的 Entry 数组。

put(K key, V value)

  	/** 同步方法*/public synchronized V put(K key, V value) {// value不允许为nullif (value == null) {throw new NullPointerException();}Entry tab[] = table;// 获取key的hashCode值int hash = key.hashCode();/** 寻址算法* 0x7FFFFFFF = Integer.MAX_VALUE* (hash & 0x7FFFFFFF)的作用是将hash变为一个正整数* 直接对table.length进行取余，得到的值的范围就在[0, len - 1]。*/int index = (hash & 0x7FFFFFFF) % tab.length;@SuppressWarnings("unchecked")      // 获取index位置的entryEntry entry = (Entry)tab[index];// 遍历桶位，查找当前key是否已经存在于桶位的链表中for(; entry != null ; entry = entry.next) {// hash值相等 并且 key的equals()结果也相等，进行替换if ((entry.hash == hash) && entry.key.equals(key)) {V old = entry.value;// 替换entry.value = value;// 返回旧的valuereturn old;}}// 能走到这里，说明当前桶位中没有key相同的entry，需要将当前entry插入进去。addEntry(hash, key, value, index);// 返回nullreturn null;}||\//** 真正插入节点的方法*/private void addEntry(int hash, K key, V value, int index) {// 添加操作 modCount + 1modCount++;Entry tab[] = table;// count = 当前哈希表中的元素个数，大于扩容阈值，所以需要扩容。if (count >= threshold) {// 扩容操作，下面详细分析。rehash();/** 扩容之后，当前entry寻址后的index会发生变化* 所以重新计算。*/tab = table;hash = key.hashCode();index = (hash & 0x7FFFFFFF) % tab.length;}// 获取当前index桶位的头结点@SuppressWarnings("unchecked")Entry e = (Entry) tab[index]; // 将当前的Entry插入到桶位的头结点，它的next节点是e(原头结点)tab[index] = new Entry<>(hash, key, value, e);count++;}

put() => addEntry() 流程总结

• 前置条件：key 和 value 都不允许为 null；
• 调用 key 的 hashCode 获取 hash 值，对 length 取余寻址，获取桶位索引 index；
• 遍历当前桶位，判断是否存在相同 key 的 entry，存在直接替换 value，然后返回旧的 value；
• 不存在，调用 addEntry()，判断是否需要扩容，需要扩容就去扩容，然后重新寻；
• 获取寻址后的桶位 index，将当前 Entry 直接插入到桶位头节点。

流程图

与 HashMap 的几点区别

• HashTable 中 Entry 的 key 的最终的 hash 值就是其 hashCode()方法的返回值，而 HashMap 中的 Entry 的 key 的最终的 hash 值是 hashCode ^ (hashCode >>> 16)。
• HashTable 的寻址算法为 (hash % tab.length)，而 HashMap 的寻址算法是 (hash & tab.length - 1)。

rehash()

• 扩容方法，相当于 HashMap 中的 resize() 方法。

    @SuppressWarnings("unchecked")protected void rehash() {// 原哈希表长度int oldCapacity = table.length;// oldMap引用原哈希表Entry[] oldMap = table;/** 一般情况：扩容为原oldCapacity * 2 + 1*/ int newCapacity = (oldCapacity << 1) + 1;// 情况很少，一般size不会是INF级别的if (newCapacity - MAX_ARRAY_SIZE > 0) {if (oldCapacity == MAX_ARRAY_SIZE)// Keep running with MAX_ARRAY_SIZE bucketsreturn;newCapacity = MAX_ARRAY_SIZE;}// 根据newCapacity创建一个新Entry数组Entry[] newMap = new Entry[newCapacity];modCount++;// 重新计算扩容阈值threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);// table引用新的Entry数组table = newMap;/** 遍历原哈希表，将所有的entry重新寻址插入到新的哈希表中*/for (int i = oldCapacity ; i-- > 0 ;) {// 遍历每一个桶位for (Entry old = (Entry)oldMap[i] ; old != null ; ) {// e指向当前节点Entry e = old;// old向后走old = old.next;// 重新寻址int index = (e.hash & 0x7FFFFFFF) % newCapacity;// 当前节点指向桶位头结点e.next = (Entry)newMap[index];// 桶位头节点变为当前节点，完成插入操作。newMap[index] = e;}}}

remove(Object key)

    /** 同步方法，删除元素。* 寻址，然后遍历桶位寻找待删除节点，找到后直接删除即可。*/public synchronized V remove(Object key) {Entry tab[] = table;/** 获取hash值然后寻址*/int hash = key.hashCode();int index = (hash & 0x7FFFFFFF) % tab.length;// 获取桶位头结点Entry e = (Entry)tab[index];/** prev指向当前节点的前驱节点 e指向当前节点*/for(Entry prev = null ; e != null ; prev = e, e = e.next) {// 找到了要删除的entryif ((e.hash == hash) && e.key.equals(key)) {modCount++;// prev != null 表示e非头结点if (prev != null) {// 直接将e干掉prev.next = e.next;// e是头结点} else {// 将头结点变为e的nexttab[index] = e.next;}// 元素个数-1count--;// 获取valueV oldValue = e.value;// 将e.value置为null，help GC e.value = null;// 将旧值返回return oldValue;}}// 不存在 返回nullreturn null;}

get(Object key)

	/** 同步方法，获取指定key的value。*/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) {// 查找成功，返回value。if ((e.hash == hash) && e.key.equals(key)) {return (V)e.value;}}// 查找失败，返回null。return null;}

总结

• Hashtable 是线程安全的容器(方法都加了synchronized)，底层只有 (数组 + 链表) ；
• Hashtable 不允许 key 或者 value 为 null；
• Hashtable 存在 fast-fail 机制，modCount 实现；
• hash 值是 key 的 hashCode() 的返回值；
• 寻址算法 hash % table.length；
• 调用无参构造器默认初始容量为11，加载因子为0.75；
• 一般情况下，扩容为 oldCap * 2 + 1。

参考文章

• shstart7_Hashtable源码解析
• 兴趣使然的草帽路飞_JDK集合源码之HashTable解析