使用的数据机构

Node[] 链接结构 TreeNode[] 红黑树结构

• 使用hash表（数组+链表），当链表过长时将其转成红黑树以实现O(logn)时间复杂度的查找

如何工作(put方法过程)

DEFAULT_INITIAL_CAPACITY = 16 初始化容量
MAXIMUM_CAPACITY= 1 << 30  = 1073741824 最大容量
DEFAULT_LOAD_FACTOR = 0.75f 默认填充因子(扩容因子)
TREEIFY_THRESHOLD = 8 阈值，当桶(bucket)上的链表数大于这个值时会转成红黑树，put方法的有用到
UNTREEIFY_THRESHOLD = 6 阈值，同上一个相反，当桶(bucket)上的链表数小于这个值时树转链表
MIN_TREEIFY_CAPACITY = 64 树的最小的容量，至少是 4 * TREEIFY_THRESHOLD = 32 然后为了避免(resizing 和 treeification thresholds) 设置成64
Node<k,v>[] table 存储元素的数组，总是2的倍数
threshold 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
loadFactor 填充因子

<<左移运算：按二进制形式把所有的数字向左移动对应的位数，高位移出（舍弃），低位的空位补零。
>>右移运算：按二进制形式把所有的数字向右移动对应巍峨位数，低位移出（舍弃），高位的空位补符号位，即正数补零，负数补1.
1 << 30
0000 0000 0000 0000 0000 0000 0000 0001 -----> 0010 0000 0000 0000 0000 0000 0000 0000
在计算二进制转十进制得到 1073741824

• 初始化数组resize()，如果Node<K,V>[] tab为空初始化长度为16的数组
• 计算key的hashCode，并计算下标

什么是hash碰撞呢？两个输入串的hash函数的值一样，则称这两个串是一个碰撞(Collision)。
h >>> 16 避免hash碰撞(hash collisons)将高位分散到低位上，最后进行高16位与低16位^异或运算得出key的hash值
(n - 1) & hash]) 计算下标

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

• 如果没有碰撞直接放入桶中

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

• 如果发生碰撞了以链表的方式放到后面

if (p.hash == hash &&
   ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;

......
afterNodeAccess(e);

• 如果链表长度超过阈值（TREEIFY_THRESHOLD > 8）,把链表转化成红黑树

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);
    break;
}

• 如果节点已经存在替换旧值
• 如果桶满了(容量*填充因子，默认是16 x 0.75)，就resize()扩容，扩容的大小是2的n次方

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;
}

冲突解决、扩容过程、原数组扩容后的位置？

• 将新节点加到链表后
• 至少2的n次方的扩容，重新计算hash值
• 原下标或者原下标+原容量的位置