HashMap的底层数据结构
一、HashMap基础机构
HashMap 由数组和链表（或红黑树）组成。数组是 HashMap 的主体，链表和红黑树则是为了解决哈希冲突而存在的。数组中的每个元素都是一个单向链表的头结点，每个链表都是由若干个 Node 节点组成的，每个节点都包含了键值对的信息，以及指向下一个节点的指针。当多个键映射到同一个位置时，它们会被存储在同一个链表中（或者是同一个红黑树中）。当链表长度超过阈值（默认为 8）时，链表就会被转换成红黑树，这样可以提高查找效率。
在 JDK1.8 中，HashMap 还引入了一个新的概念，叫做负载因子(load factor)，它是指哈希表中键值对的数量与数组长度的比值。当键值对的数量超过了负载因子与数组长度的乘积时，就会触发扩容操作，HashMap 会自动将数组长度扩大一倍，并将原来的键值对重新分配到新的数组中。这样做的目的是为了保证散列表的性能，因为当负载因子过高时，散列表的性能会急剧下降。
二、HashMap的底层数据结构
解答：在jdk1.8以前，HashMa采用链表+数组，自Jdk1.8以后，HashMap采用链表+数组+红黑树。在下图中横链(0-15)表中表示数组，竖(1-8)表示链表，在数组长度超过8之后，hashmap将数组自动转为红黑树。
HashMapJDK1.8链表和红黑树转化
三、JDK1.8对hash算法和寻址算法如何优化的？
1、对Hash值算法的优化
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
有一个key的Hash_1值：
Hash_1: 1111 1111 1111 1111 1111 1010 0111 1100
h >>> 16 // 表示对该hash值右移16位
右移后的结果Hash_2为：
Hash_2: 0000 0000 0000 0000 1111 1111 1111 1111
对上述Hash_1和Hash_2的两个值进行异或
Hash_1: 1111 1111 1111 1111 1111 1010 0111 1100
Hash_2: 0000 0000 0000 0000 1111 1111 1111 1111
=====>: 1111 1111 1111 1111 0000 0101 1000 0011 =====> 转为10进制int值，这个值就是这个key的hash值
hash算法的优化：对每个hash值，在它的低16位中，让高低16位进行异或，让它的低16位同时保持了高低16位的特征，尽量避免一些hash值后续出现冲突，大家可能会进入数组的同一位置。
2、对寻址算法的优化
(p = tab[i = (n - 1) & hash]
// (n-1) & hash ==> 数组里的一个位置
hash & (n-1) 效果是跟hash对n取模是一样的，但是与运算的性能要比hash对n取模要高很多。数组的长度会一直是2的n次方，只要他保持数组长度是2的n次方。
- 寻址为什么不用取模？
对于上面寻址算法，由于计算机对比取模，与运算会更快。所以为了效率，HashMap 中规定了哈希表长度为 2 的 k 次方，而 2^k-1 转为二进制就是 k 个连续的 1，那么 hash & (k 个连续的 1) 返回的就是 hash 的低 k 个位，该计算结果范围刚好就是 0 到 2^k-1，即 0 到 length - 1，跟取模结果一样。
也就是说，哈希表长度 length 为 2 的整次幂时， hash & (length - 1) 的计算结果跟 hash % length 一样，而且效率还更好。
- 为什么不直接用 hashCode() 而是用它的高 16 位进行异或计算新 hash 值？#
int 类型占 32 位，可以表示 2^32 种数（范围：-2^31 到 2^31-1），而哈希表长度一般不大，在 HashMap 中哈希表的初始化长度是 16（HashMap 中的 DEFAULT_INITIAL_CAPACITY），如果直接用 hashCode 来寻址，那么相当于只有低 4 位有效，其他高位不会有影响。这样假如几个 hashCode 分别是 210、220、2^30，那么寻址结果 index 就会一样而发生冲突，所以哈希表就不均匀分布了。
寻址算法的优化：用与运算替代取模，提升性能。（由于计算机对比取模，与运算会更快）
四、HashMap是如何解决hash碰撞问题
hash冲突问题，链表+红黑树，O(n)和O(logN)。
hashmap采用的就是链地址法（拉链法），jdk1.7中，当冲突时，在冲突的地址上生成一个链表，将冲突的元素的key，通过equals进行比较，相同即覆盖，不同则添加到链表上，此时如果链表过长，效率就会大大降低，查找和添加操作的时间复杂度都为O(n)；但是在jdk1.8中如果链表长度大于8，链表就会转化为红黑树，时间复杂度也降为了O(logn)，性能得到了很大的优化。
HashMapJDK1.8链表和红黑树转化
五、HashMap是如何进行扩容的
HashMap底层是一个数组，当这个数组满了之后，他就会自动进行扩容，变成一个更大数组。
1、JDK1.7下的扩容机制
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
代码中可以看到，如果原有table长度已经达到了上限，就不再扩容了。如果还未达到上限，则创建一个新的table，并调用transfer方法：
/**
* Transfers all entries from current table to newTable.
*/
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; //注释1
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity); //注释2
e.next = newTable[i]; //注释3
newTable[i] = e; //注释4
e = next; //注释5
}
}
}
transfer方法的作用是把原table的Node放到新的table中，使用的是头插法，也就是说，新table中链表的顺序和旧列表中是相反的，在HashMap线程不安全的情况下，这种头插法可能会导致环状节点。
2、JDK1.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 // 重新计算TREEIFY_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) { // 重新计算原来链表中的值的hash值在新表对应的hash值
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null) // 如果元素e的下一个位置没有值，则说明可以存放元素
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) // 如果已经是红黑树的节点，那就对其重新划分
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// loHead: 下标不变情况下的链表头
// loTAIl: 下标不变情况下的链表尾
// hiHead: 下标改变情况下的链表头
// hiTail: 下标改变情况下的链表尾
// 如果
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) { // 元素e的最新hash如果与原来的值与计算之后如果值为0，就说明是使用原来的index
// 尾插法插入元素e
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
// 与运算不等于0则说明使用新的index
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;
}
正常情况下，计算节点在table中的下标的方法是：hash&(oldTable.length-1)，扩容之后，table长度翻倍，计算table下标的方法是hash&(newTable.length-1)，也就是hash&(oldTable.length*2-1)，于是我们有了这样的结论：这新旧两次计算下标的结果，要不然就相同，要不然就是新下标等于旧下标加上旧数组的长度。
数组长度为16时，有两个keyA和keyB。
KeyA：
n-1: 0000 0000 0000 0000 0000 0000 0000 1111
hash1: 1111 1111 1111 1111 0000 1111 0000 0101
&结果: 0000 0000 0000 0000 0000 0000 0000 0101 = 5
KeyB:
n-1: 0000 0000 0000 0000 0000 0000 0000 1111
hash1: 1111 1111 1111 1111 0000 1111 0001 0101
&结果: 0000 0000 0000 0000 0000 0000 0000 0101 = 5
在数组长度为16的时候，他们两个hash值冲突会使用拉链发解决冲突。
当数组长度扩容到32之后，需要重新对每个hash值进行寻址，也就是每个hash值跟新的数组length-1 进行操作。
KeyA：
n-1: 0000 0000 0000 0000 0000 0000 000*1* 1111
hash1: 1111 1111 1111 1111 0000 1111 0000 0101
&结果: 0000 0000 0000 0000 0000 0000 0000 0101 = 5
KeyB:
n-1: 0000 0000 0000 0000 0000 000*1* 0000 1111
hash1: 1111 1111 1111 1111 0000 1111 0001 0101
&结果: 0000 0000 0000 0000 0000 000*1* 0000 0101 = 21
判断二进制结果是否多出一个bit的1，如果没有多，那就用原来的index，如果多出来了那就用index+oldCap，通过这个方式，避免了rehash的时候，用每个hash对新数组的length取模，取模性能不高，位运算性能比较高。
