对比分析HashMap，HashTable，ConcurrentHashMap，LinkedHashMap，LURLinkedHashMap...

前言：

• 这次写几篇 关于 HashMap，HashTable，ConcurrentHashMap，LinkedHashMap，LURLinkedHashMap 源码分析。
• 如果直接将他们源码，并不好理解，所以这里我会围绕着HashMap，用对比的方式进行介绍。
• 由于不同的jdk版本，都对他们做了不同的优化，我这边的jdk版本
  • jdk1.7.0_79
  • jdk1.8.0_40 -- 因为1.8里面HashMap做了很大的优化

---

一、首先聊聊 HashMap 和 HashTable

1、出生时间：

以下内容来自java.util.HashTable源码注释 @since JDK1.0 以下内容来自java.util.HashMap源码注释 @since 1.2 

可以看出，HashTable比HashMap要早一点出来（老一些）。

2、作者：

以下内容来自java.util.HashTable源码注释 * @author Arthur van Hoff * @author Josh Bloch * @author Neal Gafter 以下内容来自java.util.HashMap源码注释 * @author Doug Lea * @author Josh Bloch * @author Arthur van Hoff * @author Neal Gafter 

可以看到，HashMap比HashTable多一个 Doug Lea 的作者，想知道Doug Lea大神的信息，简介如下：

--------------------来自百度百科 如果IT的历史，是以人为主体串接起来的话，那么肯定少不了Doug Lea。这个鼻梁挂着眼镜，留着德王威廉二世的胡子，脸上永远挂着谦逊腼腆笑容，服务于纽约州立大学Oswego分校计算机科学系的老大爷。 说他是这个世界上对Java影响力最大的个人，一点也不为过。因为两次Java历史上的大变革，他都间接或直接的扮演了举足轻重的角色。2004年所推出的Tiger。Tiger广纳了15项JSRs(Java Specification Requests)的语法及标准，其中一项便是JSR-166。JSR-166是来自于Doug编写的util.concurrent包。 值得一提的是: Doug Lea也是JCP (Java社区项目)中的一员。 Doug是一个无私的人，他深知分享知识和分享苹果是不一样的，苹果会越分越少，而自己的知识并不会因为给了别人就减少了，知识的分享更能激荡出不一样的火花。《Effective JAVA》这本Java经典之作的作者Joshua Bloch便在书中特别感谢Doug Lea是此书中许多构想的共鸣板，感谢Doug Lea大方分享丰富而又宝贵的知识。 

3、常规面试题：

首先，现在面试还在问：【HashMap和HashTable的区别】的情况比较少了，这是比较老的面试题，因为

以下内容来自java.util.HashTable源码注释 * Java Collections Framework</a>. Unlike the new collection * implementations, {@code Hashtable} is synchronized. If a * thread-safe implementation is not needed, it is recommended to use * {@link HashMap} in place of {@code Hashtable}. If a thread-safe * highly-concurrent implementation is desired, then it is recommended * to use {@link java.util.concurrent.ConcurrentHashMap} in place of * {@code Hashtable}. 

简单翻译就是说，就是 HashTable已经淘汰了 ， 如果不需要线程安全，那么使用HashMap代替HashTable，如果你需要线程那么使用ConcurrentHashMap代替HashTable。

如果现在问到这块，回答的应该要更加全面，比如：
【版本】-->【作者】-->【继承】-->【安全】-->【数据结构】-->【算法】

• HashTable是jdk1.0时期出现的，HashMap是Jdk1.2时期出现的。
• HashMap比HashTable的作者多一个 DougLea大神。
• HashTable和HashMap的类继承关系不一样。(后续阅读源码分析)
• HashTable是线程安全的，HashMap是线程不安全的。（后续源码分析）
• HashTable key和valeu都不支持Null， 而HashMap支持Null（后续分析源码）
• HashTable和HashMap他们的哈希桶内部实现，是一致的。
• HashTable和HashMap在算法上的区别是最大的：（后续源码分析）
  • HashTable初始化大小是11，每次扩容是原来的2n+1，如果用户输入大小，就会直接设定用户输入的大小。
  • HashMap的初始化大小是16，每次扩容是原来的两倍，如果用户输入大小，HashMap会默认将其阔充到2的幂次。
  • HashTable的做法是尽量使用素数、奇数，这样做，简单的取模哈希的结果会更加平均。
  • HashMap的优势，在于取模计算是，如果模数是2的幂，那么我们可以直接使用位运算来得到结果，效率要大大高于做除法。
  • 总结：HashTable取模平均更有优势，HashMap计算效率上更胜一筹。
• HashTable已经淘汰了，源码中的注释写到，如果不考虑线程安全的，可以使用HashMap，如果需要线程安全的，那么使用ConcurrentHashMap可以完美的替代。

这样的回答，已经很漂亮，当然，还可以更好，HashTable安全是如何做到的的，HashMap为什么支持null，HashCode重复了怎么办，这些，往后看。

4、针对上面的答复，进行源码分析：

