HashMap学习

HashMap有两个重要参数：初始容量已经加载因子。这两个参数对HashMap的性能有较大影响。

一些变量说明：

初始容量：默认值是1<<4，1左移4位，即16

最大容量：1<<30， = (Integer.MAX_VALUE+1)/2

loadFactor：加载因子，默认值是0.75

threshold： 界限，即容量*加载因子，如果HashMap中数据量超过这个值（即比例超过0.75）时，HashMap就会容量翻倍重置。实际上HashMap类中没有保存初始容量的

数据保存在Node<K,V>[]数组中（table变量）

有4个构造器方法：无参构造器方法，初始容量构造器方法，初始容量和加载因子构造器方法和传入Map对象初始数据的构造器方法。

第一个构造器两个参数均使用默认值；第二个构造器加载因子使用默认值；第四个构造器会判断传入Map对象大小是否超过界限，如果超过则会先调整容量为当前的两倍（这里并没有进行翻倍后是否可以容纳传入Map对象的判断，是否因为如果要初始数据的话，我们应该会对传入数据量有相对准确的判断？），然后再调用putVal()方法将Map对象的数据逐个保存到当前HashMap对象中，在保存过程中，如果当前HashMap对象大小超过界限时，则会再度调用resize()方法进行重置。

resize()方法的本质和逻辑

本质：初始化或者翻倍容量，设置新的threshold和Node<K,V>数组并返回该数组

逻辑：

1）如果已经设置过HashMap容量， 旧容量大于等于最大容量，已经不能翻倍，设置界限变量（threshold）为Integer.MAX_VALUE并返回不做其他调整； 旧容量小于最大容量则进行翻倍，翻倍后的容量值如果在默认初始值与最大值之间，则最界限值翻倍，否则界限值暂不设置。

2）如果未设置容量（Node数组未初始话）但设置过界限值（说明创建实例时有指定初始容量值，调用tableSizeFor方法调整并保存到界限值变量中），那么新的容量=界限值

3）未设置过容量且未设置界限值时，则新容量值=默认容量值，新界限值=新容量*重载因子（取整）

前面设置完容量后，如果界限值未设置（上面第一种情况下中可能出现），则根据新容量值计算并赋给（threshold）变量；接着按照新容量值创建Node<K,V>[]数组和赋值给table变量，然后从旧数组中读取数据并保存到新的数组中，这里保存数据的逻辑（在存在数据的情况下）：

1）如果当前数据元素没有指向下个元素的话，直接保存到这个位置：newTab[e.hash & (newCap - 1)] = e; 这句代码的意思是：将容量值减1后，得到的奇数值转成2进制是全1的，然后与当前元素的hash值进行按位与计算，即从hash值后面截取（容量-1）值的二进制值长度部分计算在数组中的新位置。

2）如果有指向下个元素且是TreeNode实例时，调用该元素的split方法

3）如果当前元素不是TreeNode，而是其他类型链表节点时，循环遍历该元素构造链表，如果遍历到的元素计算出来的位置在旧数组范围内，则该元素放置在低位链表中，如果超出旧数组范围，则放置在高位链表中；遍历结束后，如果有低位链表，则放置到原先的位置，如果有高位链表，则放置到新区间相对于旧区间同样的位置。

tableSizeFor(int cap)方法：

通过传入容量参数初始化HashMap时，会调用这个方法计算容量，由于HashMap的容量值要求是2的幂次方，所以会计算传入值高位方向最近的2的幂次方值，如果将值转换成2进制数来看的话，就是将容量值-1后的2进制数值所有位都变成0，然后前面再增加一位，且值为1；这个计算过程是，先将传入的容量值减1，然后按照1、2、4、8、16位进行自身无符号右移后再或运算，将容量值-1后转换成2进制的值的每一位都变成1，然后再加1完成新容量值的计算。为什么前面要减1呢，因为如果传入的是Integer.MAX_VALUE最大值时，不减1的话按位运算后再+1会超出范围。

与1.7 roundUpToPowerOf2方法对比：

1）1.7方法多了范围逻辑判断，跟构造器的判断重复了

2）1.7方法计算容量值方法不同，是向高位计算，先减1再左移1位，然后将所有位变1取得最大值，再减去此时的值右移1位获得当前最高位值；而1.8方法则是减1后先将所有位变成1后再+1，然后构造器方法有校验数值范围后，此处没有重复判断了。

putVal()方法解析：

1）如果Node<K,V>数值=null，则进行初始化

2）如果计算出来元素在数组中的位置是空的时，则创建新的Node元素并保存到该位置

3）如果不为空，

static final int hash(Object key) 方法：

 (h = key.hashCode()) ^ (h >>> 16)

在Key不为空的情况下，获取key的hash值，然后与该值无符号右移16位后的值进行按位异或运算生成新的hash值

TreeNode<K,V> extends LinkedHashMap.Entry<K,V>

HashMap中的静态final的内部类TreeNode继承LinkedHashMap.Entry内部类，这个Entry内部类也是继承自HashMap.Node<K,V>内部类，只是增加了before和after两个Entry<K,V>两个变量来保存前后元素。

HashMap 1.7版本和1.8版本的不同

 1）计算Key的Hash值的方法不同

2）计算容量的方法不同，1.7是判断传入容量值是否最大，是则取最大，否则减1然后再左移1位，之后将左移后的数值按二进制格式

3）1.7版本使用数组以及链表来储存数据，1.8在1.7基础上增加红黑树来储存数据，当相同Hash值的元素达到8个或以上时，会将链表转换成红黑树结构，如果减少到6个或者以下时则将红黑树转换回链表