企业官网建设流程全解析

章节目录

1.HashMap的底层数据结构

• 在JDK7中HashMap是以[数组+链表]的形式组成的；
• JDK8以后新增了[红黑树]的组成结构；
• 当链表长度大于8并且hash桶的容量大于64时，链表结构会转成红黑树结构。

HashMap 中数组的每一个元素又称为哈希桶，也就是 key-value 这样的实例。在Java7中叫 Entry，Java8中叫 Node。

它的源码为

staticclassNode<K,V>implementsMap.Entry<K,V>{finalinthash;finalKkey;Vvalue;Node<K,V>next;...}

• 从这里我们可以看出来每个哈希桶中包含了4个字段：hash，key，value，next；
• 其中next表示表示链表的下一个节点。

[!NOTE]

• JDK8之所以添加红黑树是因为一旦链表过长，会严重影响HashMap的性能；
• 而红黑树具有快速增删改查的特点，这样就可以有效的解决链表过长是操作比较慢的问题。

2.HashMap的重要方法

查询方法（get方法）

publicVget(Objectkey){Node<K,V>e;// 对 key 进行哈希操作return(e=getNode(hash(key),key))==null?null:e.value;}finalNode<K,V>getNode(inthash,Objectkey){Node<K,V>[]tab;Node<K,V>first,e;intn;Kk;// 非空判断if((tab=table)!=null&&(n=tab.length)>0&&(first=tab[(n-1)&hash])!=null){// 判断第一个元素是否是要查询的元素// always check first nodeif(first.hash==hash&&((k=first.key)==key||(key!=null&&key.equals(k))))returnfirst;// 下一个节点非空判断if((e=first.next)!=null){// 如果第一节点是树结构，则使用 getTreeNode 直接获取相应的数据if(firstinstanceofTreeNode)return((TreeNode<K,V>)first).getTreeNode(hash,key);do{// 非树结构，循环节点判断// hash 相等并且 key 相同，则返回此节点if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))returne;}while((e=e.next)!=null);}}returnnull;}

• 当hash冲突的时候，我们不仅需要判断hash值，还需要通过判断key值是否相等；
• 才可以确定次元素是不是我们想要的元素。

新增（put方法）

publicVput(Kkey,Vvalue){// 对 key 进行哈希操作returnputVal(hash(key),key,value,false,true);}finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){Node<K,V>[]tab;Node<K,V>p;intn,i;// 哈希表为空则创建表if((tab=table)==null||(n=tab.length)==0)n=(tab=resize()).length;// 根据 key 的哈希值计算出要插入的数组索引 iif((p=tab[i=(n-1)&hash])==null)// 如果 table[i] 等于 null，则直接插入tab[i]=newNode(hash,key,value,null);else{Node<K,V>e;Kk;// 如果 key 已经存在了，直接覆盖 valueif(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k))))e=p;// 如果 key 不存在，判断是否为红黑树elseif(pinstanceofTreeNode)// 红黑树直接插入键值对e=((TreeNode<K,V>)p).putTreeVal(this,tab,hash,key,value);else{// 为链表结构，循环准备插入for(intbinCount=0;;++binCount){// 下一个元素为空时if((e=p.next)==null){p.next=newNode(hash,key,value,null);// 转换为红黑树进行处理if(binCount>=TREEIFY_THRESHOLD-1)// -1 for 1sttreeifyBin(tab,hash);break;}// key 已经存在直接覆盖 valueif(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))break;p=e;}}// existing mapping for keyif(e!=null){VoldValue=e.value;if(!onlyIfAbsent||oldValue==null)e.value=value;afterNodeAccess(e);returnoldValue;}}++modCount;// 超过最大容量，扩容if(++size>threshold)resize();afterNodeInsertion(evict);returnnull;}

扩容（resize方法）

finalNode<K,V>[]resize(){// 扩容前的数组Node<K,V>[]oldTab=table;// 扩容前的数组的大小和阈值intoldCap=(oldTab==null)?0:oldTab.length;intoldThr=threshold;// 预定义新数组的大小和阈值intnewCap,newThr=0;if(oldCap>0){// 超过最大值就不再扩容了if(oldCap>=MAXIMUM_CAPACITY){threshold=Integer.MAX_VALUE;returnoldTab;}// 扩大容量为当前容量的两倍，但不能超过 MAXIMUM_CAPACITYelseif((newCap=oldCap<<1)<MAXIMUM_CAPACITY&&oldCap>=DEFAULT_INITIAL_CAPACITY)newThr=oldThr<<1;// double threshold}// 当前数组没有数据，使用初始化的值elseif(oldThr>0)// initial capacity was placed in thresholdnewCap=oldThr;else{// zero initial threshold signifies using defaults// 如果初始化的值为 0，则使用默认的初始化容量newCap=DEFAULT_INITIAL_CAPACITY;newThr=(int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);}// 如果新的容量等于 0if(newThr==0){floatft=(float)newCap*loadFactor;newThr=(newCap<MAXIMUM_CAPACITY&&ft<(float)MAXIMUM_CAPACITY?(int)ft:Integer.MAX_VALUE);}threshold=newThr;@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[]newTab=(Node<K,V>[])newNode[newCap];// 开始扩容，将新的容量赋值给 tabletable=newTab;// 原数据不为空，将原数据复制到新 table 中if(oldTab!=null){// 根据容量循环数组，复制非空元素到新 tablefor(intj=0;j<oldCap;++j){Node<K,V>e;if((e=oldTab[j])!=null){oldTab[j]=null;// 如果链表只有一个，则进行直接赋值if(e.next==null)newTab[e.hash&(newCap-1)]=e;elseif(einstanceofTreeNode)// 红黑树相关的操作((TreeNode<K,V>)e).split(this,newTab,j,oldCap);else{// preserve order// 链表复制，JDK 1.8 扩容优化部分// 如果节点不为空，且为单链表，则将原数组中单链表元素进行拆分Node<K,V>loHead=null,loTail=null;//保存在原有索引的链表Node<K,V>hiHead=null,hiTail=null;//保存在新索引的链表Node<K,V>next;do{next=e.next;// 哈希值和原数组长度进行 & 操作，为 0 则在原数组的索引位置if((e.hash&oldCap)==0){if(loTail==null)loHead=e;elseloTail.next=e;loTail=e;}// 原索引 + oldCapelse{if(hiTail==null)hiHead=e;elsehiTail.next=e;hiTail=e;}}while((e=next)!=null);// 将原索引放到哈希桶中if(loTail!=null){loTail.next=null;newTab[j]=loHead;}// 将原索引 + oldCap 放到哈希桶中if(hiTail!=null){hiTail.next=null;newTab[j+oldCap]=hiHead;}}}}}returnnewTab;}

扩容主要分为2步：

• 扩容：创建一个新的Entry空数组，长度是原数组的2倍；

• 位运算：原来的元素哈希值和原数组长度进行&运输。

• JDK8在扩容时没有像JDK7那样重新计算每个元素的哈希值；

• 而是通过高位运算（e.hash & oldCap）来确定元素是否需要移动；

• 假如key1的信息为：key1.hash=10、二进制：0000 1010；oldCap = 16、二进制0001 0000；

• 使用e.hash & oldCap得到的结果，高一位位0，当结果为0时表示元素在扩容时位置不会发生任何变化；

• 当高1位为1是，表示元素在扩容时位置发生了变化，新的下标位置等于原下标位置+原数组长度。

HashMap有哪些属性？

// HashMap 初始化长度staticfinalintDEFAULT_INITIAL_CAPACITY=1<<4;// aka 16// HashMap 最大长度staticfinalintMAXIMUM_CAPACITY=1<<30;// 1073741824// 默认的加载因子 (扩容因子)staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;// 当链表长度大于此值且数组长度大于 64 时，会从链表转成红黑树staticfinalintTREEIFY_THRESHOLD=8;// 转换链表的临界值，当元素小于此值时，会将红黑树结构转换成链表结构staticfinalintUNTREEIFY_THRESHOLD=6;// 最小树容量staticfinalintMIN_TREEIFY_CAPACITY=64;

为什么HashMap的初始化长度是16？（必须是2的幂次方）

• 我们观察前面的源码发现HashMap初始化长度用的是1<<4，而不是直接写16；
• 这是因为位运算的方便，位运算比运算算数计算的效率高很多；
• 之所以选择16，是为了服务Key映射到index的算法。

如何实现一个尽量均匀分布的Hash函数？从而尖山HashMap碰撞？

• 通过Key的HashCode值来做位运算；
• HashCode（Key） & （Length- 1）；

[!NOTE]

也就是：hash算法最终得到的index结果，取决于hashcode值的最后几位。

[!NOTE]

• 可以把长度指定为10以及其他非2次幂的数字，做位预算；
• 发现index出现相同的概率大大升高；
• 而长度为16或者其他2次幂，length-1的值是所有二进制位全为1；
• 这种情况下，index的结果等同于hashcode后几位的值；
• 只要输入的hashCode本身分布均匀，hash算法的结果就是均匀的。

所以HashMap的默认长度为16，是为了降低hash碰撞的机率。

5.为什么树化是8，退树化是6？

• 红黑树平均查找长度Log(n)，长度为8时，查找长度为3；
• 而链表平均查找长度为N/2，也就是8/2；
• 查找长度链表大于树，转换为树，效率更高；
• 当为6时，树2.6、链表3；链表>树；
• 这是应该来说还是树化合理，但是树化需要时间，为了这点效率牺牲时间是不划算的 🙅。

6.什么是加载因子？加载因子为什么是0.75？

• 前面我们讲到了扩容机制。那么什么时候进行扩容？
• 这取决于原数组长度和加载因子两个因素。

[!NOTE]

• 加载因子也叫做扩容因子或者负载因子；
• 用来判断什么时候进行扩容，假如加载因子为0.5，HashMap的初始化容量为16；
• 那当HashMap中有16*0.5=8个元素时，HashMap就会扩容。

现在我们来分析为什么加载因子一定为0.75？

• 为了提升扩容向量，HashMap的容量有一个固定的要求，那就是一定为2的幂；
• 所以，如果负载因子为0.75，那么和容量乘积就可以是一个整数；
• 当加载因子较大时，扩容门槛变高，扩容频率变低，占用空间小；
• 但是此时发生Hash冲突可能性变高，因此需要更复杂的数据结构存储元素，对元素操作时间会增加，运行效率变低；
• 当加载因子较小时，扩容门槛变低，占用空间大；
• 此时元素存储比较稀疏，发生Hash冲突的可能性小，因此操作性会比较高；
• 所以我们在0.5和1之间去了一个平均数为加载因子🌟。

7.HashMap是线程安全的吗？

• 不是，get和put方法都没有上锁；
• 多线程操作无法保障：此时put的值，片刻后get还是相同的值，会造成线程安全问题；
• 但是有个HashTable是线程安全的，但是加锁的粒度太大；
• 并发度降低，最多同时允许一个线程访问，性能不高，我们一般使用currentHashMap。

7.为什么重写equals方法的时候，需要重新hashCode方法呢？

[!IMPORTANT]

Java中，所以对象都是集成于Object类，Object类中有两个方法equals，hashCode，这两个方法都是用来比较两个对象是否相等的。

publicbooleanequals(Objectobj){return(this==obj);}

• 在未重新equals方法，其就是==；
• 对于值对象，==比较的是两个对象的值；
• 对于引用对象，==比较的是两个对象的地址。

现在我们来分析为什么重写equals时候需要重写hashCode方法？

• 前面我们分析到put方法时，HashMap是通过key的hashcode去寻找地址index的，如果index一样就会形成链表；
• 在使用get方法的时候，当哈希冲突时我们不仅需要判断hash值，还需要通过判断key值是否相等，才能确认此元素是不是我们想要的元素；
• 我们去get首先是找到hash值一样的，那怎么知道你想要的是哪个对象呢？
• 就是利用equals方法，如果重新hashCode方法，不写equals方法，当发生hash冲突，hashCode一样时，就不知道去哪个对象了。

9.HashMap死循环分析

voidtransfer(Entry[]newTable,booleanrehash){intnewCapacity=newTable.length;for(Entry<K,V>e:table){while(null!=e){Entry<K,V>next=e.next;// 此处加断点if(rehash){e.hash=null==e.key?0:hash(e.key);}inti=indexFor(e.hash,newCapacity);e.next=newTable[i];newTable[i]=e;e=next;}}}

• 上面是JDK7链表头插法，假设HashMap默认大小为2，原本HashMap中没有一个元素，3个线程添加3个元素；
• 加入3个元素hash冲突，放到同一个链表，就是key1，key2，key3的顺序；

• 此时HashMap进行扩容，就可能变为key1和key2还是同一个位置，这时形成链表；
• 如果key2比key1后插入，根据头插法就变为key2，key1；

• 链表反转：最终3个线程调整完毕，会出现死循环，这个时候get（key1）就会出现infinite Loop异常。

在JDK8这个问题得到了改善，变成了尾部正序插入，在扩容时会保持链表元素原本的顺序，就不会出现链表成环问题。