HashMap详解
什么是HashMap容器
什么是HashMap容器
【1】HashMap是使用频率最高的用于映射(键值对)处理的数据类型。随着JDK（Java Developmet Kit）版本的更新，JDK1.8对HashMap底层的实现进行了优化，例如引入红黑树的数据结构和扩容的优化等。
【2】jdk1.8 之前 HashMap 由 数组 + 链表 组成，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突（两个对象调用的 hashCode 方法计算的哈希值经哈希函数算出来的地址被别的元素占用）而存在的（“拉链法”解决冲突）。jdk1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（或者红黑树的边界值，默认为 8 ）并且当前数组的长度大于 64 时，此时此索引位置上的所有数据改为使用红黑树存储。
【3】HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
HashMap的疑难问题
【1】为什么转成树结构的阈值是8，而由树转回为链表结构的阈值是6？
在源码中有这么一段注释：
Implementationnotes.实现注意事项Thismap usually actsasa binned(bucketed)hash table,butwhenbinsgettoolarge,they are transformedintobins ofTreeNodes,each structured similarly to thoseinjava.util.TreeMap.Mostmethodstrytousenormal bins,but relay toTreeNodemethodswhenapplicable(simplybycheckinginstanceofa node).BinsofTreeNodesmay be traversedandused like any others,but additionally support faster lookupwhenoverpopulated.However,since the vast majority of binsinnormalusearenotoverpopulated,checkingforexistence of tree bins may be delayedinthe course of table methods.这个映射通常充当一个分箱(桶)哈希表，但是当容器太大时，它们被转换为TreeNodes的容器，每个容器的结构类似于java.util.TreeMap中的容器。大多数方法尝试使用普通的bin，但在适用的情况下中继到TreeNode方法(简单地通过检查节点的实例)。TreeNodes的容器可以像其他容器一样被遍历和使用，但是在过度填充时还支持更快的查找。然而，由于正常使用的绝大多数容器都没有过度填充，所以在表方法的过程中可能会延迟检查树容器的存在。....BecauseTreeNodesare about twice the size of regular nodes,weusethem onlywhenbins contain enough nodes to warrantuse(see TREEIFY_THRESHOLD).Andwhenthey become too small(due to removalorresizing)they are converted back to plain bins.Inusageswithwell-distributeduserhashCodes,tree bins are rarely used.Ideally,under random hashCodes,the frequency of nodesinbins follows aPoissondistribution(http://en.wikipedia.org/wiki/Poisson_distribution)witha parameter of about0.5on averageforthedefaultresizing threshold of0.75,althoughwitha large variance because of resizing granularity.Ignoringvariance,the expected occurrences of list size k are(exp(-0.5)*pow(0.5,k)/factorial(k)).Thefirst values are:因为TreeNodes大约是常规节点的两倍大，所以我们只在容器包含足够的节点以保证使用时才使用它们(参见TREEIFY_THRESHOLD)。当它们变得太小(由于删除或调整大小)时，它们会被转换回普通的容器。在分布良好的用户hashCodes的用法中，很少使用树容器。理想情况下，在随机hashCodes下，容器中节点的频率遵循泊松分布(http://en.wikipedia.org/wiki/Poisson_distribution)，对于默认的调整大小阈值0.75，该分布的参数平均约为0.5，尽管由于调整大小粒度的差异很大。忽略方差，列表大小k的期望出现次数为(exp(-0.5)*pow(0.5,k)/factorial(k))。第一个值是:0:0.606530661:0.303265332:0.075816333:0.012636064:0.001579525:0.000157956:0.000013167:0.000000948:0.00000006千万分之6more:less than1inten million如果是更多的话，会低于千万分之一...
【2】为什么HashMap要保证数组长度是2的倍数呢？
主要原因是在于为了扩容时候的数据迁移，因为在源码中，HashMap是一个一个槽位的将数据迁移。如果限制了是2的倍数是怎么样的呢？如4个槽位各有四个数据【1】5，9，13，17【2】6，10，14，18【3】7，11，15，19【4】8，12，16，20扩容成了8个槽位，则数据必然散落在原本的槽位和与之倍数的槽位上【1】9，17【2】10，18【3】11，19【4】12，20【5】5，13【6】6，14【7】7，15【8】8，16这也是为什么扩容的时候只用设置两个链表结构的原因：Node<K,V>loHead=null,loTail=null;Node<K,V>hiHead=null,hiTail=null;反之如果是1.5倍，那么散落在的槽位就不确定了，那么我们就要面对更复杂的情况，必然要按照槽位设置多个链表结构如8个槽位就要8个链表结构，槽位越多，对应的花销更多，所以显得不划算
源码分析HashMap的实现（我这里是拿JDK14的源码展示的）
【0】继承关系
publicclassHashMap<K,V>extendsAbstractMap<K,V>implementsMap<K,V>,Cloneable,Serializable
【1】节点的类型分析
//明显是单链表的节点staticclassNode<K,V>implementsMap.Entry<K,V>{finalinthash;finalK key;V value;Node<K,V>next;Node(inthash,K key,V value,Node<K,V>next){this.hash=hash;this.key=key;this.value=value;this.next=next;}publicfinalK getKey(){returnkey;}publicfinalV getValue(){returnvalue;}publicfinalStringtoString(){returnkey+"="+value;}publicfinalinthashCode(){returnObjects.hashCode(key)^Objects.hashCode(value);}publicfinalV setValue(V newValue){V oldValue=value;value=newValue;returnoldValue;}publicfinalbooleanequals(Objecto){if(o==this)returntrue;if(oinstanceofMap.Entry){Map.Entrye=(Map.Entry)o;if(Objects.equals(key,e.getKey())&&Objects.equals(value,e.getValue()))returntrue;}returnfalse;}}//LinkedHashMap类的Entry结构，将单链表节点包装之后具备双向链表节点的功能staticclassEntry<K,V>extendsHashMap.Node<K,V>{Entry<K,V>before,after;Entry(inthash,K key,V value,Node<K,V>next){super(hash,key,value,next);}}//所以TreeNode其实只是在Node节点上做了包装，所以这个树节点其实是包含了树和双向链表节点两者的功能staticfinalclassTreeNode<K,V>extendsLinkedHashMap.Entry<K,V>{TreeNode<K,V>parent;//red-black tree linksTreeNode<K,V>left;TreeNode<K,V>right;TreeNode<K,V>prev;//needed to unlink next upon deletionbooleanred;TreeNode(inthash,K key,V val,Node<K,V>next){super(hash,key,val,next);}/*** Returns root of tree containing this node.*/finalTreeNode<K,V>root(){for(TreeNode<K,V>r=this,p;;){if((p=r.parent)==null)returnr;r=p;}}...}
【2】属性值
//默认初始容量staticfinalintDEFAULT_INITIAL_CAPACITY=1<<4;//aka 16//默认最大容量staticfinalintMAXIMUM_CAPACITY=1<<30;//即536,870,912//默认加载因子staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;//默认转成树结构的阈值staticfinalintTREEIFY_THRESHOLD=8;//由树转回为链表结构的阈值staticfinalintUNTREEIFY_THRESHOLD=6;//默认转成树时候数组的最小容量staticfinalintMIN_TREEIFY_CAPACITY=64;/*---------------- Fields --------------*///存放数据的集合transientNode<K,V>[]table;//用于迭代器使用的transientSet<Map.Entry<K,V>>entrySet;//数据个数transientintsize;//修改次数记录transientintmodCount;//扩容的阈值，默认是（容量*加载因子）intthreshold;//哈希表的加载因子finalfloatloadFactor;
【3】构造方法
//指定容量和负载因子publicHashMap(intinitialCapacity,floatloadFactor){if(initialCapacity<0)thrownewIllegalArgumentException(...);if(initialCapacity>MAXIMUM_CAPACITY)initialCapacity=MAXIMUM_CAPACITY;if(loadFactor<=0||Float.isNaN(loadFactor))thrownewIllegalArgumentException(...);this.loadFactor=loadFactor;this.threshold=tableSizeFor(initialCapacity);}//这个方法保证得出来的容量是2的N次方，把不足2的N次方的向上取到2的N次方//如3得4，5得8,10得16//设计的巧妙点在于使用了>>>表示无符号右移，也叫逻辑右移与异或方法//减1，是为了让二进制尽可能多的出现1，如1000000，减一后变为0111111。当然如果是1000001，这种会变为1000000【但影响并不大】。//就以1000001为例子，减一后为1000000//其次当右移一位之后再异或就会保证前两位是1，即1000000|100000=1100000//所以第二次直接右移两位再异或，即1100000|11000=1111000//第三次就右移四位，即1111000|111=1111111//所以最后+1，是会变成10000000即128staticfinalinttableSizeFor(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;}//指定容量，默认负载因子为0.75publicHashMap(intinitialCapacity){this(initialCapacity,DEFAULT_LOAD_FACTOR);}//容量使用默认值16，负载因子也为默认值0.75publicHashMap(){this.loadFactor=DEFAULT_LOAD_FACTOR;//all other fields defaulted}//传入有数据的MappublicHashMap(Map
