共计 8520 个字符，预计需要花费 22 分钟才能阅读完成。
Note: 文章的内容基于 JDK1.7 进行剖析。1.8 做的改变文章开端进行解说。
一、先来相熟一下咱们罕用的 HashMap:
1、概述
HashMap 基于 Map 接口实现，元素以键值对的形式存储，并且容许应用 null 建和 null 值，因为 key 不容许反复，因而只能有一个键为 null, 另外 HashMap 不能保障放入元素的程序，它是无序的，和放入的程序并不能雷同。HashMap 是线程不平安的。
2、继承关系
public class HashMap<K,V>extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
3、根本属性
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认初始化大小 16
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 负载因子 0.75
static final Entry<?,?>[] EMPTY_TABLE = {}; // 初始化的默认数组
transient int size; //HashMap 中元素的数量
int threshold; // 判断是否须要调整 HashMap 的容量
Note：HashMap 的扩容操作是一项很耗时的工作，所以如果能估算 Map 的容量，最好给它一个默认初始值，防止进行屡次扩容。HashMap 的线程是不平安的，多线程环境中举荐是 ConcurrentHashMap。
二、常被问到的 HashMap 和 Hashtable 的区别
1、线程平安
两者最次要的区别在于 Hashtable 是线程平安，而 HashMap 则非线程平安。
Hashtable 的实现办法外面都增加了 synchronized 关键字来确保线程同步，因而相对而言 HashMap 性能会高一些，咱们平时应用时若无非凡需要倡议应用 HashMap，在多线程环境下若应用 HashMap 须要应用 Collections.synchronizedMap()办法来获取一个线程平安的汇合。
Note：
Collections.synchronizedMap()实现原理是 Collections 定义了一个 SynchronizedMap 的外部类，这个类实现了 Map 接口，在调用办法时应用 synchronized 来保障线程同步, 当然了实际上操作的还是咱们传入的 HashMap 实例，简略的说就是 Collections.synchronizedMap()办法帮咱们在操作 HashMap 时主动增加了 synchronized 来实现线程同步，相似的其它 Collections.synchronizedXX 办法也是相似原理。
2、针对 null 的不同
HashMap 能够应用 null 作为 key，而 Hashtable 则不容许 null 作为 key
虽说 HashMap 反对 null 值作为 key，不过倡议还是尽量避免这样应用，因为一旦不小心应用了，若因而引发一些问题，排查起来很是麻烦。
Note：HashMap 以 null 作为 key 时，总是存储在 table 数组的第一个节点上。
3、继承构造
HashMap 是对 Map 接口的实现，HashTable 实现了 Map 接口和 Dictionary 抽象类。
4、初始容量与扩容
HashMap 的初始容量为 16，Hashtable 初始容量为 11，两者的填充因子默认都是 0.75。
HashMap 扩容时是以后容量翻倍即:capacity2，Hashtable 扩容时是容量翻倍 + 1 即:capacity2+1。
5、两者计算 hash 的办法不同
Hashtable 计算 hash 是间接应用 key 的 hashcode 对 table 数组的长度间接进行取模
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
HashMap 计算 hash 对 key 的 hashcode 进行了二次 hash，以取得更好的散列值，而后对 table 数组长度取摸。
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
static int hash(int h) {
// 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);
}
static int indexFor(int h, int length) {
return h & (length-1);三、HashMap 的数据存储构造
1、HashMap 由数组和链表来实现对数据的存储
HashMap 采纳 Entry 数组来存储 key-value 对，每一个键值对组成了一个 Entry 实体，Entry 类实际上是一个单向的链表构造，它具备 Next 指针，能够连贯下一个 Entry 实体，以此来解决 Hash 抵触的问题。
数组存储区间是间断的，占用内存重大，故空间简单的很大。但数组的二分查找时间复杂度小，为 O(1)；数组的特点是：寻址容易，插入和删除艰难；
链表存储区间离散，占用内存比拟宽松，故空间复杂度很小，但工夫复杂度很大，达 O（N）。链表的特点是：寻址艰难，插入和删除容易。
从上图咱们能够发现数据结构由数组 + 链表组成，一个长度为 16 的数组中，每个元素存储的是一个链表的头结点。那么这些元素是依照什么样的规定存储到数组中呢。个别状况是通过 hash(key.hashCode())%len 取得，也就是元素的 key 的哈希值对数组长度取模失去。比方上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以 12、28、108 以及 140 都存储在数组下标为 12 的地位。
HashMap 外面实现一个动态外部类 Entry，其重要的属性有 hash，key，value，next。
HashMap 外面用到链式数据结构的一个概念。下面咱们提到过 Entry 类外面有一个 next 属性，作用是指向下一个 Entry。打个比方，第一个键值对 A 进来，通过计算其 key 的 hash 失去的 index=0，记做:Entry[0] = A。一会后又进来一个键值对 B，通过计算其 index 也等于 0，当初怎么办？HashMap 会这样做:B.next = A,Entry[0] = B, 如果又进来 C,index 也等于 0, 那么 C.next = B,Entry[0] = C；这样咱们发现 index= 0 的中央其实存取了 A,B,C 三个键值对, 他们通过 next 这个属性链接在一起。所以疑难不必放心。也就是说数组中存储的是最初插入的元素。到这里为止，HashMap 的大抵实现，咱们应该曾经分明了。
public V put(K key, V value) {
if (key == null)
return putForNullKey(value); //null 总是放在数组的第一个链表中
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
// 遍历链表
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 如果 key 在链表中已存在，则替换为新 value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e); // 参数 e, 是 Entry.next
// 如果 size 超过 threshold，则裁减 table 大小。再散列
if (size++ >= threshold)
resize(2 * table.length);}
四、重要办法深度解析
1、构造方法
HashMap() // 无参构造方法
HashMap(int initialCapacity) // 指定初始容量的构造方法
HashMap(int initialCapacity, float loadFactor) // 指定初始容量和负载因子
HashMap(Map<? extends K,? extends V> m) // 指定汇合，转化为 HashMap
HashMap 提供了四个构造方法，构造方法中，依附第三个办法来执行的，然而前三个办法都没有进行数组的初始化操作，即便调用了构造方法此时寄存 HaspMap 中数组元素的 table 表长度仍旧为 0。在第四个构造方法中调用了 inflateTable()办法实现了 table 的初始化操作，并将 m 中的元素增加到 HashMap 中。
2、增加办法
public V put(K key, V value) {
if (table == EMPTY_TABLE) { // 是否初始化
inflateTable(threshold);
}
if (key == null) // 搁置在 0 号地位
return putForNullKey(value);
int hash = hash(key); // 计算 hash 值
int i = indexFor(hash, table.length); // 计算在 Entry[]中的存储地位
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;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i); // 增加到 Map 中
return null;}
在该办法中，增加键值对时，首先进行 table 是否初始化的判断，如果没有进行初始化（调配空间，Entry[]数组的长度）。而后进行 key 是否为 null 的判断，如果 key==null , 搁置在 Entry[]的 0 号地位。计算在 Entry[]数组的存储地位，判断该地位上是否已有元素，如果曾经有元素存在，则遍历该 Entry[]数组地位上的单链表。判断 key 是否存在，如果 key 曾经存在，则用新的 value 值，替换点旧的 value 值，并将旧的 value 值返回。如果 key 不存在于 HashMap 中，程序持续向下执行。将 key-vlaue, 生成 Entry 实体，增加到 HashMap 中的 Entry[]数组中。
3、addEntry()
/*
- hash hash 值
- key 键值
- value value 值
- bucketIndex Entry[]数组中的存储索引
- /
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {resize(2 * table.length); // 扩容操作，将数据元素从新计算地位后放入 newTable 中，链表的程序与之前的程序相同
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;}
增加到办法的具体操作，在增加之前先进行容量的判断，如果以后容量达到了阈值，并且须要存储到 Entry[]数组中，先进性扩容操作，空充的容量为 table 长度的 2 倍。从新计算 hash 值，和数组存储的地位，扩容后的链表程序与扩容前的链表程序相同。而后将新增加的 Entry 实体寄存到以后 Entry[]地位链表的头部。在 1.8 之前，新插入的元素都是放在了链表的头部地位，然而这种操作在高并发的环境下容易导致死锁，所以 1.8 之后，新插入的元素都放在了链表的尾部。
4、获取办法：get
public V get(Object key) {
if (key == null)
// 返回 table[0] 的 value 值
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {return null;}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;}
在 get 办法中，首先计算 hash 值，而后调用 indexFor()办法失去该 key 在 table 中的存储地位，失去该地位的单链表，遍历列表找到 key 和指定 key 内容相等的 Entry，返回 entry.value 值。
5、删除办法
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);}
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {return null;}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;}
删除操作，先计算指定 key 的 hash 值，而后计算出 table 中的存储地位，判断以后地位是否 Entry 实体存在，如果没有间接返回，若以后地位有 Entry 实体存在，则开始遍历列表。定义了三个 Entry 援用，别离为 pre, e ,next。在循环遍历的过程中，首先判断 pre 和 e 是否相等，若相等表明，table 的以后地位只有一个元素，间接将 table[i] = next = null。若造成了 pre -> e -> next 的连贯关系，判断 e 的 key 是否和指定的 key 相等，若相等则让 pre -> next ,e 失去援用。
6、containsKey
public boolean containsKey(Object key) {
return getEntry(key) != null;
}final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}containsKey 办法是先计算 hash 而后应用 hash 和 table.length 取摸失去 index 值，遍历 table[index]元素查找是否蕴含 key 雷同的值。
7、containsValue
public boolean containsValue(Object value) {
if (value == null)
return containsNullValue();
Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (value.equals(e.value))
return true;
return false;
}containsValue 办法就比拟粗犷了，就是间接遍历所有元素直到找到 value，由此可见 HashMap 的 containsValue 办法实质上和一般数组和 list 的 contains 办法没什么区别，你别指望它会像 containsKey 那么高效。
五、JDK 1.8 的 扭转
1、HashMap 采纳数组 + 链表 + 红黑树实现。
在 Jdk1.8 中 HashMap 的实现形式做了一些扭转，然而根本思维还是没有变得，只是在一些中央做了优化，上面来看一下这些扭转的中央, 数据结构的存储由数组 + 链表的形式，变动为数组 + 链表 + 红黑树的存储形式，当链表长度超过阈值（8）时，将链表转换为红黑树。在性能上进一步失去晋升。
2、put 办法简略解析：
public V put(K key, V value) {
// 调用 putVal()办法实现
return putVal(hash(key), key, value, false, true);}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;
// 判断 table 是否初始化，否则初始化操作
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);
// 链表长度 8，将链表转化为红黑树存储
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//key 存在，间接笼罩
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;}
如果存在 key 节点，返回旧值，如果不存在则返回 Null。
