HashMap

• HashMap的内部包含了一个Node类型的数组table，Node是静态内部类，实现类Map.Entry接口，有四个主要属性：key、value、next、hash。也就是说table数组的每个位置看做是一个桶，一个桶可以存储一个单向链表。HashMap 使用拉链法来解决冲突，同一个链表中存放哈希值和散列桶取模运算结果相同的节点。

• 初始容量：默认是16，也可以使用带参的构造函数指定初始值，但是会被调整成大于这个值的最小的2的次幂，这是为了在确定数组索引位置，哈希取模的时候方便使用位运算替代取模运算。

• 使用tableSizeFor(int cap)函数获得大于cap的最小的2次幂　　　　　　

static final int tableSizeFor(int cap) {
    int n = cap - 1;//大于或者等于
    n |= n >>> 1;//以下5个右移，位或操作是为了把最高位1的后面都变成1，最后结果加1就得到了大于这个数的最小2次幂
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

• 哈希函数：将哈希值与右移16位后的结果进行异或操作，合并高位的影响，否则由于数组长度的限制，哈希值的高位永远不会在计算索引时使用到。另外考虑到Null值的存在，如果key为Null,hash的结果直接返回0.

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

  • 计算索引：哈希值与table数组的大小取模，转换为位运算就是：哈希值与数组长度减1进行位与运算，因为数组长度始终是2的次幂，减一之后的结果再与哈希值进行位与运算和取模的结果是一样的。位运算效率更高。

• 红黑树在JDK8及以后的版本中，HashMap引入了红黑树，底层的数据结构变成了数组+链表或数组+红黑树。HashMap桶中添加元素时，若链表个数超过8，链表会转换成红黑树。 主要是为了寻找一种时间和空间的平衡。

  • 是根据概率统计而选择的,和hashcode碰撞次数的泊松分布有关，在负载因子0.75（HashMap默认）的情况下，单个hash槽内元素个数为8的概率小于百万分之一，大于等于8转红黑树，小于等于6才转链表。红黑树中的TreeNode是链表中的Node所占空间的2倍，虽然红黑树的查找效率为O(logN)，要优于链表的O(N)，但是当链表长度比较小的时候，即使全部遍历，时间复杂度也相差不大。所以，要寻找一种时间和空间的平衡，即在链表长度达到一个阈值之后再转换为红黑树。链表中元素个数为8时的概率已经非常小，所以在选择链表元素个数时选择了8.

• put操作：

  1. 根据Key的哈希值计算在数组中的索引，如果索引位置上是空的（此时没有冲突），就在这个位置新建一个链表节点。

  2. 如果发生冲突，接下来的思路就是已经存在的节点是否是相同的key，相同就替换，已经存在的没有相同的Key，就使用尾插法在链表结尾插入新的节点，如果是红黑树就在红黑树中进行。

  3. 维护modCount++，并判断++size是否超过threshold,是否需要扩容。

     扩容：

     • 计算新的容量，新容量是旧容量的2倍

     • 根据扩容后的容量新建一个Node数组，并且把table的引用指向新的数组。把旧数组的元素转移到新表，元素在新表中的位置有两种可能：

       1. 如果(e.hash & oldCap) == 0，原位置 j

       2. 如果(e.hash & oldCap) != 0,新位置 j+oldCap

          oldCap=16 0000 0000 0001 0000

          hash=5 0000 0000 0000 0101 旧索引是：5

          &运算 0000 0000 0000 0000 ==0 ——>新索引=5， newCap=32

          oldCap=16 0000 0000 0001 0000

          hash=17 0000 0000 0001 0001 旧索引是：1

          &运算 0000 0000 0001 0000 !=0——> 新索引=17， newCap=32

     • 对旧数组的同一个位置上的链表进行转移时，维护两个链表，一条是在新数组的相同索引位置，另一条的索引是原索引基础上加上旧的容量，采用尾插法插入节点

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//新的数组
table = newTab;
if (oldTab != null) {
    for (int j = 0; j < oldCap; ++j) {
        Node<K,V> e;
        if ((e = oldTab[j]) != null) {
            oldTab[j] = null;
            if (e.next == null)//只有一个节点的情况
                newTab[e.hash & (newCap - 1)] = e;
            else if (e instanceof TreeNode)//红黑树的情况
                ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
            else { // 维护连个链表，低位链表的索引与原索引相同，高位链表的索引在原索引基础上加上旧的容量
                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) {//原位置j
                        if (loTail == null)
                            loHead = e;
                        else
                            loTail.next = e;//尾插法
                        loTail = e;
                    }
                    else {//原索引+旧容量：j+oldCap
                        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;//高位链表
                }
            }
        }
    }
}

• get操作：

  1. 根据哈希值和数组长度得到索引，如果数组在该索引的位置是非空的，再进行后续操作，否则直接返回null

  2. 判断该位置的第一个节点哈希值是否相等，equals是否为真，如果判断为真就直接返回这个节点，否则进行下一步

  3. 判断下一个节点是否存在，判断节点类型是否是红黑树，如果是红黑树就在红黑树中查找，否则就在不断循环链表的下一个节点进行查找。