企业官网建设流程全解析

1. HashMap 概述

HashMap 是 Java 集合框架中最重要的数据结构之一，基于哈希表实现，提供了键值对的存储和检索功能。

1.1 核心特性

• 键值对存储：存储 Key-Value 对
• 允许 null：key 和 value 都允许为 null
• 非线程安全：多线程环境下需要外部同步
• 无序性：不保证元素的顺序
• 时间复杂度：理想情况下 O(1) 的查询效率

2. 数据结构演变

2.1 数组 + 链表

JDK 1.7 及之前：

// JDK 1.7 的节点结构staticclassEntry<K,V>implementsMap.Entry<K,V>{finalKkey;Vvalue;Entry<K,V>next;inthash;}

2.2 数组 + 链表/红黑树

JDK 1.8 及之后：

// JDK 1.8 的节点结构staticclassNode<K,V>implementsMap.Entry<K,V>{finalinthash;finalKkey;Vvalue;Node<K,V>next;}// 红黑树节点staticfinalclassTreeNode<K,V>extendsLinkedHashMap.Entry<K,V>{TreeNode<K,V>parent;TreeNode<K,V>left;TreeNode<K,V>right;TreeNode<K,V>prev;booleanred;}

3. 核心源码解析

3.1 关键常量

publicclassHashMap<K,V>extendsAbstractMap<K,V>implementsMap<K,V>,Cloneable,Serializable{// 默认初始容量 - 必须是 2 的幂staticfinalintDEFAULT_INITIAL_CAPACITY=1<<4;// 16// 最大容量staticfinalintMAXIMUM_CAPACITY=1<<30;// 默认负载因子staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;// 链表转红黑树的阈值staticfinalintTREEIFY_THRESHOLD=8;// 红黑树转链表的阈值staticfinalintUNTREEIFY_THRESHOLD=6;// 最小树化容量staticfinalintMIN_TREEIFY_CAPACITY=64;// 存储元素的数组transientNode<K,V>[]table;// 元素个数transientintsize;// 修改次数transientintmodCount;// 扩容阈值 (capacity * loadFactor)intthreshold;// 负载因子finalfloatloadFactor;}

3.2 哈希计算

staticfinalinthash(Objectkey){inth;// key 为 null 时哈希值为 0，否则计算哈希值return(key==null)?0:(h=key.hashCode())^(h>>>16);}// 计算数组下标finalintindexFor(inthash,intlength){// 等价于 hash % length，但效率更高returnhash&(length-1);}

3.3 put 方法实现

publicVput(Kkey,Vvalue){returnputVal(hash(key),key,value,false,true);}finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){Node<K,V>[]tab;Node<K,V>p;intn,i;// 1. 如果 table 为空，进行初始化if((tab=table)==null||(n=tab.length)==0)n=(tab=resize()).length;// 2. 计算索引位置，如果该位置为空，直接插入if((p=tab[i=(n-1)&hash])==null)tab[i]=newNode(hash,key,value,null);else{Node<K,V>e;Kk;// 3. 如果第一个节点就是目标节点if(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k))))e=p;// 4. 如果是树节点elseif(pinstanceofTreeNode)e=((TreeNode<K,V>)p).putTreeVal(this,tab,hash,key,value);// 5. 链表遍历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;}if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))break;p=e;}}// 6. 存在相同的 key，更新 valueif(e!=null){VoldValue=e.value;if(!onlyIfAbsent||oldValue==null)e.value=value;afterNodeAccess(e);returnoldValue;}}++modCount;// 7. 检查是否需要扩容if(++size>threshold)resize();afterNodeInsertion(evict);returnnull;}

3.4 扩容机制 (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;}elseif((newCap=oldCap<<1)<MAXIMUM_CAPACITY&&oldCap>=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<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];table=newTab;if(oldTab!=null){for(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{// 链表// 低位链表和高位链表Node<K,V>loHead=null,loTail=null;Node<K,V>hiHead=null,hiTail=null;Node<K,V>next;do{next=e.next;// 判断节点在新数组中的位置if((e.hash&oldCap)==0){if(loTail==null)loHead=e;elseloTail.next=e;loTail=e;}else{if(hiTail==null)hiHead=e;elsehiTail.next=e;hiTail=e;}}while((e=next)!=null);// 将链表放入新数组if(loTail!=null){loTail.next=null;newTab[j]=loHead;}if(hiTail!=null){hiTail.next=null;newTab[j+oldCap]=hiHead;}}}}}returnnewTab;}

3.5 get 方法实现

publicVget(Objectkey){Node<K,V>e;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){// 检查第一个节点if(first.hash==hash&&((k=first.key)==key||(key!=null&&key.equals(k))))returnfirst;if((e=first.next)!=null){// 如果是树节点if(firstinstanceofTreeNode)return((TreeNode<K,V>)first).getTreeNode(hash,key);// 遍历链表do{if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))returne;}while((e=e.next)!=null);}}returnnull;}

4. 核心原理详解

4.1 哈希冲突解决

链地址法

// 当发生哈希冲突时，将新节点添加到链表末尾if((e=p.next)==null){p.next=newNode(hash,key,value,null);}

红黑树优化

当链表长度超过 TREEIFY_THRESHOLD(8) 且数组长度达到 MIN_TREEIFY_CAPACITY(64) 时，链表转换为红黑树：

finalvoidtreeifyBin(Node<K,V>[]tab,inthash){intn,index;Node<K,V>e;if(tab==null||(n=tab.length)<MIN_TREEIFY_CAPACITY)resize();// 先尝试扩容elseif((e=tab[index=(n-1)&hash])!=null){// 转换为红黑树TreeNode<K,V>hd=null,tl=null;do{TreeNode<K,V>p=replacementTreeNode(e,null);if(tl==null)hd=p;else{p.prev=tl;tl.next=p;}tl=p;}while((e=e.next)!=null);if((tab[index]=hd)!=null)hd.treeify(tab);}}

4.2 扩容机制原理

扩容时机

• 元素数量超过阈值 (capacity × loadFactor)
• 链表长度超过阈值但数组长度小于 MIN_TREEIFY_CAPACITY

高效重新哈希

JDK 1.8 优化：节点在新数组中的位置要么保持不变，要么是原位置 + 原容量

// 判断节点位置变化的巧妙方法if((e.hash&oldCap)==0){// 位置不变（低位链表）}else{// 位置 = 原位置 + 原容量（高位链表）}

4.3 负载因子作用

负载因子 = 元素数量 / 数组长度

• 默认值 0.75：时间和空间的平衡点
• 较小值：减少哈希冲突，但浪费空间
• 较大值：节省空间，但增加哈希冲突

5. 性能分析

5.1 时间复杂度

5.2 空间复杂度

• O(n)：存储 n 个元素

6. 使用注意事项

6.1 正确实现 hashCode() 和 equals()

classKeyClass{privatefinalStringid;@OverridepublicinthashCode(){returnObjects.hash(id);}@Overridepublicbooleanequals(Objectobj){if(this==obj)returntrue;if(obj==null||getClass()!=obj.getClass())returnfalse;KeyClasskey=(KeyClass)obj;returnObjects.equals(id,key.id);}}

6.2 线程安全问题

// 解决方案 1：使用 ConcurrentHashMapMap<String,String>concurrentMap=newConcurrentHashMap<>();// 解决方案 2：使用 Collections.synchronizedMapMap<String,String>syncMap=Collections.synchronizedMap(newHashMap<>());// 解决方案 3：使用同步块synchronized(map){// 操作 map}

7. 总结

HashMap 的核心设计思想：

1. 数组 + 链表/红黑树的复合结构平衡了空间和时间效率
2. 动态扩容机制保证哈希表的负载均衡
3. 红黑树优化解决了极端情况下的性能退化问题
4. 位运算优化提升了计算效率

理解 HashMap 的源码和原理对于编写高性能的 Java 程序至关重要