本文是hashMap系列的最后一篇文章，接上文
六 HashMap是如何解决hash冲突的
解决哈希冲突的方法一般有：开放定址法、链地址法（拉链法）、再哈希法、建立公共溢出区等方法。
HashMap是用拉链法解决的Hash冲突问题。HashMap的数据结构 ，前两篇文章有介绍过，jdk1.7 是数组+链表的结构 ，jdk1.8是数组+链表+红黑树。正是为了解决Hash冲突以及平衡查询、插入等操作的效率HashMap的作者才将HashMap设计成这种数据结构
我们来具体看一下put方法的源码(jdk1.8)，通过这个过程了解下如何解决冲突
<code>/**
* 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[] tab; Node /<code>p; int n, i;
//tab为空则创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//计算index，并对null做处理
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Nodee; K k;
//节点key存在，直接覆盖value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判断该链为红黑树
else if (p instanceof TreeNode)
e = ((TreeNode)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已经存在直接覆盖value
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;
}
HashMap的put方法执行过程可以通过下图来理解
通过上图和源码注释，我们了解了put方法的执行过程，其中在这一行：
<code>if ((p = tab[i = (n - 1) & hash]) == null)/<code>
计算 index，并对 null 做处理，如果不为 null ,则表明 tab 的这个 i 位置上已经有数据了，hash冲突就发生在了这里。从这里的else条件开始就是hashMap解决hash冲突的过程。也就是所谓的“拉链法”。
这里有几个需要注意的点：
- HashMap采用的链表法的方式，链表是单向链表
- 当发生hash冲突，hashMap的桶中形成链表的时候，新的元素插入到该链表的时候，jdk1.7使用的是“头插法” 即新元素在链表头，而jdk1.8使用的“尾插法” 即新元素在链表尾。
- 在多线程使用场景中，应该尽量避免使用线程不安全的HashMap，而使用线程安全的ConcurrentHashMap
思考题：jdk1.8为什么改头插法为尾插法？
关于上面第三点，其中有个著名的例子，就是在多线程环境下使用HashMap可能产生环链（死循环）问题，当然是在jdk1.7版本，jdk1.8由于使用了“尾插法”就避免了这个问题。在使用jdk1.7的情况下，是put过程中的resize方法在调用transfer方法的时候导致的环链。
我们举例说明一下：
<code>public class HashMapInfiniteLoop {
private static HashMap<integer> map = new HashMap<integer>(2，0.75f);
public static void main(String[] args) {
map.put(5， "C");
new Thread("Thread1") {
public void run() {
map.put(7, "B");
System.out.println(map);
};
}.start();
new Thread("Thread2") {
public void run() {
map.put(3, "A);
System.out.println(map);
};
}.start();
}
}/<integer>/<integer>/<code>其中，map初始化为一个长度为2的数组，loadFactor=0.75，threshold=2*0.75=1，也就是说当put第二个key的时候，map就需要进行resize。下面代码是jdk1.7的
<code>void resize(int newCapacity) { //传入新的容量
Entry[] oldTable = table; //引用扩容前的Entry数组
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了
threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
return;
}
Entry[] newTable = new Entry[newCapacity]; //初始化一个新的Entry数组
transfer(newTable); //！！将数据转移到新的Entry数组里
table = newTable; //HashMap的table属性引用新的Entry数组
threshold = (int)(newCapacity * loadFactor);//修改阈值
}
void transfer(Entry[] newTable) {
Entry[] src = table; //src引用了旧的Entry数组
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
Entry e = src[j]; //取得旧Entry数组的每个元素
if (e != null) {
src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
do {
Entry next = e.next;
int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
e.next = newTable[i]; //标记[1]
newTable[i] = e; //将元素放在数组上
e = next; //访问下一个Entry链上的元素
} while (e != null);
}
}
/<code>通过设置断点让线程1和线程2同时debug到transfer方法的首行。注意此时两个线程已经成功添加数据。放开thread1的断点至transfer方法的“Entry next = e.next;” 这一行；然后放开线程2的断点，让线程2进行完resize。结果如下图。
注意，Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二 rehash 后，指向了线程二重组后的链表。
线程一被调度回来执行，先是执行 newTalbe[i] = e， 然后是e = next，导致了e指向了key(7)，而下一次循环的next = e.next导致了next指向了key(3)。
e.next = newTable[i] 导致 key(3).next 指向了 key(7)。注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。
于是，当我们用线程一调用map.get(11)时，悲剧就出现了——Infinite Loop。
HashMap 有并发问题，并不单单指环链问题，而是在数据结构的设计上就没有考虑并发环境。HashMap 的设计目标是简洁高效，没有采取任何措施保证 put、remove 操作的多线程安全。put 方法的操作对象要么是整个散列表，要么是某个哈希桶里的链表或红黑树，而这些过程都没有采取措施保证多线程安全。在这个复杂的逻辑过程中，任何一个线程在这个过程中改动了散列表的结构，都有可能造成另一个线程的操作失败。
java有一条深入人心的规则：“重写equals()时，必须重写hashCode()”, 那么这是为什么呢？我们从hashMap的源码中也能看出些原因
<code> if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p;/<code>
上面这段比较简单就不解释了，试想如果你的对象没有正确重写这两个方法，那么装在容器中一定会有问题。
閱讀更多 小盒子的技術分享 的文章
