Java HashMap的本质
HashMap的本质其实就是数组加链表。
它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。
HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
HashMap寻址方式
对新数据的插入或者读取数据时，HashMap将Key的哈希值对数组长度取模，结果作为该Entry在数组中的index。在计算机中，取模的代价远高于位操作的代价，因此HashMap要求数组的长度必须为2的N次方。此时将Key的哈希值对2^N-1进行与运算，其效果即与取模等效。HashMap并不要求用户在指定HashMap容量时必须传入一个2的N次方的整数，而是会通过Integer.highestOneBit算出比指定整数小的最大的2^N值。
public static int highestOneBit(int i) {
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}
由于Key的哈希值的分布直接决定了所有数据在哈希表上的分布或者说决定了哈希冲突的可能性，因此为防止糟糕的Key的hashCode实现（例如低位都相同，只有高位不相同，与2^N-1取与后的结果都相同），JDK 1.7的HashMap通过如下方法使得最终的哈希值的二进制形式中的1尽量均匀分布从而尽可能减少哈希冲突。
int h = hashSeed;
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
为什么HashMap线程不安全
HashMap的线程不安全主要体现在resize时的死循环及使用迭代器时的fast-fail上。
resize死循环
当HashMap的size超过Capacity*loadFactor时，需要对HashMap进行扩容。具体方法是，创建一个新的，长度为原来Capacity两倍的数组，保证新的Capacity仍为2的N次方，从而保证上述寻址方式仍适用。同时需要通过如下transfer方法将原来的所有数据全部重新插入（rehash）到新的数组中。
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
这里假设有两个线程同时执行了put操作并引发了rehash，执行了transfer方法，并假设线程一进入transfer方法并执行完next = e.next后，因为线程调度所分配时间片用完而“暂停”，此时线程二完成了transfer方法的执行。此时状态如下。
线程一：
e=key(5)
next=e.next=key(9)
线程二：
table[1]->key(9)->key(5)->null
接着线程1被唤醒，继续执行第一轮循环的剩余部分
e.next = newTable[1] = null
newTable[1] = e = key(5)
e = next = key(9)
e.next=table[1]=null
table[1]=e=key(5)
e=next=key(9)
next=e.next=key(5)
e.next=table[1]=key(5)
table[1]=e=key(9)
e=next=key(5)
next=e.next=null
e.next=table[1]=key(9)
table[1]=e=key(5)
e=next=null
此时循环链表形成，并且key(11)无法加入到线程1的新数组。在下一次访问该链表时会出现死循环。
Fast-fail
在使用迭代器的过程中如果HashMap中key被remove，那么ConcurrentModificationException将被抛出，也即Fast-fail策略。
当HashMap的iterator()方法被调用时，会构造并返回一个新的EntryIterator对象，并将EntryIterator的expectedModCount设置为HashMap的modCount（该变量记录了HashMap被修改的次数）。
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
java8对HashMap的优化
当成员变量 MIN_TREEIFY_CAPACITY（树形最小容量）>64 && TREEIFY_THRESHOLD（树形阈值）>8 时将链表转为红黑树 ,当TREEIFY_THRESHOLD<=6时会再将红黑树转化成链表。
而将链表转为红黑树主要是为了加快hash冲突时的查询速度。整个红黑树的查找，插入和删除都是O(logN)的，原因就是整个红黑树的高度是logN，查找从根到叶，走过的路径是树的高度，删除
和插入操作是从叶到根的，所以经过的路径都是logN。红黑树深入剖析