4.1、HashTable和HashMap的类继承关系不一样

HashMap和HashTable 都是给予哈希来实现键值映射的工具类。下面是他们的继承、实现的关系。

以下内容来自java.util.HashTable源码注释 public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable{} public abstract class Dictionary<K,V> {} 以下内容来自java.util.HashMap源码注释 public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable{} public abstract class AbstractMap<K,V> implements Map<K,V> {} 

从源码中可以看出，他们继承的体系又一些不同，虽然都是实现了Map、Cloneable、Serializable三个接口，但是HashMap继承抽象类 AbstractMap，HashTable继承抽象类Dictionary，这里提一下，Dictionary类是一个已经被废弃的类，这一点在注释中有写：

以下内容来自java.util.Dictionary * <strong>NOTE: This class is obsolete. New implementations should * implement the Map interface, rather than extending this class.</strong> 

细节上还有一点，Dictionary这个类，多一个方法，elements，但是介于 Dictionary已经废弃了，我也就没有在关注他了。

4.2、HashTable是线程安全的，HashMap是线程不安全的。

以下内容来自java.util.HashTable源码 public synchronized V put(K key, V value) { // Make sure the value is not null ......... } public synchronized Enumeration<K> keys() { return this.<K>getEnumeration(KEYS); } 以下内容来自java.util.HashMap源码 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } 

可见，HashTable 线程安全的做法，比较简单，就是所有方法都是带 synchronized 。

4.3、HashTable key和valeu都不支持Null， 而HashMap支持Null

以下内容来自java.util.HashTable源码注释 public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { // 这里会抛错 throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry<?,?> tab[] = table; int hash = key.hashCode();//如果key为null，这里会报NullPointerException ........................ } 以下内容来自java.util.HashMap源码， jdk1.7版本 public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) return putForNullKey(value);//这里做了特殊处理 int hash = hash(key); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value;//Value 直接赋值，不会报错，作为 Null 存入Map e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; } /** * Offloaded version of put for null keys */ private V putForNullKey(V value) { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) {// 把null 作为 一个key 存在 table[0]的位子 V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(0, null, value, 0); return null; } 

通过源码可以看出：

• HashTable valuse 为null ，直接抛 NullPointerException，如果key为null，那么后面那句，key.hashCode();会报NullPointerException。
• HashMap 当key等于kull ，单独包装了一个方法，会调用putForNullKey方法，会把null作为key，放到Entry的table[0]的位置上。
• 通过这个源码，还可以看出一点，如果value 为null ，并不会把key清除，而是把null存入进去。初级程序员，会有这样一个误区，以为put（key,null) 进去，就是把这条是数据清掉了，其实并没有。

 Map map = new HashMap(); System.out.println(map.size()); System.out.println(map.put("a","a")); System.out.println(map.size()); System.out.println(map.put("a",null)); System.out.println(map.size()); System.out.println(map.put("a","a")); System.out.println(map.size()); 输出结果： 0 null 1 //size 是1 a 1//size 还是1 null 1//size 还是1 

从测试代码可以看出，size，一直是1，map的大小并没有发生改变。

在就是到了Jdk1.8，HashMap的变化还是有非常大的，如下：

以下内容来自java.util.HashMap源码 JDK1.8 /** * Returns the value to which the specified key is mapped, * or {@code null} if this map contains no mapping for the key. * * <p>More formally, if this map contains a mapping from a key * {@code k} to a value {@code v} such that {@code (key==null ? k==null : * key.equals(k))}, then this method returns {@code v}; otherwise * it returns {@code null}. (There can be at most one such mapping.) * * <p>A return value of {@code null} does not <i>necessarily</i> * indicate that the map contains no mapping for the key; it's also * possible that the map explicitly maps the key to {@code null}. * The {@link #containsKey containsKey} operation may be used to * distinguish these two cases. * * @see #put(Object, Object) */ public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } /** * Implements Map.get and related methods * * @param hash hash for key * @param key the key * @return the node, or null if none */ final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; } /** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt>. * (A <tt>null</tt> return can also indicate that the map * previously associated <tt>null</tt> with <tt>key</tt>.) */ public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } /** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } 

一眼看去，代码复杂很多，简单的说，JDK1.8对HashMap进行了较大的优化，底层实现由之前的“数组+链表”改为“数组+链表+红黑树”。我这里不详细展开，有兴趣的，可以看一下：https://blog.csdn.net/v123411739/article/details/78996181

4.4、HashTable和HashMap他们的哈希桶内部实现，是一致的。

以下内容来自java.util.HashTable源码注释 /** * The hash table data. */ private transient Entry<K,V>[] table; // 这个对象 /** * Constructs a new, empty hashtable with the specified initial * capacity and the specified load factor. * * @param initialCapacity the initial capacity of the hashtable. * @param loadFactor the load factor of the hashtable. * @exception IllegalArgumentException if the initial capacity is less * than zero, or if the load factor is nonpositive. */ 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 = new Entry[initialCapacity]; threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1); initHashSeedAsNeeded(initialCapacity); } 以下内容来自java.util.HashMap源码注释 /** * An empty table instance to share when the table is not inflated. */ static final Entry<?,?>[] EMPTY_TABLE = {}; /** * The table, resized as necessary. Length MUST Always be a power of two. */ transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;// 这个对象 

