HashMap简介HashMap是一个基于哈希表实现的无序键值容器，它的键和值都允许设置为null，是一个线程不安全。HashMap底层是在jdk1.7中实现的。HashMap是由数组+链表实现的。在jdk1.8中引入了红黑树，HashMap底层变成数组+链表+红黑树实现红黑树。简介红黑树是一种特殊的平衡二叉树，具有以下特点：结点非红即黑，根结点是黑色，所有叶子都是黑色。（叶子是空节点）每个红色节点的两个孩子都是黑色的（从每个叶子到根的所有路径上不能有两个连续的红色节点）从任何节点到它的每个叶子的所有路径都包含相同数量的黑色节点.所以红黑树的时间复杂度为：O(lgn)。jdk1.8：数组+链表+红黑树HashMap底层首先是一个数组，元素中存储的数组索引值由元素的哈希值（key中key的哈希值）决定key-value），这可能会出现一种特殊情况——不同的键具有相同的哈希值。在这种情况下，引入链表。如果键的哈希值相同，则在数组的索引中存储一个链表。这个链表包含了所有key的hash值相同的value值，解决了hash的问题。冲突问题。但是如果出现大量hash值相同的特例，导致链表很长，会严重影响HashMap的性能，因为链表的查询效率需要遍历所有节点。于是在jdk1.8中引入了红黑树。当链表长度大于8且HashMap的容量大于64时，链表将转为红黑树。//jdk1.8//HashMap#putVal//binCount是链表的长度计数器。当链表长度大于等于8时，执行树方法//TREEIFY_THRESHOLD=8if(binCount>=TREEIFY_THRESHOLD-1)treeifyBin(tab,hash);//HashMap#treeifyBinfinalvoidtreeifyBin(Node[]tab,inthash){intn,index;Nodee;//MIN_TREEIFY_CAPACITY=64//如果HashMap的大小小于64，只扩容，不树if(tab==null||(n=tab.length)hd=null,tl=null;do{TreeNodep=replacementTreeNode(e,null);if(tl==null)hd=p;else{p.prev=tl;tl.next=p;}tl=p;}while((ee=e.next)!=null);if((tab[index]=hd)!=null)hd.treeify(tab);}}loadfactor为什么是所谓的0.75的loadfactor也称为扩展因子或负载因子，用于判断容量扩展。假设加载因子为0.5，HashMap初始容量为16，当HashMap中有16*0.5=8个元素时，HashMap会扩容。HashMap中的负载因子为0.75，兼顾了性能和容量的平衡。从loadfactor的定义我们可以知道它的取值范围是(0,1)。如果loadfactor太小，扩容门槛低，扩容频繁。虽然这样可以让元素存储的更多sparsely，可以有效避免hash冲突的发生，运行性能高，但是会占用较多的空间，如果加载因子过大，扩容门槛高，扩容不频繁，虽然占用空间减少，这会导致密集的元素存储和哈希冲突的概率大大增加，导致存储元素的数据结构更加复杂（用于解决哈希冲突），最终导致运行性能降低。另一个因素是提高扩展效率。因为HashMap的容量（size属性，构造函数中的initialCapacity变量）有一个要求：必须是2的幂。所以选择0.75作为加载因子可以保证它和容量的乘积是一个整数。//构造函数publicHashMap(ininitialCapacity,floatloadFactor){//……this.loadFactor=loadFactor;//加载因子this.threshold=tableSizeFor(initialCapacity);}/***Returnapoweroftwosizeforthegiventargetcapacity。2*MAXIMUM_CAPACITY=1<<30*/staticfinalinttableSizeFor(intcap){intn=cap-1;n|=n>>>1;n|=n>>>2;n|=n>>>4的返回功率;n|=n>>>8;n|=n>>>16;return(n<0)?1:(n>=MAXIMUM_CAPACITY)?MAXIMUM_CAPACITY:n+1;}为什么HashMap的容量是第n个2的幂？HashMap默认初始容量为16，每次扩容都是原来容量的两倍。这里的16和2次保证了HashMap的容量是2的n次方，那么这样设计的原因是什么呢？理由一：AND运算高效AND运算&是根据二进制值，同时为1结果为1，否则为0。如1&1=1、1&0=0、0&0=0。使用AND运算的原因是AND运算对于计算机来说非常高效。理由二：有利于元素的全哈希，减少哈希冲突。在向HashMap添加元素的putVal函数中，有这样一段代码：//n是容量，hash是元素的hash值if((p=tab[i=(n-1)&hash])==null)tab[i]=newNode(hash,key,value,null);在中添加元素位置时，会通过i=(n-1)&hash计算HashMap中的元素。当HashMap的容量为2的n次方时，其二进制值为100000...(n0s)，所以n-1的值为011111...(n1s)，所以(n-1)&的哈希值可以完全哈希。比如假设容量为16，现在有四种哈希值1111、1110、1011、1001要相加，它们的哈希值和n-1（15二进制=01111）1111、1110、1110和1011是不一样的。并且假设容量不是2的n次方，假设是10，那么它和上面四个哈希值的AND运算结果分别是：0101,0100,0001,0001。可以看出后者两个值发生了碰撞，可见非2的n次方会增加哈希碰撞的概率。因此，将HashMap的容量设置为2的n次方，有利于元素的全散列。参考：为什么HashMap的初始容量是2的n次方，为什么扩容是2倍的形式？在多线程环境下，可能会产生循环链表，从而导致死循环。在jdk1.8中改用了尾部插入的方式，避免了死循环。
