file:///C:/Users/禽兽/AppData/Roaming/feiq/RichOle/95941822.bmp一，JDK1.8中的涉及到的数据结构1，位桶数组transient Node[] table;//存储（位桶）的数组  2，数组元素Node实现了Entry接口1//Node是单向链表，它实现了Map.Entry接口  2staticclassNode implementsMap.Entry{  3finalinthash;  4finalK key;  5V value;  6Nodenext;  7//构造函数Hash值 键 值 下一个节点  8Node(inthash, K key, V value, Nodenext) {  9this.hash =hash;  10this.key =key;  11this.value =value;  12this.next =next;  13}  1415publicfinalK getKey()        { returnkey; }  16publicfinalV getValue()      { returnvalue; }  17publicfinalString toString() { returnkey + = +value; }  1819publicfinalinthashCode() {  20returnObjects.hashCode(key) ^Objects.hashCode(value);  21}  2223publicfinalV setValue(V newValue) {  24V oldValue =value;  25value =newValue;  26returnoldValue;  27}  28//判断两个node是否相等,若key和value都相等，返回true。可以与自身比较为true  29publicfinalbooleanequals(Object o) {  30if(o == this)  31returntrue;  32if(o instanceofMap.Entry) {  33Map.Entry e = (Map.Entry)o;  34if(Objects.equals(key, e.getKey()) &&  35Objects.equals(value, e.getValue()))  36returntrue;  37}  38returnfalse;  39}  3，红黑树1//红黑树  2staticfinalclassTreeNode extendsLinkedHashMap.Entry{  3TreeNode parent;  //父节点  4TreeNode left; //左子树  5TreeNode right;//右子树  6TreeNode prev;    //needed to unlink next upon deletion  7booleanred;    //颜色属性  8TreeNode(inthash, K key, V val, Nodenext) {  9super(hash, key, val, next);  10}  1112//返回当前节点的根节点  13finalTreeNoderoot() {  14for(TreeNode r = this, p;;) {  15if((p = r.parent) == null)  16returnr;  17r =p;  18}  19}  二，源码中的数据域加载因子（默认0.75）：为什么需要使用加载因子，为什么需要扩容呢？因为如果填充比很大，说明利用的空间很多，如果一直不进行扩容的话，链表就会越来越长，这样查找的效率很低，因为链表的长度很大（当然最新版本使用了红黑树后会改进很多），扩容之后，将原来链表数组的每一个链表分成奇偶两个子链表分别挂在新链表数组的散列位置，这样就减少了每个链表的长度，增加查找效率HashMap本来是以空间换时间，所以填充比没必要太大。但是填充比太小又会导致空间浪费。如果关注内存，填充比可以稍大，如果主要关注查找性能，填充比可以稍小。1publicclassHashMap extendsAbstractMap implementsMap, Cloneable, Serializable {  2privatestaticfinallongserialVersionUID = 362498820763181265L;  3staticfinalintDEFAULT_INITIAL_CAPACITY = 1 << 4; //aka 16  4staticfinalintMAXIMUM_CAPACITY = 1 << 30;//最大容量  5staticfinalfloatDEFAULT_LOAD_FACTOR = 0.75f;//填充比  6//当add一个元素到某个位桶，其链表长度达到8时将链表转换为红黑树  7staticfinalintTREEIFY_THRESHOLD = 8;  8staticfinalintUNTREEIFY_THRESHOLD = 6;  9staticfinalintMIN_TREEIFY_CAPACITY = 64;  10transientNode[] table;//存储元素的数组  11transientSet<map.entry>entrySet;  12transientintsize;//存放元素的个数  13transientintmodCount;//被修改的次数fast-fail机制  14intthreshold;//临界值 当实际大小(容量*填充比)超过临界值时，会进行扩容   15finalfloatloadFactor;//填充比（......后面略）  三，HashMap的构造函数HashMap的构造方法有4种，主要涉及到的参数有，指定初始容量，指定填充比和用来初始化的Map1//构造函数1  2publicHashMap(intinitialCapacity, floatloadFactor) {  3//指定的初始容量非负  4if(initialCapacity < 0)  5thrownewIllegalArgumentException(Illegal initial capacity:  +  6initialCapacity);  7//如果指定的初始容量大于最大容量,置为最大容量  8if(initialCapacity >MAXIMUM_CAPACITY)  9initialCapacity =MAXIMUM_CAPACITY;  10//填充比为正  11if(loadFactor <= 0 ||Float.isNaN(loadFactor))  12thrownewIllegalArgumentException(Illegal load factor:  +  13loadFactor);  14this.loadFactor =loadFactor;  15this.threshold = tableSizeFor(initialCapacity);//新的扩容临界值  16}  1718//构造函数2  19publicHashMap(intinitialCapacity) {  20this(initialCapacity, DEFAULT_LOAD_FACTOR);  21}  2223//构造函数3  24publicHashMap() {  25this.loadFactor = DEFAULT_LOAD_FACTOR; //all other fields defaulted  26}  2728//构造函数4用m的元素初始化散列映射  29publicHashMap(Mapm) {  30this.loadFactor =DEFAULT_LOAD_FACTOR;  31putMapEntries(m, false);  32}  四，HashMap的存取机制1，HashMap如何getValue值，看源码1publicV get(Object key) {  2Nodee;  3return(e = getNode(hash(key), key)) == null? null: e.value;  4}  5/**6* Implements Map.get and related methods 7* 8* @paramhash hash for key 9* @paramkey the key 10* @returnthe node, or null if none 11*/12finalNode getNode(inthash, Object key) {  13Node[] tab;//Entry对象数组  14Node first,e; //在tab数组中经过散列的第一个位置  15intn;  16K k;  17/*找到插入的第一个Node，方法是hash值和n-1相与，tab[(n - 1) & hash]*/18//也就是说在一条链上的hash值相同的  19if((tab = table) != null&& (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {  20/*检查第一个Node是不是要找的Node*/21if(first.hash == hash && //always check first node  22((k = first.key) == key || (key != null&& key.equals(k))))//判断条件是hash值要相同，key值要相同  23returnfirst;  24/*检查first后面的node*/25if((e = first.next) != null) {  26if(first instanceofTreeNode)  27return((TreeNode)first).getTreeNode(hash, key);  28/*遍历后面的链表，找到key值和hash值都相同的Node*/29do{  30if(e.hash == hash &&  31((k = e.key) == key || (key != null&&key.equals(k))))  32returne;  33} while((e = e.next) != null);  34}  35}  36returnnull;  37}  get(key)方法时获取key的hash值，计算hash&(n-1)得到在链表数组中的位置first=tab[hash&(n-1)],先判断first的key是否与参数key相等，不等就遍历后面的链表找到相同的key值返回对应的Value值即可2，HashMap如何put(key，value);看源码1publicV put(K key, V value) {  2returnputVal(hash(key), key, value, false, true);  3}  4/**5* Implements Map.put and related methods 6* 7* @paramhash hash for key 8* @paramkey the key 9* @paramvalue the value to put 10* @paramonlyIfAbsent if true, don't change existing value 11* @paramevict if false, the table is in creation mode. 12* @returnprevious value, or null if none 13*/14finalV putVal(inthash, K key, V value, booleanonlyIfAbsent,  15booleanevict) {  16Node[] tab;   17Nodep;   18intn, i;  19if((tab = table) == null|| (n = tab.length) == 0)  20n = (tab =resize()).length;  21/*如果table的在（n-1）&hash的值是空，就新建一个节点插入在该位置*/22if((p = tab[i = (n - 1) & hash]) == null)  23tab = newNode(hash, key, value, null);  24/*表示有冲突,开始处理冲突*/25else{  26Nodee;   27K k;  28/*检查第一个Node，p是不是要找的值*/29if(p.hash == hash &&((k = p.key) == key || (key != null&&key.equals(k))))  30e =p;  31elseif(p instanceofTreeNode)  32e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);  33else{  34for(intbinCount = 0; ; ++binCount) {  35/*指针为空就挂在后面*/36if((e = p.next) == null) {  37p.next = newNode(hash, key, value, null);  38//如果冲突的节点数已经达到8个，看是否需要改变冲突节点的存储结构，　　　　　　　　　　　　　  39//treeifyBin首先判断当前hashMap的长度，如果不足64，只进行  40//resize，扩容table，如果达到64，那么将冲突的存储结构为红黑树  41if(binCount >= TREEIFY_THRESHOLD - 1) //-1 for 1st  42treeifyBin(tab, hash);  43break;  44}  45/*如果有相同的key值就结束遍历*/46if(e.hash == hash &&((k = e.key) == key || (key != null&&key.equals(k))))  47break;  48p =e;  49}  50}  51/*就是链表上有相同的key值*/52if(e != null) { //existing mapping for key，就是key的Value存在  53V oldValue =e.value;  54if(!onlyIfAbsent || oldValue == null)  55e.value =value;  56afterNodeAccess(e);  57returnoldValue;//返回存在的Value值  58}  59}  60++modCount;  61/*如果当前大小大于门限，门限原本是初始容量*0.75*/62if(++size >threshold)  63resize();//扩容两倍  64afterNodeInsertion(evict);  65returnnull;  66}  下面简单说下添加键值对put(key,value)的过程：1，判断键值对数组tab[]是否为空或为null，否则以默认大小resize()；2，根据键值key计算hash值得到插入的数组索引i，如果tab==null，直接新建节点添加，否则转入33，判断当前数组中处理hash冲突的方式为链表还是红黑树(check第一个节点类型即可),分别处理五，HasMap的扩容机制resize();构造hash表时，如果不指明初始大小，默认大小为16（即Node数组大小16），如果Node[]数组中的元素达到（填充比*Node.length）重新调整HashMap大小 变为原来2倍大小,扩容很耗时1/**2* Initializes or doubles table size.  If null, allocates in 3* accord with initial capacity target held in field threshold. 4* Otherwise, because we are using power-of-two expansion, the 5* elements from each bin must either stay at same index, or move 6* with a power of two offset in the new table. 7* 8* @returnthe table 9*/10finalNode[] resize() {  11Node[] oldTab =table;  12intoldCap = (oldTab == null) ? 0: oldTab.length;  13intoldThr =threshold;  14intnewCap, newThr = 0;  1516/*如果旧表的长度不是空*/17if(oldCap > 0) {  18if(oldCap >=MAXIMUM_CAPACITY) {  19threshold =Integer.MAX_VALUE;  20returnoldTab;  21}  22/*把新表的长度设置为旧表长度的两倍，newCap=2*oldCap*/23elseif((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&  24oldCap >=DEFAULT_INITIAL_CAPACITY)  25/*把新表的门限设置为旧表门限的两倍，newThr=oldThr*2*/26newThr = oldThr << 1; //double threshold  27}  28/*如果旧表的长度的是0，就是说第一次初始化表*/29elseif(oldThr > 0) //initial capacity was placed in threshold  30newCap =oldThr;  31else{               //zero initial threshold signifies using defaults  32newCap =DEFAULT_INITIAL_CAPACITY;  33newThr = (int)(DEFAULT_LOAD_FACTOR *DEFAULT_INITIAL_CAPACITY);  34}  35363738if(newThr == 0) {  39floatft = (float)newCap * loadFactor;//新表长度乘以加载因子  40newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?  41(int)ft : Integer.MAX_VALUE);  42}  43threshold =newThr;  44@SuppressWarnings({"rawtypes","unchecked"})  45/*下面开始构造新表，初始化表中的数据*/46Node[] newTab = (Node[])newNode[newCap];  47table = newTab;//把新表赋值给table  48if(oldTab != null) {//原表不是空要把原表中数据移动到新表中      49/*遍历原来的旧表*/50for(intj = 0; j < oldCap; ++j) {  51Nodee;  52if((e = oldTab[j]) != null) {  53oldTab[j] = null;  54if(e.next == null)//说明这个node没有链表直接放在新表的e.hash & (newCap - 1)位置  55newTab[e.hash & (newCap - 1)] =e;  56elseif(e instanceofTreeNode)  57((TreeNode)e).split(this, newTab, j, oldCap);  58/*如果e后边有链表,到这里表示e后面带着个单链表，需要遍历单链表，将每个结点重*/59else{ //preserve order保证顺序  60////新计算在新表的位置，并进行搬运  61Node loHead = null, loTail = null;  62Node hiHead = null, hiTail = null;  63Nodenext;  6465do{  66next = e.next;//记录下一个结点  67//新表是旧表的两倍容量，实例上就把单链表拆分为两队，  68//e.hash&oldCap为偶数一队，e.hash&oldCap为奇数一对  69if((e.hash & oldCap) == 0) {  70if(loTail == null)  71loHead =e;  72else73loTail.next =e;  74loTail =e;  75}  76else{  77if(hiTail == null)  78hiHead =e;  79else80hiTail.next =e;  81hiTail =e;  82}  83} while((e = next) != null);  8485if(loTail != null) {//lo队不为null，放在新表原位置  86loTail.next = null;  87newTab[j] =loHead;  88}  89if(hiTail != null) {//hi队不为null，放在新表j+oldCap位置  90hiTail.next = null;  91newTab[j + oldCap] =hiHead;  92}  93}  94}  95}  96}  97returnnewTab;  98}  六，JDK1.8使用红黑树的改进在Java jdk8中对HashMap的源码进行了优化，在jdk7中，HashMap处理“碰撞”的时候，都是采用链表来存储，当碰撞的结点很多时，查询时间是O（n）。在jdk8中，HashMap处理“碰撞”增加了红黑树这种数据结构，当碰撞结点较少时，采用链表存储，当较大时（>8个），采用红黑树（特点是查询时间是O（logn））存储（有一个阀值控制，大于阀值(8个)，将链表存储转换成红黑树存储）问题分析：你可能还知道哈希碰撞会对hashMap的性能带来灾难性的影响。如果多个hashCode()的值落到同一个桶内的时候，这些值是存储到一个链表中的。最坏的情况下，所有的key都映射到同一个桶中，这样hashmap就退化成了一个链表——查找时间从O(1)到O(n)。随着HashMap的大小的增长，get()方法的开销也越来越大。由于所有的记录都在同一个桶里的超长链表内，平均查询一条记录就需要遍历一半的列表。JDK1.8HashMap的红黑树是这样解决的：如果某个桶中的记录过大的话（当前是TREEIFY_THRESHOLD = 8），HashMap会动态的使用一个专门的treemap实现来替换掉它。这样做的结果会更好，是O(logn)，而不是糟糕的O(n)。它是如何工作的？前面产生冲突的那些KEY对应的记录只是简单的追加到一个链表后面，这些记录只能通过遍历来进行查找。但是超过这个阈值后HashMap开始将列表升级成一个二叉树，使用哈希值作为树的分支变量，如果两个哈希值不等，但指向同一个桶的话，较大的那个会插入到右子树里。如果哈希值相等，HashMap希望key值最好是实现了Comparable接口的，这样它可以按照顺序来进行插入。这对HashMap的key来说并不是必须的，不过如果实现了当然最好。如果没有实现这个接口，在出现严重的哈希碰撞的时候，你就并别指望能获得性能提升了。大家可以相互学习，我们都是热爱编程的IT少年，大家一起努力，让我们的IT梦飞得更高吧!!!</map.entry

神仙排版？