前言：
- 这次写几篇 关于 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对象，以方便我们快速查找和修改的呢？请看下图。
image_1536219041.924343.jpg
上图画出的是一个桶数量为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对象，使用了红黑树来存储，从而大大加速了其查找效率。
网友评论