结构图
讲一下HashMap的原理，内部数据结构？
HashMap的底层是使用hash表–数组+链表（单向），当链表多长会将链表转换成红黑树的实现，因为红黑树的查找时间复杂度为O（logn）
讲一下HashMap中的put方法步骤？
transient Node
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}高16位与低16位进行异或运算，满足插入的数据尽可能的均匀的分配，如果碰撞概率高 就会导致某一个节点链表会很长，而其他节点确实空的不能得到有效利用
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node 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 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)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;
} 步骤：
- 对key求hash值，然后计算出小标index（table[index]）
- 判断table是否为空，为什么会判断为null的情况，则初始化table数组
- 如果这个节点数据为空则直接放入
- 如果节点已经存在，则替换value
- 如果碰撞，以链表的方式方法next=null中next=当前Node
- 如果链表长度超过8，binCount >= TREEIFY_THRESHOLD – 1，就把链表转成红黑树
- 如果table大小已经达到（阈值*数组容量），就需要rezise，另外rezise后原来如果在table[2]则扩容后可能就是table[2]或者table[18]。
讲一下HashMap怎样解决冲突，讲一下扩容过程，加入一直在原数组中，现在移动了新数组，位置可能变了，那是怎么定位到这个值新数组中的位置？
- 将新节点加到链表后
- 容量扩充为原来的两倍，然后对每一个节点重新计算hash值
- 这个值只可能在两个地方，一个是原来的位置，另外一个是下标=原下标+原始容量 的位置，
抛开HashMap。hash冲突有哪些解决办法？
开放地址，链地址法
HaspMap怎么获取table的Index？
（n-1）&hash相当于hash%n,不过前者是二进制的运算，后者是十进制的运算，明显前者比后者性能要好
比如说n=16，那么n-1=15,15的二进制表达为01111。然后比如说key通过hash方法得到是1111101101101。
000000001111
1111101101101
————————
000000001101=13，13是小于16的。这种方式速度快性能高
为什么容量必须是2的n次幂？
如果不是2的n次幂，容量为15，则n-1=14。14的二进制表达为1110
想想前面已经采用hash方计算出来的hash值是为了充分利用table数组。
1110和任何数进行异或运算，不管怎么计算最后一位肯定是0。那上面那个key的hash值来运算
000000001110
1111101101101
—————————–
000000001100
这样就会导致某些节点数据过多，某些节点根本没有数据
所以说扩容的时候16*=32,32*2=64……..都是2的n次幂
针对HashMap中某个entry链太长，查找的时间复杂度可能达到O(n)，怎么优化？
将链表转换成红黑树，JDK1.8已经实现了
如果链表大小一直减少，到什么时候把红黑树转换成链表？
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net
