Java——HashMap和HashTable的区别

Java HashMap和HashTable的区别

1. 继承的父类

都实现了Map、Cloneable（可复制）、Serializable（可序列化）接口。

HashMap: 继承自AbstractMap类。

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {}

HashTable: 继承自Dictionary类。

public class Hashtable<K,V>extends Dictionary<K,V>implements Map<K,V>, Cloneable, java.io.Serializable {}

2. 线程安全性

HashMap: 线程不安全，效率高。在多线程并发的环境下，可能会产生死循环，数据覆盖等问题。

参考：
https://www.jianshu.com/p/e2f75c8cce01
https://www.cnblogs.com/developer_chan/p/10450908.html

HashTable: 线程安全，效率低。

3. null值问题

HashMap: 允许null值作为key或value。只有一个key可以为null，可以多个null为value.

Map<Integer, Integer> map = new HashMap<>();
map.put(null, 12);
System.out.println(map.get(null));  // 12
map.put(1, null);
map.put(2, null);
System.out.println(map.get(1));  // null
System.out.println(map.get(2));  // null

HashTable: 不允许null值作为key或value

Hashtable<Integer, Integer> hashtable = new Hashtable<>();
hashtable.put(null, 12);    // java.lang.NullPointerException
hashtable.put(1, null);     // java.lang.NullPointerException

4. 初始容量及扩容方式

HashMap: hash数组默认大小为16，扩容方式：16 * 2

/*** The default initial capacity - MUST be a power of two.*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16/*** Initializes or doubles table size.  If null, allocates in* accord with initial capacity target held in field threshold.* Otherwise, because we are using power-of-two expansion, the* elements from each bin must either stay at same index, or move* with a power of two offset in the new table.** @return the table*/
final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)// 将阈值扩大为2倍newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else {               // zero initial threshold signifies using defaults// 当threshold的为0的使用默认的容量，也就是16newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})// 新建一个数组长度为原来2倍的数组Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {oldTab[j] = null;if (e.next == null)newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve order//HashMap在JDK1.8的时候改善了扩容机制，原数组索引i上的链表不需要再反转。// 扩容之后的索引位置只能是i或者i+oldCap（原数组的长度）// 所以我们只需要看hashcode新增的bit为0或者1。// 假如是0扩容之后就在新数组索引i位置，新增为1，就在索引i+oldCap位置Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;// 新增bit为0，扩容之后在新数组的索引不变if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else { //新增bit为1，扩容之后在新数组索引变为i+oldCap（原数组的长度）if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) { loTail.next = null;//数组索引位置不变，插入原索引位置newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;//数组索引位置变化为j + oldCapnewTab[j + oldCap] = hiHead;}}}}}return newTab;
}

HashTable: hash数组默认大小为11，扩容方式：old * 2 + 1

/*** Increases the capacity of and internally reorganizes this* hashtable, in order to accommodate and access its entries more* efficiently.  This method is called automatically when the* number of keys in the hashtable exceeds this hashtable's capacity* and load factor.*/
@SuppressWarnings("unchecked")
protected void rehash() {int oldCapacity = table.length;Entry<?,?>[] oldMap = table;// overflow-conscious code// 扩容为 old * 2 + 1int newCapacity = (oldCapacity << 1) + 1;if (newCapacity - MAX_ARRAY_SIZE > 0) {if (oldCapacity == MAX_ARRAY_SIZE)// Keep running with MAX_ARRAY_SIZE bucketsreturn;newCapacity = MAX_ARRAY_SIZE;}// 新建长度为old * 2 + 1的数组Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];modCount++;threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);table = newMap;for (int i = oldCapacity ; i-- > 0 ;) {for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {Entry<K,V> e = old;old = old.next;int index = (e.hash & 0x7FFFFFFF) % newCapacity;// 使用头插法将链表反序e.next = (Entry<K,V>)newMap[index];newMap[index] = e;}}
}

5. 遍历方式

Hashtable、HashMap都使用了Iterator。而由于历史原因，Hashtable还使用了Enumeration的方式。

HashMap实现 Iterator，支持fast-fail，当有其它线程改变了HashMap的结构（增加，删除，修改元素），将会抛出ConcurrentModificationException。不过，通过Iterator的remove()方法移除元素则不会抛出ConcurrentModificationException异常。Hashtable的Iterator遍历支持fast-fail，用 Enumeration不支持fast-fail。

6. 计算hash值方式

HashMap: 根据元素的key计算出一个hash值，然后再用这个hash值来计算得到最终的位置。

HashMap为了提高计算效率，将哈希表的大小固定为了2的幂，这样在取模预算时，不需要做除法，只需要做位运算。效率虽然提高了，但是hash冲突却也增加了。因为它得出的hash值的低位相同的概率比较高，而计算位运算为了解决这个问题，HashMap重新根据hashcode计算hash值后，又对hash值做了一些运算来打散数据。使得取得的位置更加分散，从而减少了hash冲突。当然了，为了高效，HashMap只做了一些简单的位处理。从而不至于把使用2的幂次方带来的效率提升给抵消掉。例如通过h ^ (h >>> 16)无符号位右移。

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}// 类似的原理 (table.length-1) & hash(key)
public native int hashCode();

HashTable: Hashtable直接使用key对象的hashCode。hashCode是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值。然后再使用除留余数法来获得最终的位置。然而除法运算是非常耗费时间的，效率很低。

public synchronized V put(K key, V value) {// Make sure the value is not nullif (value == null) {throw new NullPointerException();}// Makes sure the key is not already in the hashtable.Entry<?,?> tab[] = table;// 直接使用 key对象的 hashcodeint hash = key.hashCode();// 0x7FFFFFFF转换为10进制之后是Intger.MAX_VALUE,也就是2^31 - 1int index = (hash & 0x7FFFFFFF) % tab.length;@SuppressWarnings("unchecked")Entry<K,V> entry = (Entry<K,V>)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;
}