存储结构
hashmap在jdk1.8之前采用数组加链表的方式存储，根据key的hash计算存储在数组中的位置，因为hash可能重复，当hash值重复时，则在该数组元素下卦一个链表，jdk1.8以后，默认当链表长度大于8时，会在该链表下挂一个红黑树。
- 如何计算hash
使用数据的hash值与数组长度进行按位与运行hash(data) & table.length
效果相当于取模，得到的值不会大于数组长度（redis中的slot也是这样的算法）
效率
所以对于没有链表数组元素的操作，比如CRUD都很快，只需一次寻址即可，如果定位到有链表的数组元素，对于添加操作其时间复杂度依然位O(1)，因为最新的Entry会插入链表的头部，只需要简单的改变引用链即可，但是对于查找来说，就需要遍历整个链表，通过key的equals方法逐一对比。
容量问题
解释1：创建hashmap和hashtable时，若不指定初始容量值，hashtable默认的初始值为11，之后每次扩充，容量变为原来的==2n+1==。hashmap默认初始大小为16，之后每次扩容，容量变为原来的==2倍==。如果创建时制定了大小，hashtable会直接使用给定大小，但hashmap会将其扩充到==2的幂次方==大小。也就是说hashmap总是使用2的幂次方作为hash表的大小。原因：为了能让hashmap存取高效，尽量减少碰撞，也就是说要尽量把数据分配均匀，每个链表/红黑树长度大致相同，首先会想到取余操作实现，但是，取余（%）中如果除数是2的幂次则等价于与其除数减一的与（&）操作，即 hash%length==hash&(length-1)，前提是length是2的n次方，并且二进制操作&相对于%能提高效率，这就解释了hashmap的长度为什么是2的幂次方。
解释2：
根据上面计算元素在数组中的角标算法（按位与），则table的长度的二进制必须得是 000011111的形式（后面必须全是连续的1），否则进行按位与时就有的值取不到，例如，如果表长为 0110（十进制为6），则任何数据与其进行按位与时都无法取到 xxx1，因为按位与必须两个数据对应位置全是1结果才是1。这样就浪费了一个空间