HashTable详解

概论

HashTable是遗留类,很多映射的常用功能与HashMap类似,不同的是它承自Dictionary类,并且是线程安全的,并发性不如ConcurrentHashMap,因为ConcurrentHashMap引入了分段锁。

Hashtable不建议在新代码中使用,不需要线程安全的场合可以用HashMap替换,需要线程安全的场合可以用ConcurrentHashMap替换。

对比HashMap 的初始容量

默认11 的初始容量

需要注意的是Hashtable的默认初始容量大小是11,而HashMap 是16,但是他们的加载因子都是0.75f

  1. /**
  2. * Constructs a new, empty hashtable with a default initial capacity (11)
  3. * and load factor (0.75).
  4. */
  5. public Hashtable() {
  6. this(11, 0.75f);
  7. }

Java

  1. /**
  2. * Constructs an empty <tt>HashMap</tt> with the default initial capacity
  3. * (16) and the default load factor (0.75).
  4. */
  5. public HashMap() {
  6. this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
  7. }

Java

任意指定非负的容量

还有一点就是Hashtable的initialCapacity 也就是初始容量是是可以是你指定的任何非负整数,也就是你给它设置个0 也可以的

  1. public Hashtable(int initialCapacity) {
  2. this(initialCapacity, 0.75f);
  3. }
  4. public Hashtable(int initialCapacity, float loadFactor) {
  5. if (initialCapacity < 0)
  6. throw new IllegalArgumentException("Illegal Capacity: "+
  7. initialCapacity);
  8. if (loadFactor <= 0 || Float.isNaN(loadFactor))
  9. throw new IllegalArgumentException("Illegal Load: "+loadFactor);
  10. if (initialCapacity==0)
  11. initialCapacity = 1;
  12. this.loadFactor = loadFactor;
  13. table = new Entry<?,?>[initialCapacity];
  14. threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
  15. }

但是你看一下HashMap 的初始容量就不那么听话了,默认情况下,当我们设置HashMap的初始化容量时,实际上HashMap会采用第一个大于该数值的2的幂作为初始化容量(0 1 除外)

  1. public HashMap(int initialCapacity, float loadFactor) {
  2. if (initialCapacity < 0)
  3. throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
  4. if (initialCapacity > MAXIMUM_CAPACITY)
  5. initialCapacity = MAXIMUM_CAPACITY;
  6. if (loadFactor <= 0 || Float.isNaN(loadFactor))
  7. throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
  8. this.loadFactor = loadFactor;
  9. this.threshold = tableSizeFor(initialCapacity);
  10. }

Java

对比HashMap 的 对null 值的支持

HashTable key value 都不支持null

首先HashMap 是支持null 值做key和value 的,但是HashTable 是不支持的,key 也不支持 value 也不支持

  1. public synchronized V put(K key, V value) {
  2. // Make sure the value is not null
  3. if (value == null) {
  4. throw new NullPointerException();
  5. }
  6. // Makes sure the key is not already in the hashtable.
  7. Entry<?,?> tab[] = table;
  8. int hash = key.hashCode();
  9. int index = (hash & 0x7FFFFFFF) % tab.length;
  10. @SuppressWarnings("unchecked")
  11. Entry<K,V> entry = (Entry<K,V>)tab[index];
  12. for(; entry != null ; entry = entry.next) {
  13. if ((entry.hash == hash) && entry.key.equals(key)) {
  14. V old = entry.value;
  15. entry.value = value;
  16. return old;
  17. }
  18. }
  19. addEntry(hash, key, value, index);
  20. return null;
  21. }

Java

聪明的你们发现了吗,上面值检测了value ==null 则抛出NPE 但是没有说key 啊,因为如果key 是null 的话,key.hashCode()则会抛出异常,根本不需要判断,但是value 就不会抛出来

但是需要注意的实HashMap 对null 值虽然支持,但是可以从hash值的计算方法中看出,<null,value>的键值对,value 会覆盖的。

  1. static final int hash(Object key) {
  2. int h;
  3. return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  4. }

