java的集合list、set 、map的源码解读

<think>我们正在讨论Java集合框架中List、Set和Map的源码分析与解读。根据引用内容，我们可以从以下几个方面进行解读：1.List：以ArrayList为例（引用[1]提到ArrayList）2.Set：以HashSet为例（引用[2]和[3]提到HashSet）3.Map：以HashMap为例（引用[4]和[5]提到HashMap）我们将分别从它们的存储结构、关键方法（如添加、删除、查找）的源码实现以及性能特性进行分析。注意：由于源码版本不同，我们主要参考JDK8及以上的实现，因为JDK8中HashMap引入了红黑树。开始分析：1.ArrayList-存储结构：基于动态数组-关键方法：add(Ee)：添加元素到末尾，如果容量不足则进行扩容（通常扩容为原来的1.5倍）remove(intindex)：移除指定位置的元素，需要移动后续元素（效率较低）get(intindex)：直接通过下标访问，效率高2.HashSet-存储结构：基于HashMap（实际上，HashSet内部使用了一个HashMap，其元素作为HashMap的key，而value则是一个固定的Object对象）-关键方法：add(Ee)：调用HashMap的put方法，将元素作为key，一个固定的PRESENT对象作为valueremove(Objecto)：调用HashMap的remove方法由于基于HashMap，所以HashSet的元素不可重复，且无序3.HashMap-存储结构（JDK8）：数组+链表+红黑树-关键方法：put(Kkey,Vvalue)：计算key的hash值，确定数组下标；如果该位置为空，则直接放入；如果发生冲突，则以链表形式存储；当链表长度超过阈值（默认为8）且数组长度大于64时，链表转换为红黑树。get(Objectkey)：根据key的hash值找到数组下标，然后在链表或红黑树中查找。resize()：当元素数量超过阈值（容量*负载因子）时，进行扩容（容量变为原来的2倍），并重新分配元素。下面我们分别对ArrayList、HashSet和HashMap的源码进行详细解读。由于篇幅限制，我们不会列出全部源码，而是分析关键代码片段。一、ArrayList源码分析1.存储结构：Object[]数组```javatransientObject[]elementData;//存储元素的数组```2.添加元素（add方法）：```javapublicbooleanadd(Ee){ensureCapacityInternal(size+1);//确保容量足够，如果不够则扩容elementData[size++]=e;returntrue;}privatevoidensureCapacityInternal(intminCapacity){if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){minCapacity=Math.max(DEFAULT_CAPACITY,minCapacity);}ensureExplicitCapacity(minCapacity);}privatevoidensureExplicitCapacity(intminCapacity){modCount++;if(minCapacity-elementData.length>0)grow(minCapacity);}privatevoidgrow(intminCapacity){intoldCapacity=elementData.length;intnewCapacity=oldCapacity+(oldCapacity>>1);//扩容为原来的1.5倍if(newCapacity-minCapacity<0)newCapacity=minCapacity;if(newCapacity-MAX_ARRAY_SIZE>0)newCapacity=hugeCapacity(minCapacity);elementData=Arrays.copyOf(elementData,newCapacity);//复制到新数组}```3.删除元素（remove方法）：```javapublicEremove(intindex){rangeCheck(index);//检查索引modCount++;EoldValue=elementData(index);intnumMoved=size-index-1;if(numMoved>0)System.arraycopy(elementData,index+1,elementData,index,numMoved);//移动数组元素elementData[--size]=null;//让GC回收returnoldValue;}```二、HashSet源码分析1.内部使用HashMap：```javaprivatetransientHashMap<E,Object>map;//虚拟值，用于作为HashMap的valueprivatestaticfinalObjectPRESENT=newObject();```2.添加元素（add方法）：```javapublicbooleanadd(Ee){returnmap.put(e,PRESENT)==null;//如果HashMap中此key不存在，则添加成功}```3.删除元素（remove方法）：```javapublicbooleanremove(Objecto){returnmap.remove(o)==PRESENT;//删除key，并判断是否成功}```三、HashMap源码分析（JDK8）1.存储结构：数组（Node[]table）+链表/红黑树```javatransientNode<K,V>[]table;//Node节点结构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;//red-blacktreelinksTreeNode<K,V>left;TreeNode<K,V>right;TreeNode<K,V>prev;//neededtounlinknextupondeletionbooleanred;//...方法}```2.添加元素（put方法）：```javapublicVput(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;if((tab=table)==null||(n=tab.length)==0)n=(tab=resize()).length;//初始化数组if((p=tab[i=(n-1)&hash])==null)//计算数组下标，如果该位置为空tab[i]=newNode(hash,key,value,null);//直接放入else{Node<K,V>e;Kk;if(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k))))e=p;//如果第一个节点就是相同的keyelseif(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)//达到阈值treeifyBin(tab,hash);//转换为红黑树break;}if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))break;p=e;}}if(e!=null){//存在相同的key，则更新valueVoldValue=e.value;if(!onlyIfAbsent||oldValue==null)e.value=value;afterNodeAccess(e);returnoldValue;}}++modCount;if(++size>threshold)//超过阈值，扩容resize();afterNodeInsertion(evict);returnnull;}```3.扩容（resize方法）：```javafinalNode<K,V>[]resize(){//...代码较长，主要步骤：//1.计算新的容量和阈值（2倍）//2.创建新数组//3.将旧数组中的元素重新分配到新数组中（需要重新计算位置）//如果是树节点，则调用split方法（可能会将树拆分为链表或两棵树）//如果是链表，则拆分为两个链表（根据hash值新增的bit位是0还是1）}```总结：-ArrayList：动态数组，随机访问快，插入删除慢（需要移动元素）。-HashSet：基于HashMap，元素不重复，无序。-HashMap：数组+链表+红黑树，根据键的hash值存储，提供快速的查找和插入。通过源码分析，我们可以理解这些集合的内部实现机制，从而在实际开发中根据需求选择合适的集合类型，并注意其性能特性。参考文献：[^1]:Java集合框架提供了丰富的集合类型，开发者应根据实际需求选择合适的集合。理解集合的内部实现和性能特性将有助于写出高效的代码。通过对ArrayList、HashSet和HashMap的深入分析，我们可以看到这些集合是如何运作的，以及它们的优势和局限性。希望通过本篇文章，能够帮助你深入理解Java集合框架，从而在开发中游刃有余！[^2]:用以下代码进行分析：importjava.util.HashSet;publicclassHashSet_{publicstaticvoidmain(String[]args){HashSethashSet=newHashSet();//添加元素hashSet.add("xiong");hashSet.add("study");hashSet.add("xiong");}}[^3]:想要理解Java中集合类底层使用的数据结构，就要先了解有什么数据结构。本篇文章我们不多做解释，将常见数据结构以及概念罗列，为我们下面分析Java集合源码做铺垫。我将数据结构分为了两类，分别是线性结构和非线性结构。2.1线性结构[^4]:⭕HashMap的存储结构JDK7及以前版本：HashMap是数组+链表结构(即为链地址法)JDK8版本发布以后：HashMap是数组+链表+红黑树实现。3.2HashMap的底层实现原理[^5]:做以上这些操作的根本原因还是因为java设计者认为把HashMap$Node对象存放到entrySet就方便我们遍历，因为Map.Entry提供了getKey()和getValue()，可以让我们单独地取出table里的key对象§§相关问题§§1.ArrayList的扩容机制是如何优化的？2.为什么HashSet不能保证元素的顺序？3.HashMap在JDK8中引入红黑树解决了什么问题？4.在HashMap中，如何解决哈希冲突？5.如何选择合适的集合类以满足不同的应用场景？</think>### Java 集合框架 List、Set、Map 源码分析与解读 #### **一、List 接口（以 ArrayList 为例）** **存储结构** ArrayList 基于**动态数组**实现，核心源码如下： ```java transient Object[] elementData; // 存储元素的数组 private int size; // 实际元素数量 ``` - 初始容量为 10（默认），扩容时增长 50%： ```java private void grow(int minCapacity) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容为原容量的1.5倍 elementData = Arrays.copyOf(elementData, newCapacity); } ``` **关键操作** 1. **添加元素**： ```java public boolean add(E e) { ensureCapacityInternal(size + 1); // 检查容量并扩容 elementData[size++] = e; return true; } ``` - 时间复杂度：均摊 $O(1)$（扩容时 $O(n)$）。 2. **随机访问**： ```java public E get(int index) { rangeCheck(index); // 检查索引范围 return elementData(index); // 直接通过下标访问 } ``` - 时间复杂度：$O(1)$。 **特点** - 有序、允许重复元素。 - 随机访问高效，但插入/删除中间元素需移动数据（$O(n)$）[^1]。 --- #### **二、Set 接口（以 HashSet 为例）** **存储结构** HashSet 基于 **HashMap** 实现（元素作为 Key）： ```java private transient HashMap<E, Object> map; private static final Object PRESENT = new Object(); // 虚拟Value值 ``` **添加元素**： ```java public boolean add(E e) { return map.put(e, PRESENT) == null; // 依赖HashMap的put方法 } ``` - 重复元素判断：通过 `hashCode()` 和 `equals()` 方法。 **底层原理** - 使用哈希表存储（数组 + 链表/红黑树）： ```java // HashMap内部结构（JDK8+） transient Node<K,V>[] table; // 数组+链表 static class Node<K,V> { final int hash; final K key; V value; Node<K,V> next; } ``` - 哈希冲突时，链表长度 >8 且数组长度 >64 时转为红黑树[^4]。 **特点** - 无序、元素唯一。 - 添加/查找时间复杂度：平均 $O(1)$，最坏 $O(\log n)$（树化后）[^2]。 --- #### **三、Map 接口（以 HashMap 为例）** **存储结构（JDK8+）** ```java transient Node<K,V>[] table; // 数组（桶） static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; // 链表结构 } ``` - **数组 + 链表 + 红黑树**（树化阈值：链表长度 ≥8 且数组长度 ≥64）[^4]。 **核心方法** 1. **`put()` 流程**： ```java final V putVal(int hash, K key, V value, boolean onlyIfAbsent) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 初始化或扩容 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); // 直接放入桶中 else { // 处理哈希冲突（链表/树插入） if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); // 链表转树 break; } if (e.hash == hash && Objects.equals(e.key, key)) break; p = e; } } } // ... 更新值并检查扩容 } ``` 2. **扩容机制**： - 触发条件：元素数量 > 容量 × 负载因子（默认 0.75）。 - 过程：新建双倍容量数组，重新哈希所有元素（时间复杂度 $O(n)$）[^4]。 **特点** - Key 唯一、Value 可重复。 - 高效查找（平均 $O(1)$），线程不安全。 --- #### **四、性能对比** | 集合类型 | 底层结构 | 是否有序 | 允许重复 | 查找性能 | 适用场景 | |------------|-------------------|----------|----------|----------|------------------------------| | `ArrayList`| 动态数组 | 是 | 是 | $O(1)$ | 频繁随机访问 | | `HashSet` | 哈希表（HashMap） | 否 | 否 | $O(1)$ | 快速去重 | | `HashMap` | 数组+链表+红黑树 | 否 | Key 唯一 | $O(1)$ | Key-Value 映射（如缓存） | --- #### **设计思想总结** 1. **动态扩容**：ArrayList/HashMap 均通过动态扩容平衡空间与时间效率。 2. **哈希优化**：HashMap 通过树化解决哈希冲突导致的性能退化。 3. **接口统一**：所有集合实现标准接口（如 `Iterable`），便于扩展[^1]。 ---