-2c57ec47146f40cbabf9adc9f224a0a3.jpg)
老弟虽然不能陪你一生，但是能让你对Map的理解满满登登。怎么说呢HashMap是不是让你又爱又恨呢，工作中最常使用的类，仅次于ArrayList,用起来随心应手，面试还总会被面试官问到说说JDK中的HashMap,诸如HashTable和HashMap的区别，HashSet和HashMap的区别，问你1.7版本和1.8版本，JDK对其有什么特殊的优化，还回问你为什么HashMap不能够在多线程环境下使用，以及多线程环境下的ConcurrentHashMap，究极版让是实现一个HashMap的，写出put和get方法。如果你对上面的问题都能一眼在脑海中有答案，那你基本不需要看这篇文章。由简单问题开始对HashMap抽丝剥茧。
HashTable和HashMap的区别
- 从类结构来说
都实现了Map接口，HashMap继承自AbstractMap，而HashTable继承自Dictionary。 - 线程安全来讲
HashTable是线程安全的，HashMap多线程访问不保证数据准确性。HashMap支持存键为null的数据，HashTable则不支持。 - 扩容方式二者不同
HashTable初始化默认容量为11,每次扩容为原来容量的2倍+1；而HashMap则是原来容量的2倍。 - 遍历的方式
HashMap的遍历基于迭代器进行遍历，HashTable则是使用Enumeration方式。 - 散列函数不同
HashMap使用源对象的HashCode异或上源对象的hashCode右移16位得到。HashTable则是直接使用源对象的HashCode。
HashSet和HashMap的区别
HashSet内部使用了一个HashMap，只不过这个Map中的value都是Object对象(PRESENT)。
1.7版本和1.8版本HashMap处理
- 1.7版本的HashMap
数据存储是数组加链表。采取的是先扩容，头插插入 - 1.8版本的HashMap
数组加链表，当链表的长度超过8个的时候会转换为一棵红黑树。尾插法插入新节点，后扩容。
为什么HashMap不能够在多线程环境下使用
内心真的无语，JDoc上都写了多线程环境下不建议使用，非要使用会引起数据不一致的问题，但是面试呢还是会问你为什么不能使用，wdnmd。
这一切都要从扩容开始说起。其实不止是扩容会有问题，像内部的++size之类的操作都不是原子操作，不过声名远播(面试官总爱问的)的则是在扩容阶段的并发问题，面试还总问。先看1.8版本中的扩容方法。
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)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = 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"})
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
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
先来看resize方法主要是遍历旧数组，然后在那个头节点处理，当节点类型是红黑树的时候，调用split方法进行扩容，当前节点是单链表时候进行和旧的数组容量做与运算。
- （e.hash & oldCap) == 0
等于0的情况下将其在新数组的索引和原来的位置不变。 - （e.hash & oldCap) != 0
在新数组当中从旧的数组容量起开始顺序存放。
大多数的帖子都说1.8改了单链表的插入变成尾插法，是为了避免并发中的环形数组。其实并不是这样的，我理解这个东西的映入根本不是为了在处理环形数组，避免出现环形数组是因为扩容处理不一样了。而尾插法主要是为了引入红黑树。在putVal方法中我们就看到从头节点往后遍历计数，当超过8个就转换为红黑树进行插入。OK回归到1.8版本扩容的时候出现的并发问题，出现在哪里呢 当多个线程进行扩容操作时候，当A线程把同一个数组下标的单链表[1](A->B->C->D->null）做扩容之后变A,B的hash值符合（e.hash & oldCap) == 0,所以保存在原来的位置[1]（A->B->null）,C,Dd的hash值不符合呢则存放在[3]（C->null),[4]（D->null)。此时B线程得到执行权限，他呢并不知道已经发生了扩容，还是要去执行扩容，同样执行到迁移[1]的数据，但是次数A节点的指向已经发生了改变，当B线程重复A,B节点的hash值师傅满足（e.hash & oldCap) == 0，满足之后存放在数组原来的位置，由于B节点之后的数据没有，所以直接结束遍历单链表返回。此时B线程就丢失了C,D节点。
还有就是多线程执行put方法的putVal方法的size计数也是不准确的,转换红黑树多线程操作也会出现死循环。一起来看下代码
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;
}
- Node数组容量为空，延迟初始化操作，首先进行初始化容量。调用resize方法。
- 当前hash定位的Node数组下标是否存在数据，不存在则直接赋值
- 判断数组下标的节点对应的类型是不是红黑树。如果是执行红黑树的插入
- 列表计数，统计长度，如果单链表的节点个数超过8个，调用
treeifyBin进行处理。
4.1treeifyBin回判断当前map的容量(Node数组大小)是否超过64。如果没超过进行扩容操作。
4.2 超过64容量之后会把该节点为头节点的单链表进行树化，执行红黑树的转化。 - 单链表个数不满8个，插入当前节点
- 增加Map容量，执行回调处理(适配LinkedHashMap)
/**
* 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;
}
- 当前hash定位的Node数组下标是否存在数据，存在则直接返回
- 判断数组下标的节点对应的类型是不是红黑树。如果是执行红黑树查找
- 进行单链表遍历，遍历完找不到，返回null
ConcurrentHashMap 分析
哈。这么重要的工具类这么可以如此简简单单的叨叨几句就ok。新开篇分析。期待我能分析完全，每次都分析到一般就不弄了，这层我一定要写个完全体。