Java

升级HashTable 使其支持null 做value

大部分代码都是直接copy 的HashTable,只去掉了value 的空值检测

  1. public class BuerHashTable<K, V> extends Hashtable<K, V> {
  2. // ..... 省略了部分代码,直接copy HashTable 的即可,主要是BuerHashTable.Entry 的定义和构造方法
  3. public synchronized V put(K key, V value) {
  4. // Makes sure the key is not already in the hashtable.
  5. Entry<?,?> tab[] = table;
  6. int hash = key.hashCode();
  7. int index = (hash & 0x7FFFFFFF) % tab.length;
  8. @SuppressWarnings("unchecked")
  9. Entry<K,V> entry = (Entry<K,V>)tab[index];
  10. for(; entry != null ; entry = entry.next) {
  11. if ((entry.hash == hash) && entry.key.equals(key)) {
  12. V old = entry.value;
  13. entry.value = value;
  14. return old;
  15. }
  16. }
  17. addEntry(hash, key, value, index);
  18. return null;
  19. }
  20. private void addEntry(int hash, K key, V value, int index) {
  21. modCount++;
  22. BuerHashTable.Entry<?,?> tab[] = table;
  23. if (count >= threshold) {
  24. // Rehash the table if the threshold is exceeded
  25. rehash();
  26. tab = table;
  27. hash = key.hashCode();
  28. index = (hash & 0x7FFFFFFF) % tab.length;
  29. }
  30. // Creates the new entry.
  31. @SuppressWarnings("unchecked")
  32. BuerHashTable.Entry<K,V> e = (BuerHashTable.Entry<K,V>) tab[index];
  33. tab[index] = new BuerHashTable.Entry<>(hash, key, value, e);
  34. count++;
  35. }
  36. }

Java

接下来,就可以将null 值作为value 存入BuerHashTable 了

  1. BuerHashTable<String, String> buerHashTable = new BuerHashTable<>();
  2. buerHashTable.put("a", null);

Java

对比 HashTable 的继承关系

Dictionary

这个类是HashTable特有继承的,HashMap 是没有继承的,但是这个抽象类其实是没有多大意义的,因为它的方法都在Map接口中有,其实这个就是个历史问题了,因为Map接口是在Java1.2 中才加进去的,而Dictionary抽象类在Java1.0中就存在了

  1. public abstract
  2. class Dictionary<K,V> {
  3. public Dictionary() {
  4. }
  5. abstract public int size();
  6. abstract public boolean isEmpty();
  7. abstract public Enumeration<K> keys();
  8. abstract public Enumeration<V> elements();
  9. abstract public V get(Object key);
  10. /**
  11. * @exception NullPointerException if the <code>key</code> or
  12. */
  13. abstract public V put(K key, V value);
  14. abstract public V remove(Object key);
  15. }

Java

这个地方的NullPointerException 对应的就是HashTable 中put 方法中的null 值检测

最后一点就是Dictionary 抽象类上的注释,新的实现应该实现Map 接口而不是该抽象类

NOTE: This class is obsolete.  New implementations should implement the Map interface, rather than extending this class

其实HashMap更准确地说是继承自AbstractMap类,而不是直接实现了Map 接口,所以要是Dictionary这个抽象类要是实现的实Map 接口,那HashMap和Hashtable 就在继承关系上保持一致了

Hashtable

线程安全

其实HashTable 没有那么多要说的,比较重要的一点就是线程安全,但是这个线程安全的实现方式就是所有的操作都加了synchronized关键字,哈哈! 关于synchronized 我们后面会说

  1. public synchronized int size() {}
  2. public synchronized boolean isEmpty() {}
  3. public synchronized boolean contains(Object value) {}
  4. public synchronized boolean containsKey(Object key) {}
  5. public synchronized V get(Object key) {}
  6. public synchronized V put(K key, V value) {}
  7. public synchronized V remove(Object key) {}

