在Java中，HashMap是一种很常用的数据结构，很多时候都可以见到它的身影，因为它的效率比较高，下面来看看它是个怎么样的存在。
1、首先，从构造函数讲起：
HashMap有4个构造函数，前面三个基本相同
无参构造函数设置默认装载因子(DEFAULT_LOAD_FACTOR)，一个参数的为HashMap的大小(hashMap中数组的大小)，此构造函数调用两个参数的构造函数，传数组大小和默认装载因子，有看到，这几个构造函数都么有初始化数组的大小，第四个构造函数的参数是一个map，就是遍历map，然后把值put到新建的map里面。
2、HashMap是由一个数组加链表(或者红黑树)组成的数据结构。它是怎么存数据的呢，一起看看put方法。
put方法中调用putVal
看看这些参数是什么含义：
hash：经过一次hash的key
key和value就是put方法的key和value了
onlyIfAbsent：为true的时候表示不替换，就是如果已经存在某个key了，那么这个key对应的值就不会被替换，即使再put一个相同的key，值也还是原来的值
evict：这个是在LinkedHashMap中使用的
下面看看这个函数具体做了什么，首先判断table是否为空，为空则调用resize方法初始化，前面说到在构造函数时并没有初始化数组，原来是留到put值的时候才初始化，这在一定程度上节省了内存，因为真正用到的时候才分配内存。接着就是再次hash，找到这次的key在数组中所对应的位置，如果该位置为空，则放在那个位置上就可以了，如果该位置不为空，则表明发生了冲突，HashMap的解决冲突的方法是首先用链表，把新加入的值存到链表的后面，如果链表的长度达到8以后，就自动变成红黑树（调用treeifyBin(tab, hash)）。因为HashMap中存在可能存在链表和树两个结构，所以解决冲突之前，先判断数组当前位置后面的节点是树还是链表，树的话，直接add进去，链表的话就进行上面所说的操作。这个函数的最后还有一点，就是判断扩容
扩容在Java8之后变得很巧妙
resize()
前面的判断就不说了有兴趣自己研究研究，下面说一下精髓部分，首先是把数组后面的链表或者红黑树分成两个链表（这里选链表举例），一个是hash值和旧的数组长度（odlCap）按位与等于0的，另一个链表是不等于0的，为什么要这么划分呢，下面是见证奇迹的时刻：假设旧的数组长度为4（这里为了方便，就假设为4），那么oldCap变成二进制就是0100，这里和putVal方法中的二次hash不同，二次hash是和cap-1按位与，这里是cap，没有减1。
1）
如果结果为0，说明e.hash值的第三位（低位开始）为0，当扩容后长度变成8后，e.hash与8-1（00111）进行hash的结果和与4-1（00011）(原来数组长度-1) 进行hash的结果一样
所以扩容前后相对于数组的位置不变，于是有 newTab[j] = loHead;
2）
如果结果不为0，说明e.hash值的第三位（低位开始）为1，当扩容后长度变成8后，e.hash与8-1（00111）进行hash的结果相当于 与4-1（00011）(原来数组长度-1) 进行hash的结果再加oldCap（4）
所以有 newTab[j + oldCap] = hiHead，扩容后的位置等于原来的位置 + 原来的数组大小
HashMap中的数组长度是2的幂次方有这个好处，避免二次hash。java8后链表采用尾插入法，保持原来的顺序，避免了死循环，8之前采用头插入法，会出现死循环。
8之前采用头插入法，会出现死循环：假设本来有一个链表 a -> b ，扩容时线程1、线程2同时拿到b节点的指针，线程1挂起，此时，线程2开始执行，迁移节点b到新数组，链表变成 b -> a，此时线程1继续从节点b开始迁移到新数组，迁移节点b后，线程1中的链表变成 b -> a，因为由于线程2的复制，节点b的next指向a，所以线程1继续迁移b.next (即节点a)，于是出现死循环 a -> b -> a
java8后增加红黑树，提升查找新能，改用尾插法。如果按照之前的扩容算法，采用尾插法的话，要么变量一遍链表，要么增加一个数组存尾指针，开销都不小，新的扩容算法只需要两个尾指针就搞定，从某种意见上讲，性能有所提升。
网友评论