HashMap(jdk8)特性数组+链表+红黑树key不重复的双列元素key和value可以为空key只能有一个null非安全构造函数无参构造函数使用无参构造，第一次put时，会先检查table中的长度是否>0，如果小于0，则返回检查初始容量阈值是否大于0，如果没有指定threshold的初始容量，会使用默认的初始容量16作为表的长度，默认的loadfactor是0.75。只有在放set的时候，表的长度才会真正扩容，当达到初始容量*负载因子=临界值时，会再次触发下一次扩容。./***使用默认初始容量*(16)和默认加载因子(0.75)构造一个空的HashMap。*/publicHashMap(){this.loadFactor=DEFAULT_LOAD_FACTOR;//其他字段默认}指定初始化容量和加载因子的构造函数使用初始化容量和加载因子的构造函数的初始容量不得小于0。如果初始化容量大于1<<30(1的30次方），直接用1到30的次方作为初始容量的大小。加载因子不能小于等于0或者不是float类型。publicHashMap(intinitialCapacity,floatloadFactor){if(initialCapacity<0)thrownewIllegalArgumentException("非法初始容量："+initialCapacity);如果(initialCapacity>MAXIMUM_CAPACITY)initialCapacity=MAXIMUM_CAPACITY;if(load.FactorFloatisNaN(loadFactor))thrownewIllegalArgumentException("非法加载因子："+loadFactor);this.loadFactor=loadFactor;this.threshold=tableSizeFor(initialCapacity);}单参数初始容量构造函数的初始容量对于30平方不能大于1，不能小于0。默认加载因子为0.75publicHashMap(intinitialCapacity){this(initialCapacity,DEFAULT_LOAD_FACTOR);}使用传入地图集合的构造函数publicHashMap(Mapm){this.loadFactor=DEFAULT_LOAD_FACTOR;//计算容量和负载系数//如果容量超过负载系数，则扩展容量。//然后遍历Map，依次进行put操作putMapEntries(m,false);}扩展机制hashMap默认初始化为16个长度，默认加载因子为0.75。当加入集合的元素长度达到临界值时——集合中元素总数*0.75=临界值，即12。当加入元素且集合长度>12时，一个容量将进行扩展。扩容会是当前容量的两倍，临界值会根据当前的负载因子计算，下次再次触发时，会进行同样的操作。我们在表中存储元素（即hashmap中的数组）时，会先根据key获取对应的hash值（不是hashcode值），这是基于bitwise算法--(h=key.hashCode())^(h>>>16)--得到这个值后，将表中的长度-1进行按位运算，得到一个索引值，如果表中对应索引值的元素表为空，则直接将元素添加到数组中的索引处。如果存在，则比较新元素key的哈希值是否等于已有元素key的哈希值，以及两个元素的key是否相等。如果相等，则元素重复，则进行替换操作。如果不相等，会先判断这个索引处的对象类型是不是红黑树。如果是红黑树，就以红黑树的形式存储。如果是链表，它会依次比较链中的元素是否相等。如果相等，则直接退出。如果它们不相等，则在链的末尾添加一个元素。如果创建后chain的长度>=8，会判断table表的长度是否为64，如果不是64，则先扩表，然后是新元素的Node节点将被添加到链的末尾。如果是64，链会形成红黑树结构。EntitySet了解HashMap集合的内部类EntitySet的分析。Map集合是key-value对存储，经过源码分析，其实每个k-v元素本质上都是一个Node节点对象（HashMap内部类Node），而这个Node对象实现了Entity接口地图界面。其实我们在初始化一个Node节点的时候，newNode(hash,key,value,null)，其实Map接口的内部类Entity保存的是Node对象的引用，因为多态关系，Node对象是Node类型，可以向上转化为Entity，即Entity可以向下转化。为了方便HashMap集合的遍历，HashMap中存储的Node节点的引用会保存在一个EntitySet中。该集合存储的元素类型为Entity，一个Entity对象有K-V，EntitySet>，即：Set>，在EntitySet中，定义的类型为Map.Entity，但实际存储的还是HashMap$Node，因为Node实现了Map。Entity，当HashMap$Node对象存储在entitySet中，方便我们的遍历和取值。HashMap扩展源码/***初始化或加倍表的大小。如果为空，则分配*满足初始容量目标以保持在字段阈值。*否则，因为我们使用的是二次幂扩展，*每个bin中的元素必须保持相同的索引，或者在新表中偏移*为2的幂次方。**@return表格*/finalNode[]resize(){Node[]oldTab=table;intoldCap=(oldTab==null)?0:旧标签长度；intoldThr=阈值；intnewCap,newThr=0;if(oldCap>0){if(oldCap>=MAXIMUM_CAPACITY){threshold=Integer.MAX_VALUE;返回旧标签；}elseif((newCap=oldCap<<1)=DEFAULT_INITIAL_CAPACITY)newThr=oldThr<<1;//双阈值}elseif(oldThr>0)//初始容量被置于阈值newCap=oldThr;else{//零初始阈值表示使用默认值newCap=DEFAULT_INITIAL_CAPACITY;newThr=(int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);}if(newThr==0){floatft=(float)newCap*loadFactor;newThr=(newCap[]newTab=(Node[])newNode[newCap];表=新标签；if(oldTab!=null){for(intj=0;je;如果((e=oldTab[j])!=null){oldTab[j]=null;如果(e.next==null)newTab[e.hash&(newCap-1)]=e;elseif(einstanceofTreeNode)((TreeNode)e).split(this,newTab,j,oldCap);else{//保留顺序NodeloHead=null,loTail=null;NodehiHead=null,hiTail=null;下一个节点；做{next=e.next;if((e.hash&oldCap)==0){if(loTail==null)loHead=e;否则loTail.next=e;loTail=e;}else{if(hiTail==null)hiHead=e;否则hiTail.next=e;高尾=e;}}while((e=next)!=null);if(loTail!=null){loTail.next=null;newTab[j]=loHead;}if(hiTail!=null){hiTail.next=null;newTab[j+oldCap]=hiHead;}}}}}返回新标签；}总结1、HashMap的key不能重复。如果再次放入一个已存在的键，则集合中该键对应的值将被替换为新放入的值。2、HashMap不安全，因为类中没有同步机制3、HashMap高效，因为HashMap底层是数组+单向链表+红黑树。4、HashMap的key和value都可以为空，但是key只能有一个为空。5、当集合中的元素大于临界值时，可以触发HashMap的扩容，扩容加倍。当单链表长度>=8且表不是64时，会加倍。6.HashMap放入时，会将根据key计算出的hash值与当前表的长度-1按位与，计算出表中的索引7.如果根据hash值计算出的索引已经存在于表中表，它会被比较。如果key的hash值不同或者不满足key的equals，就会进行红黑树结构的转换或者单向链表的加法。8、HashMap是无序的，因为底层是以哈希表的形式存储的，所以存储的顺序和取的顺序是不一样的。9、HashMap使用不带参数或指定容量、指定容量、加载因子的构造函数。它只会记录阈值的初始容量长度和HashMap类中loadFactor的加载因子。只有放上去，藏品的容量才会扩大。.HashTable安全性和效率低，key和value都不允许为空。当key存在时，value会被替换为数组+链表解析。Hashtable默认的初始容量是11个长度，Hashtable的初始容量是在put之前完成的。Hashtable默认加载因子为0.75，临界值为threshold=(int)Math.min(initialCapacityloadFactor,MAX_ARRAY_SIZE+1)，也就是说最大加载因子为MAX_ARRAY_SIZE+1，但默认还是initialCapacityloadFactor，初始容量*负载因子。如果进行put操作，在添加元素之前会先判断count>=threshold（当前集合的大小是否大于等于临界值）。如果大于临界值，则按照intnewCapacity=(oldCapacity<<1)+1(oldCapacity=table.length;)，扩容，也就是说每次扩容是`当前容量2+1,临界值仍然按照threshold=(int)Math.min(newCapacityloadFactor,MAX_ARRAY_SIZE+1)进行扩容；每次扩容完成Hashtable都会重新hash。扩容前会先获取当前集合中的所有Node数组，然后table表指向一个新的空数组。数组的大小就是扩展后的容量。之后，重新散列Node数组中所有对象Node的key。执行put操作时，如果当前容量>=临界值，则按照当前容量的2倍+1扩容，扩容前会备份当前表。扩容完成后，会进行一次re-hash操作，执行完毕。之后再对新元素的key的索引值进行hash，然后将这个元素放入新表中。Hashtable构造函数Hashtable的所有构造都基于以下构造函数进行初始化。publicHashtable(intinitialCapacity,floatloadFactor){if(initialCapacity<0)thrownewIllegalArgumentException("非法容量："+initialCapacity);如果(loadFactor<=0||Float.isNaN(loadFactor))thrownewIllegalArgumentException("IllegalLoad:"+loadFactor);如果（初始容量==0）初始容量=1；this.loadFactor=loadFactor;table=newEntry[initialCapacity];threshold=(int)Math.min(initialCapacity*loadFactor,MAX_ARRAY_SIZE+1);}put方法源码publicsynchronizedVput(Kkey,Vvalue){//确保值不为空if(value==null){thrownewNullPointerException();}//确保键不在哈希表中。条目tab[]=table;inthash=key.hashCode();intindex=(hash&0x7FFFFFFF)%tab.length;@SuppressWarnings("unchecked")条目entry=(Entry)tab[index];for(;entry!=null;entry=entry.next){if((entry.hash==hash)&&entry.key.equals(key)){Vold=entry.value;entry.value=值；返老还童；}}addEntry（散列，键，值，索引）；返回空值；}addEntry方法privatevoidaddEntry(inthash,Kkey,Vvalue,intindex){modCount++;条目tab[]=table;if(count>=threshold){//如果超过阈值则重新哈希表rehash();制表符=表格；hash=key.hashCode();index=(hash&0x7FFFFFFF)%tab.length;}//创建新条目。@SuppressWarnings("unchecked")Entrye=(Entry)tab[index];tab[index]=newEntry<>(hash,key,value,e);计数++；}重新哈希方法protectedvoidrehash(){intoldCapacity=table.length;条目[]oldMap=表；//溢出意识代码intnewCapacity=(oldCapacity<<1)+1;if(newCapacity-MAX_ARRAY_SIZE>0){if(oldCapacity==MAX_ARRAY_SIZE)//使用MAX_ARRAY_SIZE桶继续运行return;newCapacity=MAX_ARRAY_SIZE;}条目[]newMap=new条目[newCapacity];模数++；threshold=(int)Math.min(newCapacity*loadFactor,MAX_ARRAY_SIZE+1);表=新地图；for(inti=oldCapacity;i-->0;){for(Entryold=(Entry)oldMap[i];old!=null;){Entrye=旧；旧的=旧的。下一个；intindex=(e.hash&0x7FFFFFFF)%newCapacity;e.next=(Entry)newMap[index];新地图[索引]=e;}}}