HashMap和HashTable都是用哈希表来存储键值对，在数据结构上基本相同的，从源码中可以看到，都是建立了一个 【transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;】，Map.Entry是一个私有内部类，每一个Entry对象表示存储在Hash表中的一个键值对。

private static class Entry<K,V> implements Map.Entry<K,V> { int hash;//hash键对象的hash值 final K key;//key对象 V value;//值对象 Entry<K,V> next;//指链表中下一个Entry对象，可为null，表示当前Entry对象在链表尾部。 

可以说，有多少个键值对，就有多少个Entry对象，那么在HashMap和HashTable中是怎么存储这些Entry对象，以方便我们快速查找和修改的呢？请看下图。

---

上图画出的是一个桶数量为8，存有4个键值对的HashMap/HashTable的内存布局情况。可以看到HashMap/HashTable内部创建有一个Entry类型的引用数组，用来表示哈希表，数组的长度，即是哈希桶的数量。而数组的每一个元素都是一个Entry引用，从Entry对象的属性里，也可以看出其是链表的节点，每一个Entry对象内部又含有另一个Entry对象的引用。

哈希碰撞就是上图 【2】的位子，两个 Entry的hash值计算出来，在同一个位子上。

这样就可以得出结论，HashMap/HashTable内部用Entry数组实现哈希表，而对于映射到同一个哈希桶（数组的同一个位置）的键值对，使用Entry链表来存储(解决hash冲突)。

这里照顾一下新人：java 的transient关键字为我们提供了便利，你只需要实现Serilizable接口，将不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会序列化到指定的目的地中。

4.5、接下来就是他们最大的区别了 ， 初始化，算法

以下内容来自java.util.HashTable源码注释 /** * Constructs a new, empty hashtable with a default initial capacity (11) * and load factor (0.75). */ //初始化 11 public Hashtable() { this(11, 0.75f); } /** * 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. */ protected void rehash() { int oldCapacity = table.length; Entry<K,V>[] oldMap = table; // overflow-conscious code 乘2+1 int newCapacity = (oldCapacity << 1) + 1; 。。。。。。。。。。。。。。 } 以下内容来自java.util.HashMap源码注释 /** * The default initial capacity - MUST be a power of two. */ //初始化1 左移4次， 2的四次方，16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * Adds a new entry with the specified key, value and hash code to * the specified bucket. It is the responsibility of this * method to resize the table if appropriate. * * Subclass overrides this to alter the behavior of put method. */ void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length);//每次扩容，乘2 hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); } 

• HashTable初始化大小是11，每次扩容是原来的2n+1，如果用户输入大小，就会直接设定用户输入的大小。

• HashMap的初始化大小是16，每次扩容是原来的两倍，如果用户输入大小，HashMap会默认将其阔充到2的幂次。

• HashTable的做法是尽量使用素数、奇数，这样做，简单的取模哈希的结果会更加平均。

• HashMap的优势，在于取模计算是，如果模数是2的幂，那么我们可以直接使用位运算来得到结果，效率要大大高于做除法。

 以下内容来自java.util.HashTable源码注释 /** * A randomizing value associated with this instance that is applied to * hash code of keys to make hash collisions harder to find. */ transient int hashSeed; private int hash(Object k) { // hashSeed will be zero if alternative hashing is disabled. return hashSeed ^ k.hashCode(); } 以下内容来自java.util.HashMap源码注释 int hash = hash(key); int i = indexFor(hash, table.length); // 在计算了key.hashCode()之后，做了一些位运算来减少哈希冲突 final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } /** * Returns index for hash code h. */ static int indexFor(int h, int length) { // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; return h & (length-1); } 

正如我们所言，HashMap由于使用了2的幂次方，所以在取模运算时不需要做除法，只需要位的与运算就可以了。但是由于引入的hash冲突加剧问题，HashMap在调用了对象的hashCode方法之后，又做了一些位运算在打散数据。关于这些位计算为什么可以打散数据的问题，本文不再展开了。

如果你有细心读代码，还可以发现一点，就是HashMap和HashTable在计算hash时都用到了一个叫hashSeed的变量。这是因为映射到同一个hash桶内的Entry对象，是以链表的形式存在的，而链表的查询效率比较低，所以HashMap/HashTable的效率对哈希冲突非常敏感，所以可以额外开启一个可选hash（hashSeed），从而减少哈希冲突。因为这是两个类相同的一点，所以本文不再展开了，感兴趣的看这里。事实上，这个优化在JDK 1.8中已经去掉了，因为JDK 1.8中，映射到同一个哈希桶（数组位置）的Entry对象，使用了红黑树来存储，从而大大加速了其查找效率。