put() 方法执行流程

  1. put(key, value)，先通过 hash() 方法计算出key的hash值。
  2. 判断Node数组是否初始化，没有则初始化数组，并赋值长度n=初始化数组的长度。
  3. 通过key的hash值计算出要放在数组的哪个地方，即计算出数组下标，tab[i]。i=(n-1) & hash。限定数组的长度要为2的n次方数
  4. 计算出的要放在数组的位置如果没有数据，则new一个节点将数据直接放进去。tab[i]=newNode(hash,key,value,null)。
  5. 如果要放的位置已经有数据了，则判断key是否相等，如果key相等，则会将节点value的值进行替换。
  6. 如果key不想等，判断当前位置的Node类型是否为TreeNode类型，是，则new一个TreeNode对象将数据插入到红黑数中。
  7. 如果是Node类型，遍历Node链表，找到next属性为null的节点即找到尾节点，并new一个节点将原尾节点next值赋值为插入的数据。将数据插入链表尾部。在遍历时，如果发现key相同，则break循环，更新value值。
  8. 遍历过程中，如果发现put新节点时原链表长度>=8，判断数组的长度，如果数组的长度>=64，则将原链表转为红黑树，否则会对数组进行扩容。treeifyBin()
  9. 判断是否需要扩容。加载因子0.75 （++size > threshold），满足条件则针对数组进行扩容，扩容为双倍扩容。

hash()

1
2
3
4
5
6
static final int hash(Object key) {
	int h;
    return (key == null) ? 0 : (h = key.hashcode()) ^ (h >>> 16);
}

//扰动+寻址，让hashcode的高位也一起参与到计算数组下标的计算中，减少hash冲突的概率。

treeifyBin()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            //遍历链表，将每个Node对象替换为TreeNode，并将单向链表改为双向链表方便操作。
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

& 与位运算

有一个0则为0，都为1才为1。

15 0000 1111

n 0101 0101

& 0000 0101