Java

而HashMap 是线程不安全的

contains方法

HashMap中没有Hashtable中的contains方法,只有containsValue和containsKey,因为contains方法容易让人引起误解。

Hashtable则保留了contains,containsValue和containsKey三个方法,其中contains和containsValue功能相同。

debug 源码 put 方法

  1. public synchronized V put(K key, V value) {
  2. // Make sure the value is not null 确保value 不是null
  3. if (value == null) {
  4. throw new NullPointerException();
  5. }
  6. // Makes sure the key is not already in the hashtable.
  7. // 这里的英文注释很有意思啊,就是告诉你确保key 不存在,存在咋地,覆盖又咋地
  8. Entry<?,?> tab[] = table;
  9. // 哈希值的计算不同,HashTable直接使用对象的hashCode。而HashMap重新计算hash值(高16位异或低16位)
  10. int hash = key.hashCode();
  11. // 计算下标 HashMap 是计算key的hash再与tab.length-1进行与运算;
  12. // HashTable则是key的hash值与0x7FFFFFFF进行与运算,然后再对tab.length取模
  13. // 先hash&0x7FFFFFFF后,再对length取模,与0x7FFFFFFF的目的是为了将负的hash值转化为正值,因为hash值有可能为负数,
    而&0x7FFFFFFF后,只有符号外改变,而后面的位都不变
  14. int index = (hash & 0x7FFFFFFF) % tab.length;
  15. @SuppressWarnings("unchecked")
  16. // 确定 index 位置上的链表头,这里主要是遍历链表找到key 值相等的节点,然后返回old value,这样的话就不用添加新值
  17. // 也就是不用调用addEntry 方法
  18. Entry<K,V> entry = (Entry<K,V>)tab[index];
  19. // 存在key
  20. for(; entry != null ; entry = entry.next) {
  21. if ((entry.hash == hash) && entry.key.equals(key)) {
  22. V old = entry.value;
  23. entry.value = value;
  24. return old;
  25. }
  26. }
  27. // 链表中不存在,则添加新值
  28. addEntry(hash, key, value, index);
  29. // 返回null
  30. return null;
  31. }

Java

  1. private void addEntry(int hash, K key, V value, int index) {
  2. modCount++;
  3. Entry<?,?> tab[] = table;
  4. // 判断是否要扩容
  5. if (count >= threshold) {
  6. // Rehash the table if the threshold is exceeded
  7. rehash();
  8. tab = table;
  9. hash = key.hashCode();
  10. index = (hash & 0x7FFFFFFF) % tab.length;
  11. }
  12. // Creates the new entry.
  13. @SuppressWarnings("unchecked")
  14. Entry<K,V> e = (Entry<K,V>) tab[index];
  15. // e 也就是 tab[index] 是这个链表的头结点, tab[index] = new Entry<>(hash, key, value, e); 也就是将元素添加到链表
    的头部,e 做为new Entry<>(hash,key, value, e)的next 节点
  16. tab[index] = new Entry<>(hash, key, value, e);
  17. count++;
  18. }

Java

这里我们对比一下HashMap 的添加方法,很明显别人都是添加的链表尾部的,因为HashTable 是线程安全的,在这个前提下,使用头查法性能更好,否则还有遍历到链表的尾部插入

  1. for (int binCount = 0; ; ++binCount) {
  2. if ((e = p.next) == null) {
  3. p.next = newNode(hash, key, value, null);
  4. if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  5. treeifyBin(tab, hash);
  6. break;
  7. }
  8. if (e.hash == hash &&
  9. ((k = e.key) == key || (key != null && key.equals(k))))
  10. break;
  11. p = e;
  12. }

Java

