HashMap.put 处理流程

HashMap.put

容量2的倍数？元素位置怎么确认的?

/**
*找到大于或等于 cap 的 最小2的n次幂
**/
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

hash值计算，低位和高位异或，在容量小的情况下，更加散列，减少冲突：

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

位置：(capacity - 1) & hash

好处：

• 可以用 位与 运算代替 取模 运算；
• 扩容时，容量扩大一倍后，如果 hash & oldCap == 0，元素位置为原位置； hash & oldCap == 1，原位置+旧容量值，避免了哈希冲突处理；

为什么负载因子是0.75?

负载因子越大，空间利用率越高，冲突机率越大，增加结构复杂性，查找成本高；

负载因子越小，空间利用率越小，冲突率低，查找效率高；

冲突率和空间利用率，0.75是个最佳实践

为什么树化？树化和反树化时机？

红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。加快检索速率。

插入元素后，判断链表长度大于8，就树化；

扩容时，判断链表长度小于6，就反树化；

线程不安全的原因

1.在jdk1.7中，在多线程环境下，头插法，扩容时会造成环形链或数据丢失。

2.在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。