HashMap 常问的 9 个问题

1、HashMap 的数据结构是什么？

HashMap 我们知道 HashMap 的数据结构是数组+链表，所以这个问题可以理解为数组+链表有什么优点？

如果只是数组，就存在数组的缺点，如：需要更长的连续内存空间；扩容更加频繁；并且删除操作需要移动其他元素位置，等等
如果只是链表，就存在链表的缺点，如：查找复杂度 O(n) 太高，等等
而数组+链表是一个折中的方案

2、为什么数组的默认长度是 16？

/**
* The default ∞initial capacity - MUST be a power of two. 默认初始容量必须是 2 的幂次方。
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

这跟计算数组下标有关，计算数组下标的代码为 index = hash & (n-1)，当 n 为 2 的幂，如 16，n-1 = 15，转换为二进制为 1111，通过按位与 & ，数组下标就由 hash 二进制的低 4 位决定。比起传统的取模（余）操作，效率更高。

3、为什么 HashMap 没有直接用 Key 的 hashCode，而是生成一个新的 hash？

hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

同样跟数组下标有关，HashMap 没有用取模（余）运算，而是直接使用低 4 位作为数组下标，如果使用 hashCode 低 4 位，碰撞几率很大，将 hashCode 的低位和高位异或生成 hash，取 hash 的低 4 位作为数组下标，可以增加低位的随机性，减少碰撞。>>> 为无符号右移，h >>> 16：舍弃右边 16 位，将高位向右移动 16 位，左边用 0 补齐。

当 key == null 时，hash 为 0，所以 key 可以为 null。

4、扩容因子为 0.75，有什么好处？

// As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put).
// 作为一般的规则，默认扩容因子（.75）在时间和空间成本之间提供了一个很好的折中。较高的值减少了空间开销，但增加了查找成本（反映在 HashMap 类的大多数操作中，包括 get 和 put）。 
static final float DEFAULT_LOAD_FACTOR = 0.75f;

如果是 0.5 的话，空间利用率不高，扩容太频繁。
如果是 1 的话，因为不是均匀分布，碰撞产生链表，扩容后，链表将更长，查找和修改的时间复杂度将更高。
0.75 是一个折中的方案。
注意：扩容触发条件 0.75，不是指数组 75% 的区域被占用时，而是指当前 Map 的容量，包括链表上的元素。

5、HashMap 如何扩容？

// 伪代码
static final float DEFAULT_LOAD_FACTOR = 0.75f;
int threshold = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
if (++size > threshold)
    resize();

final Node<K,V>[] resize() {
    // 创建一个容量为原来的 2 倍的新数组
    newCap = oldCap << 1;
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    for (int j = 0; j < oldCap; ++j) {
        Node<K,V> e;
        if ((e = oldTab[j]) != null) {
            // 当只有一个元素时，根据节点原来的 hash 和新的数组长度得到新的数组下标
            if (e.next == null)
            	newTab[e.hash & (newCap - 1)] = e
            else {
                // oldCap 初始为 16，即 10000，最高位始终为 1，通过 1 来随机判断使用原数组下标还是加上原数组长度的新数组下标
                if ((e.hash & oldCap) == 0)
                    loHead = e
            	else
                    hiHead = e
            	if (loTail != null) {
                    newTab[j] = loHead;
                }
                if (hiTail != null) {
                    newTab[j + oldCap] = hiHead;
                }    
            }
        }
    }
}

首先，HashMap 需要扩容，否则，链表长度过长，查找和修改的复杂度都将变高。
扩容时，创建一个容量为原来的 2 倍的新数组，遍历原数组，如果当前位置只有一个元素，则根据节点原来的 hash 和新的数组长度得到新的数组下标，如果是一个链表，则通过 oldCap 来随机判断使用原数组下标还是加上原数组长度的新数组下标
因为需要扩容，需要额外的性能，在能估算容量的情况下，可以直接设置初始容量。

public HashMap(int initialCapacity) {}

6、HashMap 为什么线程不安全？

/* <p><strong>Note that this implementation is not synchronized.</strong>

HashMap 不是线程安全的，它的线程安全版本是 HashTable 和 ConcurrentHashMap
它的线程不安全是因为 HashMap 存在变量，如 DEFAULT_INITIAL_CAPACITY 等，对象在方法中使用这些共享变量时，没有加锁。共享变量在并发操作，值容易被覆盖，存在丢失数据的问题。
在 jdk 1.7 中，并发操作下，扩容时，还可能造成死循环，Java HashMap.get(Object) infinite loop

7、为什么如果对象作为 HashMap 的 Key，对象需要重写 hashCode 和 equals 方法？

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

因为 HashMap 通过 Key 对象的 hashCode 计算 hash，还通过 equals 方法比较对象是否相同，如果不重写，相同内容的两个对象，其 hashCode 将不同，也不会相等。

String 常作为 Map 的 Key，String 如何重写：

hashCode() - 如果字符串已经存在，那么 hash 不变；如果不存在，通过每个字符的 ASSCII 码计算

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

equals() - 依次比较每个字符是否相同

public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof String) {
        String anotherString = (String)anObject;
        int n = value.length;
        if (n == anotherString.value.length) {
            char v1[] = value;
            char v2[] = anotherString.value;
            int i = 0;
            while (n-- != 0) {
                if (v1[i] != v2[i])
                    return false;
                i++;
            }
            return true;
        }
    }
    return false;
}

注意：HashSet 是特殊的 HashMap，存放在 HashSet 的对象都需要重写 hashCode() 和 equals() 方法

8、get() 和 containsKey() 的时间复杂度是多少？

// This implementation provides constant-time performance for the basic operations (get and put)
// 这个实现为基本操作（get 和 put）提供了常量时间性能，假设散列函数将元素正确地分散在存储桶中。

时间复杂度为 O(1)，因为链表的长度不会过长，基本不会达到 8 个

9、当链表长度大于 8 个时，将链表转换为红黑树，有什么好处？

链表查找的时间复杂度时 O(n)
红黑树查找的时间复杂度时 O(logN)
所以好处是查找和修改的时间复杂度更低