最后我们再看一下扩容的方法

  1. @SuppressWarnings("unchecked")
  2. protected void rehash() {
  3. int oldCapacity = table.length;
  4. Entry<?,?>[] oldMap = table;
  5. // overflow-conscious code
  6. // 扩容成2倍+1
  7. int newCapacity = (oldCapacity << 1) + 1;
  8. // 这里判断是否超出了容量限制
  9. if (newCapacity - MAX_ARRAY_SIZE > 0) {
  10. if (oldCapacity == MAX_ARRAY_SIZE)
  11. // Keep running with MAX_ARRAY_SIZE buckets
  12. return;
  13. // 最大容量 MAX_ARRAY_SIZE
  14. newCapacity = MAX_ARRAY_SIZE;
  15. }
  16. // 创建新的数组
  17. Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
  18. modCount++;
  19. // 更新 threshold
  20. threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
  21. table = newMap;
  22. // 数据迁移,遍历数组
  23. for (int i = oldCapacity ; i-- > 0 ;) {
  24. // for 循环的方式遍历链表
  25. for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
  26. Entry<K,V> e = old;
  27. old = old.next;
  28. int index = (e.hash & 0x7FFFFFFF) % newCapacity;
  29. e.next = (Entry<K,V>)newMap[index];
  30. newMap[index] = e;
  31. }
  32. }
  33. }

Java

总结

  1. 需要注意的是Hashtable的默认初始容量大小是11,而HashMap 是16,但是他们的加载因子都是0.75f
  2. HashTable的初始容量可以使任何非负整数,但是HashMap会采用第一个大于该数值的2的幂作为初始化容量(0 1 除外,都是 1)
  3. HashTable的线程安全是完全借助synchronized 的加持
  4. HashTable 的元素是头插法,也就是插入到链表的头部,因为HashTable 是线程安全的,在这个前提下,使用头查法性能更好,否则还有遍历到链表的尾部插入
  5. HashTable 是没有红黑树支持的,就是不论链表的长度有多长,都不会转化成红黑树
  6. 哈希值的计算不同,HashTable直接使用对象的hashCode。而HashMap重新计算hash值(高16位异或低16位),并且HashMap 支持key 为null 就是在这里的
  7. Hashtable扩容时,将容量变为原来的2倍加1,而HashMap扩容时,将容量变为原来的2倍。

你觉得HashTable 还有什么可以改进的地方吗,欢迎讨论

和上一节一样这里我依然给出这个思考题,虽然我们的说法可能不对,可能我们永远也站不到源代码作者当年的高度,但是我们依然积极思考,大胆讨论

虽然java 源代码的山很高,如果你想跨越,至少你得有登山的勇气,这里我给出自己的一点点愚见,希望各位不吝指教

  1. int hash = key.hashCode();
  2. addEntry(hash, key, value, index);
  3. private void addEntry(int hash, K key, V value, int index) {
  4. // 记录修改,快速失败
  5. modCount++;
  6. Entry<?,?> tab[] = table;
  7. // count 实际存储的key-value 数目,在HashMap 中用size 表示
  8. if (count >= threshold) {
  9. // Rehash the table if the threshold is exceeded
  10. rehash();
  11. tab = table;
  12. // 咋地,数组扩容之后key 的hash值会变吗,你还有重新计算一下
  13. hash = key.hashCode();
  14. index = (hash & 0x7FFFFFFF) % tab.length;
  15. }
  16. // Creates the new entry.
  17. @SuppressWarnings("unchecked")
  18. Entry<K,V> e = (Entry<K,V>) tab[index];
  19. tab[index] = new Entry<>(hash, key, value, e);
  20. count++;
  21. }

Java

当然这只是小问题,但是也有很多其他小问题,例如求index 时候的计算方式是直接取模,而不是用与运算,它最大的问题在设计上,例如hash值的计算方式就没有HashMap 设计的好,还有就是没有红黑树的支持,还有就是线程安全的实现方式也不高效,所以我们说它好像是遗留类,HashTable 在Java1.0 时代就存在了,而HashMap才是Java1.2才有的

 

 作者:柯广的网络日志

微信公众号:Java大数据与数据仓库