对于HashMap源码剖析，可以参考：JDK集合源码之HashMap解析(上) 以及JDK集合源码之HashMap解析(下) ，HashMap底层红黑树实现(自己实现一个简单的红黑树)
1. 二者继的承体系有区别
HashTable
HashMap
从图中可以对比得出，二者都是源于Map口接口，都实现Cloneable和Serializable接口，二者都可以克隆和序列化。但HashMap的父类是AbstractMap，HashTable父类是Dictionary。
Dictionary 类是一个已经被废弃的类（见其源码中的注释）。父类被废弃，自然其子类Hashtable也用的比较少了。
2. HashTable比HashMap多提供了elments() 和contains() 两个方法
elments()方法继承自父类Dictionnary。elements() 方法用于返回此Hashtable中的value的枚举。
contains()方法判断该Hashtable中是否包含传入的value。它的作用与containsValue()一致。事实上，contansValue()就只是调用了一下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); }
3. 二者对Null key 和Null value的支持不同
Hashtable中的Key 和 Value 均不可以为NULL，我们可以从其put()方法中得出：
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<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; }
HashMap中，NULL可以作为键，且这样的键只能存在一个。可以有一个或多个键所对应的值为NULL。当get()方法返回NULL值时，可能是 HashMap中没有该键，也可能使该键所对应的值为NULL。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键， 而应该用containsKey()方法来判断。
4. HashMap线程不安全，HashTable线程安全
Hashtable是线程安全的，它的每个方法中都加入了synchronize关键字。在多线程并发的环境下，可以直接使用Hashtable，不需要自己为它的方法实现同步
HashMap是线程不安全的，在多线程并发的环境下，可能会产生死锁等问题。使用HashMap时就必须要自己增加同步处。
虽然HashMap不是线程安全的，但是它的效率会比Hashtable要好很多。这样设计是合理的。在我们的日常使用当中，大部分时间是单线程操作的。HashMap把这部分操作解放出来了。当需要多线程操作的时候可以使用线程安全的ConcurrentHashMap。ConcurrentHashMap虽然也是线程安全的，但是它的效率比Hashtable要高好多倍。因为ConcurrentHashMap使用了分段锁，并不对整个数据进行锁定。
5. 二者初始容量大小和每次扩充容量大小的不同
Hashtable默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。
HashMap默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。
创建时，如果给定了容量初始值，那么Hashtable会直接使用你给定的大小，而HashMap会将其扩充为2的幂次方大小。也就是说Hashtable会尽量使用素数、奇数。而HashMap则总是使用2的幂作为哈希表的大小。
之所以会有这样的不同，是因为Hashtable和HashMap设计时的侧重点不同。Hashtable的侧重点是哈希的结果更加均匀，使得哈希冲突减少。当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀。而HashMap则更加关注hash的计算效率问题。在取模计算时，如果模数是2的幂，那么我们可以直接使用位运算来得到结果，效率要大大高于做除法。HashMap为了加快hash的速度，将哈希表的大小固定为了2的幂。当然这引入了哈希分布不均匀的问题，所以HashMap为解决这问题，又对hash算法做了一些改动。这从而导致了Hashtable和HashMap的计算hash值的方法不同。
6. 二者计算hash值的方法不同
为了得到元素的位置，首先需要根据元素的KEY计算出一个hash值，然后再用这个hash值来计算得到最终的位置。
Hashtable直接使用对象的hashCode。hashCode是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值。然后再使用除留余数法来获得最终的位置。
Hashtable在计算元素的位置时需要进行一次除法运算，而除法运算是比较耗时的。
HashMap为了提高计算效率，将哈希表的大小固定为了2的幂，这样在取模预算时，不需要做除法，只需要做位运算。位运算比除法的效率要高很多。
HashMap的效率虽然提高了，但是hash冲突却也增加了。因为它得出的hash值的低位相同的概率比较高。
为了解决这个问题，HashMap重新根据hashcode计算hash值后，又对hash值做了一些运算来打散数据。使得取得的位置更加分散，从而减少了hash冲突。当然了，为了高效，HashMap只做了一些简单的位处理。从而不至于把使用2的幂次方带来的效率提升给抵消掉。
HashTable源码
HashTable的属性
// Entry[]数组类型，Entry代表了“拉链”的节点，每一个Entry代表了一个键值对，哈希表的"key-value键值对"都是存储在Entry数组中的 private transient Entry<?,?>[] table; // HashTable的大小，注意: 这个大小并不是HashTable的容器大小，而是他所包含Entry键值对的数量 private transient int count; // Hashtable的阈值，用于判断是否需要调整HashTable的容量。threshold的值=“容量*加载因子” private int threshold; // 加载因子 private float loadFactor; // 用来实现“fail-fast”机制的（也就是快速失败）。所谓快速失败就是在并发集合中，其进行迭代操作时，若有其他线程对其进行结构性的修改，这时迭代器会立马感知到，并且立即抛出ConcurrentModificationException异常，而不是等到迭代完成之后才告诉你（你已经出错了） private transient int modCount = 0;
HashTable构造函数
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 (initialCapacity==0) initialCapacity = 1; this.loadFactor = loadFactor; // 初始化table，获得大小为initialCapacity的table数组 table = new Entry<?,?>[initialCapacity]; // 计算阀值 ---> threshold的值=“容量*加载因子” threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1); } public Hashtable(int initialCapacity) { this(initialCapacity, 0.75f); } // 空参构造方法，初始容量为11 public Hashtable() { this(11, 0.75f); } // 根据传入的Map集合直接初始化HashTable,容量为传入Map集合容量大小*2与11进行比较，取值较大者 public Hashtable(Map<? extends K, ? extends V> t) { this(Math.max(2*t.size(), 11), 0.75f); putAll(t); } private int hash(Object k) { return hashSeed ^ k.hashCode(); }
HashTable几个常用成员方法
1. put方法
// 获取synchronized锁 public synchronized V put(K key, V value) { // 如果value是空抛出异常 if (value == null) { throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry<?,?> tab[] = table; // 计算key的哈希值和index int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; @SuppressWarnings("unchecked") Entry<K,V> entry = (Entry<K,V>)tab[index]; // 遍历对应index位置的链表 for(; entry != null ; entry = entry.next) { // 如果key 已经存在，则更新数据 if ((entry.hash == hash) && entry.key.equals(key)) { V old = entry.value; entry.value = value; return old; } } // 增加新Entry元素 addEntry(hash, key, value, index); return null; }
步骤
1.获取synchronized锁。
2.put方法不允许null值，如果发现是null，则直接抛出异常。
3.计算key的哈希值和index
4.遍历对应位置的链表，如果发现已经存在相同的hash和key，则更新value，并返回旧值。
5.如果不存在相同的key的Entry节点，则调用addEntry方法增加节点。
2. addEntry方法
private void addEntry(int hash, K key, V value, int index) { // 修改次数++ modCount++; Entry<?,?> tab[] = table; // 当前容量超过阈值,需要扩容 if (count >= threshold) { // Rehash the table if the threshold is exceeded // 重新构建桶数组（相当于扩容方法），并对数组中所有键值对重哈希，耗时 rehash(); tab = table; // 根据key，获取hash值 hash = key.hashCode(); // 取摸运算（相当于HashMap定位桶的槽位） // int index = (hash & 0x7FFFFFFF) % tab.length; ？？？ // （前31一个1代表数值，在计算机中整型最高位（32位）是符号位 0代表正数，1代表负数） // 0x7FFFFFFF: 16进制表示的整型,是整型里面的最大值 // 0x7FFFFFFF: 0111 1111 1111 1111 1111 1111 1111 1111：除符号位外的所有1 // (hash & 0x7FFFFFFF) 将产生正整数 // (hash & 0x7FFFFFFF) % tab.length 将在标签长度的范围内 // 所有hashtable采用奇数导致的hash冲突会比较少，采用偶数会导致的冲突会增多 // h & (length-1); hashmap采用相与的方法，所有采用2的幂次方的长度会导致的冲突比较少 index = (hash & 0x7FFFFFFF) % tab.length; } // Creates the new entry. @SuppressWarnings("unchecked") // 获取index槽位的桶中的Entry链表,头节点是e Entry<K,V> e = (Entry<K,V>) tab[index]; // 生成一个新结点, 将新结点插到链表首部，其下一个结点是e tab[index] = new Entry<>(hash, key, value, e); // 有效元素数量++ count++; }
步骤
- 当前容量超过阈值,需要扩容
- 生成一个新结点, 将新结点插到链表首部
3. rehash方法(扩容方法)
相当于hashmap中的resize()方法
protected void rehash() { // 获取当前table数组的容量（数组长度） int oldCapacity = table.length; // oldMap: 当前table数组 Entry<?,?>[] oldMap = table; // 扩容扩为原来的两倍+1 ---> 即：扩容为原来的 2n + 1 这样可以确保容量是奇数 // 奇数有利于index = (hash & 0x7FFFFFFF) % tab.length 求桶位的时候减少hash冲突 // 这种方式类似于HashMap： hash & (tab.length-1),确保容量为2的幂次方，可以减少hash冲突 int newCapacity = (oldCapacity << 1) + 1; // 判断是否超过最大容量 if (newCapacity - MAX_ARRAY_SIZE > 0) { if (oldCapacity == MAX_ARRAY_SIZE) // Keep running with MAX_ARRAY_SIZE buckets return; newCapacity = MAX_ARRAY_SIZE; } // newMap：新table数组 Entry<?,?>[] newMap = new Entry<?,?>[newCapacity]; // HashTable结构修改次数++ modCount++; // 计算下一次rehash的阈值 threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); table = newMap; // 把旧哈希表的键值对重新哈希到新哈希表中去（双重循环，耗时！） // 这个方法类似于HashMap扩容后，将旧数组数据赋给新数组， // 在HashMap中会将其旧数组每个桶位进一步‘打散'，放置到新数组对应的桶位上（有一个重新计算桶位的过程） 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; // 根据新table数组容量newCapacity重新计算桶位 int index = (e.hash & 0x7FFFFFFF) % newCapacity; e.next = (Entry<K,V>)newMap[index]; // 链表放入该桶中 newMap[index] = e; } } }
步骤
- 数组长度增加一倍（如果超过上限，则设置成上限值）。
- 更新哈希表的扩容门限值。
- 遍历旧表中的节点，计算在新表中的index，插入到对应位置链表的头部。
4. get方法
public synchronized V get(Object key) {// 根据键取出对应索引 Entry tab[] = table; int hash = hash(key);// 先根据key计算hash值 int index = (hash & 0x7FFFFFFF) % tab.length;// 再根据hash值找到索引 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {// 遍历entry链 if ((e.hash == hash) && e.key.equals(key)) {// 若找到该键 return e.value;// 返回对应的值 } } return null;// 否则返回null }
骤
- 先获取synchronized锁。
- 计算key的哈希值和index。
- 在对应位置的链表中寻找具有相同hash和key的节点，返回节点的value。
- 如果遍历结束都没有找到节点，则返回
null。
5. remove方法
public synchronized V remove(Object key) { Entry<?,?> tab[] = table; // 计算key的哈希值和index int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; @SuppressWarnings("unchecked") Entry<K,V> e = (Entry<K,V>)tab[index]; for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) { // 遍历对应位置的链表，寻找待删除节点 if ((e.hash == hash) && e.key.equals(key)) { modCount++; // 更新前驱节点的next，指向e的next if (prev != null) { prev.next = e.next; } else { tab[index] = e.next; } count--; V oldValue = e.value; e.value = null; // 返回待删除节点的value值 return oldValue; } } // 如果不存在，返回null return null; }
步骤
- 先获取synchronized锁。
- 计算key的哈希值和index。
- 遍历对应位置的链表，寻找待删除节点，如果存在，用e表示待删除节点，pre表示前驱节点。如果不存在，返回
null。 - 更新前驱节点的next，指向e的next。返回待删除节点的value值。
