详解HashMap前置篇

本文将讲述HashMap底层是通过什么数据结构实现的，以及如何计算Key的Hash值，包括初始容量以及为什么这么设计，以及HashMap的扩容机制。

初探HashMap底层是数据结构

首先来看下面这张图，HashMao底层是由数组+链表/红黑树实现的，首先计算Key的Hash值，如出现Hash碰撞则采用链表法解决Hash碰撞；如果链表长度大于8则转为使用红黑树存储提高查询效率。

什么是Hash碰撞？有哪些解决办法？

不同Key计算出来的Hash值相同；常见的解决方法有：

1. 开放定址法：只要发生冲突就去寻找下一个空的散列地址
2. 链地址法：将Hash值相同的元素通过链表相连接
3. 再哈希法：用其他的函数计算另一个哈希函数地址，直到冲突不再产生为止。

Hash是如何计算的？为什么初始容量是16？

下面这段是计算key的Hash值的方法，key.hashCode()就足以完成获取Hash值的功能，为什么还要h >>> 16？

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

hash函数的作用是用来确定key在数组桶中的位置的，使用位运算(&)来代替取模运算(%)效率上会高出很多，源码中计算Hash经常会出现下面一行代码：

index = (table.length - 1) & key.hash(); // 可理解成 key % (table.length - 1)

初始容量为16，假设Hash值为50，&运算是两侧都为1才为1，15的左侧都为0，这意味着只有低4位在做运算，进行&运算过程如下所示：

所以初始容量或者说Hash桶的数量必须是2的正整数次幂，这样才能通过位运算快速定位寻址，而h >>> 16则是让高16位与低16位做异或，目标则是减少Hash碰撞。

既然能使用链表，为什么数组不规定在16？

这里要搞清楚一点，HashMap快的原因是可以根据Hash值能直接找到数据，也就是说需要尽量减少Hash碰撞，链表是在没有办法的情况下才使用的。