06_java常见集合类底层实现

在JDK8中，Java的集合类是一个非常重要的部分，它们提供了丰富的数据结构来存储和操作对象。这些集合类主要位于 java.util包中，并由两大接口派生而来：一个是 Collection接口，主要用于存放单一元素；另一个是 Map接口，主要用于存放键值对。下面是对一些常见集合类的底层实现及源码的简要解析：

一、Collection接口及其子接口

1. List接口

List接口是一个有序的集合，可以包含重复的元素。List接口的实现类主要有ArrayList、LinkedList和Vector。

• ArrayList

  • 底层实现：ArrayList底层维护了一个Object类型的数组（elementData），用于存储集合中的元素。

    // 源码
    public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    {// ***transient Object[] elementData; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//***public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}// ***
    }
    

  • 扩容机制：当向ArrayList中添加元素时，如果当前数组容量不足，会进行扩容。扩容后的新容量通常是当前容量的1.5倍（向下取整）。如果使用的是无参构造器，则初始容量为0（懒汉式，只有第一次add元素时才会进行容量的指定），第一次添加元素时扩容为10。如果使用的是指定大小的构造器，则初始容量为指定大小，后续扩容时按照1.5倍的规则进行。

    // 调用
    public class DemoUtils {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("a");}
    }// ArrayList源码
    public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    {// ***public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;}private void ensureCapacityInternal(int minCapacity) {// 容量判断ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private static final int DEFAULT_CAPACITY = 10; // 默认容量10private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // 数组最大容量private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;}private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1); // >>1表示“除2取整”，因为转为二进制后右移1位，所以直接丢弃最右侧的一位，即向下取整if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:elementData = Arrays.copyOf(elementData, newCapacity);}private static int hugeCapacity(int minCapacity) {// 大容量判断if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}// ***
    }
    

  • 源码解析：ArrayList的add方法会先调用ensureCapacityInternal方法确保当前容量足够，如果不够则调用grow方法进行扩容。扩容时会创建一个新的数组，并将旧数组中的元素复制到新数组中。

• LinkedList

  • 底层实现：LinkedList底层采用了双向链表结构，每个节点（Node对象）包含三个属性：prev（指向前一个节点）、next（指向后一个节点）和item（存储节点值）。

    // 源码
    public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    {transient int size = 0;/*** Pointer to first node.* Invariant: (first == null && last == null) ||*            (first.prev == null && first.item != null)*/transient Node<E> first;/*** Pointer to last node.* Invariant: (first == null && last == null) ||*            (last.next == null && last.item != null)*/transient Node<E> last;public LinkedList() {}public LinkedList(Collection<? extends E> c) {this();addAll(c);}public boolean add(E e) { // 新增元素linkLast(e);return true;}/*** Links e as last element.*/void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++;}// 节点类private static class Node<E> {E item;Node<E> next;Node<E> prev;Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}}// ***
    }
    

  • 特点：LinkedList适合进行频繁的插入和删除操作，因为链表结构可以使得这些操作的时间复杂度为O(1)。但是，LinkedList的查询效率较低，因为需要从头节点开始遍历链表。

• Vector

  • 底层实现：Vector的底层实现与ArrayList类似，也是采用了一个Object类型的数组来存储元素。

    // 调用
    public class DemoUtils {public static void main(String[] args) {// 默认午餐构造（初始默认容量为10）Vector<String> vector = new Vector<>();vector.add("1");// 1 末尾添加元素，不考虑线程安全vector.add(0, "2");// 2 在指定下标index设置元素，线程安全System.out.println(vector.get(0));// 指定初始容量7，扩容时增量长度为5Vector<String> vector2 = new Vector<>(7, 5);}
    }// 源码
    public class Vector<E>extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    {protected Object[] elementData;// 元素内容数组// 有参构造-参数：容量public Vector(int initialCapacity) {this(initialCapacity, 0);}// 无参构造public Vector() {this(10); // 初始容量默认10}// 传入集合作为入参public Vector(Collection<? extends E> c) {elementData = c.toArray();elementCount = elementData.length;// c.toArray might (incorrectly) not return Object[] (see 6260652)if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, elementCount, Object[].class);}// 有参构造-参数为指定容量public Vector(int initialCapacity) {this(initialCapacity, 0);}// 有参构造-参数：1容量、2增量容量；当前类中构造函数最后实际调用的就是这个public Vector(int initialCapacity, int capacityIncrement) {super();if (initialCapacity < 0)throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);this.elementData = new Object[initialCapacity];this.capacityIncrement = capacityIncrement;}// 新增元素1-末尾追加，不考虑线程安全，所以不用`synchronized`public synchronized boolean add(E e) {modCount++;ensureCapacityHelper(elementCount + 1);elementData[elementCount++] = e;return true;}// 新增元素2-指定位置添加元素，线程安全public void add(int index, E element) {insertElementAt(element, index);}// 操作指定位置的元素时，通过`synchronized`保证了线程安全，其他方法也是如此public synchronized void insertElementAt(E obj, int index) {modCount++;if (index > elementCount) {throw new ArrayIndexOutOfBoundsException(index+ " > " + elementCount);}ensureCapacityHelper(elementCount + 1);System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);elementData[index] = obj;elementCount++;}// 添加元素前-容量判断[扩容]private void ensureCapacityHelper(int minCapacity) {// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity); // 扩容}protected int capacityIncrement; // 扩容长度private void grow(int minCapacity) { // 扩容方法// overflow-conscious codeint oldCapacity = elementData.length;// 新数组长度 = 旧数组容量 + (增量容量 > 0 ? 增量容量 : 旧数组容量)// 所以，如果调用Vector构造时不指定增量时，Vector的扩容后总容量时扩容前2倍int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity);}// ***
    }
    

  • 扩容机制：（无参构造初始容量10）Vector的扩容机制与ArrayList不同，Vector每次扩容时会将当前容量扩大为原来的两倍或者当前容量+增量容量。

    private void grow(int minCapacity) { // 扩容方法// overflow-conscious codeint oldCapacity = elementData.length;// 新数组长度 = 旧数组容量 + (增量容量 > 0 ? 增量容量 : 旧数组容量)// 所以，如果调用Vector构造时不指定增量时，Vector的扩容后总容量时扩容前2倍int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity);}
    

  • 线程安全性：Vector是线程安全的，因为它的所有方法都添加了synchronized关键字来保证线程安全。但是，这也导致了Vector在多线程环境下的性能不如ArrayList。

2. Set接口

Set接口是一个不包含重复元素的集合。Set接口的实现类主要有HashSet、LinkedHashSet和TreeSet。

• HashSet

  • 底层实现：HashSet是基于HashMap实现的。HashSet中的元素被存储在HashMap的key中，而value则是一个固定的对象（通常是PRESENT）。

    // 源码
    public class HashSet<E>extends AbstractSet<E>implements Set<E>, Cloneable, java.io.Serializable
    {static final long serialVersionUID = -5024744406713321676L;private transient HashMap<E,Object> map;// Dummy value to associate with an Object in the backing Mapprivate static final Object PRESENT = new Object();public HashSet() {map = new HashMap<>();// 可见基于HashMap实现}public HashSet(Collection<? extends E> c) {map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));addAll(c);}public HashSet(int initialCapacity, float loadFactor) {map = new HashMap<>(initialCapacity, loadFactor);}public HashSet(int initialCapacity) {map = new HashMap<>(initialCapacity);}//LinkedHashSet专用：LinkedHashSet构造方法中调用的super() 指向此处HashSet(int initialCapacity, float loadFactor, boolean dummy) {map = new LinkedHashMap<>(initialCapacity, loadFactor);}// 新增元素public boolean add(E e) {//  默认的虚拟对象PRESENT作为map的valuereturn map.put(e, PRESENT)==null;}
    }// HashMap源码的关键片段
    public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {// 负载因子，扩容时使用static final float DEFAULT_LOAD_FACTOR = 0.75f; public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}// 设置元素-返回值是value本身public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}// ***
    }
    

  • 元素添加过程：当HashSet要添加一个元素时，它会执行以下步骤：

    1. 计算哈希值：调用元素的hashCode方法计算哈希值。
    2. 定位桶：根据哈希值定位到HashMap中的某个桶（或称为槽位）。
    3. 检查桶中元素：
       • 如果桶为空，则直接将新元素添加到桶中。
       • 如果桶中已经有元素，则会遍历桶中的元素（在JDK8中，桶可能是链表或红黑树），并比较每个元素的哈希值。
         • 如果找到哈希值相同的元素，则进一步调用equals方法比较两个元素是否相等。
           • 如果相等，则不添加新元素（因为HashSet不允许重复元素）。
           • 如果不相等，则将新元素添加到桶中（这可能是将新元素链接到链表的末尾，或者插入到红黑树中的适当位置）。
         • 如果遍历完桶中的所有元素都没有找到哈希值相同的元素，则将新元素添加到桶中。

  • 扩容机制：因为HashSet基于HashMap实现，所以HashSet的扩容机制实际上与HashMap的扩容机制相同。在下面【二、Map】章节中讲解。

• LinkedHashSet

  • 底层实现：LinkedHashSet是基于HashMap和双向链表实现的。它继承了HashSet的所有特性（因为LinkedHashSet<E> extends HashSet<E>），并额外维护了一个双向链表（构造方法中通过super()调用HashSet中LinkedHashSet专用的构造方法，其中使用LinkedHashMap引入了双向链表）来记录元素的插入顺序。

    // 源码
    public class LinkedHashSet<E>extends HashSet<E>implements Set<E>, Cloneable, java.io.Serializable {private static final long serialVersionUID = -2851667679971038690L;public LinkedHashSet(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor, true);}public LinkedHashSet(int initialCapacity) {super(initialCapacity, .75f, true);}public LinkedHashSet() {// 初始容量16，负载因子0.75super(16, .75f, true);// 调用父类HashSet中的构造函数}public LinkedHashSet(Collection<? extends E> c) {super(Math.max(2*c.size(), 11), .75f, true); // 调用父类HashSet中的构造函数addAll(c);}
    }// HashSet源码
    public class HashSet<E>extends AbstractSet<E>implements Set<E>, Cloneable, java.io.Serializable
    {// ***/*** Constructs a new, empty linked hash set.  (This package private* constructor is only used by LinkedHashSet.) The backing* HashMap instance is a LinkedHashMap with the specified initial* capacity and the specified load factor.** @param      initialCapacity   the initial capacity of the hash map* @param      loadFactor        the load factor of the hash map* @param      dummy             ignored (distinguishes this*             constructor from other int, float constructor.)* @throws     IllegalArgumentException if the initial capacity is less*             than zero, or if the load factor is nonpositive*///LinkedHashSet专用：LinkedHashSet构造方法中调用的super() 指向此处HashSet(int initialCapacity, float loadFactor, boolean dummy) {map = new LinkedHashMap<>(initialCapacity, loadFactor);// 此处LinkedHashMap说明引入了双向链表的概念}// ***
    }

  • 扩容机制：LinkedHashSet的扩容机制是基于其内部的HashMap实现的，当元素数量超过容量限制时，会进行扩容操作，以容纳更多的元素，同时保持元素的插入顺序不变。

  • 特点：LinkedHashSet既保留了HashSet的添加、删除和查找效率，又能够按照元素的插入顺序进行遍历。

3. Queue接口

Queue接口是一个按照特定排队规则来确定元素先后顺序的集合。Queue接口的实现类有很多，比如LinkedList（它同时实现了List接口和Deque接口，因此既可以作为List使用，也可以作为Queue使用）、PriorityQueue等。

二、Map接口及其实现类

Map接口是一个存储键值对（key-value）的集合。Map接口的实现类主要有HashMap、LinkedHashMap、TreeMap、Hashtable等。

1. HashMap

• 底层实现：HashMap底层采用了数组+链表+红黑树的结构。在JDK8中，当链表长度超过一定阈值（默认为8）且数组容量大于64时，链表会转换为红黑树以提高查找效率。

  // 调用
  public class DemoUtils {public static void main(String[] args) {HashMap<String, String> map = new HashMap<>();map.put("k1", "v1");map.put("k2", "v2");System.out.println(map);}
  }// 源码
  public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {/*** The default initial capacity - MUST be a power of two.*/static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认容量16/*** The maximum capacity, used if a higher value is implicitly specified* by either of the constructors with arguments.* MUST be a power of two <= 1<<30.*/static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量2^30/*** The load factor used when none specified in constructor.*/static final float DEFAULT_LOAD_FACTOR = 0.75f; // 负载因子，默认0.75/*** The bin count threshold for using a tree rather than list for a* bin.  Bins are converted to trees when adding an element to a* bin with at least this many nodes. The value must be greater* than 2 and should be at least 8 to mesh with assumptions in* tree removal about conversion back to plain bins upon* shrinkage.*/static final int TREEIFY_THRESHOLD = 8; // 树化阈值，8/*** The bin count threshold for untreeifying a (split) bin during a* resize operation. Should be less than TREEIFY_THRESHOLD, and at* most 6 to mesh with shrinkage detection under removal.*/static final int UNTREEIFY_THRESHOLD = 6; /*** The smallest table capacity for which bins may be treeified.* (Otherwise the table is resized if too many nodes in a bin.)* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts* between resizing and treeification thresholds.*/static final int MIN_TREEIFY_CAPACITY = 64;/*** Basic hash bin node, used for most entries.  (See below for* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)*/static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}public final K getKey()        { return key; }public final V getValue()      { return value; }public final String toString() { return key + "=" + value; }public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}public final V setValue(V newValue) {V oldValue = value;value = newValue;return oldValue;}public final boolean equals(Object o) {if (o == this)return true;if (o instanceof Map.Entry) {Map.Entry<?,?> e = (Map.Entry<?,?>)o;if (Objects.equals(key, e.getKey()) &&Objects.equals(value, e.getValue()))return true;}return false;}}
  }
  

• 元素添加过程：当向HashMap中添加元素时，会先调用key的hashCode方法计算哈希值，然后根据哈希值确定元素在数组中的位置（桶）。如果桶中已经有元素存在，则按照链表或红黑树的方式存储新元素。

  public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}/*** Implements Map.put and related methods** @param hash hash for key* @param key the key* @param value the value to put* @param onlyIfAbsent if true, don't change existing value* @param evict if false, the table is in creation mode.* @return previous value, or null if none*/final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {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 {Node<K,V> e; K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;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) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}
  

• 扩容机制：HashMap的默认初始容量为16，加载因子为0.75。当HashMap中的元素数量超过阈值（容量乘以加载因子）时，会进行扩容操作。扩容后的新容量通常是当前容量的两倍。

2. LinkedHashMap

• 底层实现：LinkedHashMap是基于HashMap和双向链表实现的。它继承了HashMap的所有特性，并额外维护了一个双向链表来记录元素的插入顺序或访问顺序（取决于构造时的参数）。

  // 源码
  public class LinkedHashMap<K,V>extends HashMap<K,V>implements Map<K,V>
  {static class Entry<K,V> extends HashMap.Node<K,V> { // 键值对实体EntryEntry<K,V> before, after;Entry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);}}private static final long serialVersionUID = 3801124242820219131L;/*** The head (eldest) of the doubly linked list.*/transient LinkedHashMap.Entry<K,V> head;/*** The tail (youngest) of the doubly linked list.*/transient LinkedHashMap.Entry<K,V> tail;// ***/*** Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance* with the specified initial capacity and load factor.** @param  initialCapacity the initial capacity* @param  loadFactor      the load factor* @throws IllegalArgumentException if the initial capacity is negative*         or the load factor is nonpositive*/public LinkedHashMap(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor);accessOrder = false;}/*** Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance* with the specified initial capacity and a default load factor (0.75).** @param  initialCapacity the initial capacity* @throws IllegalArgumentException if the initial capacity is negative*/public LinkedHashMap(int initialCapacity) {super(initialCapacity);accessOrder = false;}/*** Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance* with the default initial capacity (16) and load factor (0.75).*/public LinkedHashMap() {super();accessOrder = false;}/*** Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with* the same mappings as the specified map.  The <tt>LinkedHashMap</tt>* instance is created with a default load factor (0.75) and an initial* capacity sufficient to hold the mappings in the specified map.** @param  m the map whose mappings are to be placed in this map* @throws NullPointerException if the specified map is null*/public LinkedHashMap(Map<? extends K, ? extends V> m) {super();accessOrder = false;putMapEntries(m, false);}/*** Constructs an empty <tt>LinkedHashMap</tt> instance with the* specified initial capacity, load factor and ordering mode.** @param  initialCapacity the initial capacity* @param  loadFactor      the load factor* @param  accessOrder     the ordering mode - <tt>true</tt> for*         access-order, <tt>false</tt> for insertion-order* @throws IllegalArgumentException if the initial capacity is negative*         or the load factor is nonpositive*/public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder = accessOrder;}final class LinkedKeySet extends AbstractSet<K> {public final int size()                 { return size; }public final void clear()               { LinkedHashMap.this.clear(); }public final Iterator<K> iterator() {return new LinkedKeyIterator();}public final boolean contains(Object o) { return containsKey(o); }public final boolean remove(Object key) {return removeNode(hash(key), key, null, false, true) != null;}public final Spliterator<K> spliterator()  {return Spliterators.spliterator(this, Spliterator.SIZED |Spliterator.ORDERED |Spliterator.DISTINCT);}public final void forEach(Consumer<? super K> action) {if (action == null)throw new NullPointerException();int mc = modCount;for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)action.accept(e.key);if (modCount != mc)throw new ConcurrentModificationException();}}final class LinkedValues extends AbstractCollection<V> {public final int size()                 { return size; }public final void clear()               { LinkedHashMap.this.clear(); }public final Iterator<V> iterator() {return new LinkedValueIterator();}public final boolean contains(Object o) { return containsValue(o); }public final Spliterator<V> spliterator() {return Spliterators.spliterator(this, Spliterator.SIZED |Spliterator.ORDERED);}public final void forEach(Consumer<? super V> action) {if (action == null)throw new NullPointerException();int mc = modCount;for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)action.accept(e.value);if (modCount != mc)throw new ConcurrentModificationException();}}final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {public final int size()                 { return size; }public final void clear()               { LinkedHashMap.this.clear(); }public final Iterator<Map.Entry<K,V>> iterator() {return new LinkedEntryIterator();}public final boolean contains(Object o) {if (!(o instanceof Map.Entry))return false;Map.Entry<?,?> e = (Map.Entry<?,?>) o;Object key = e.getKey();Node<K,V> candidate = getNode(hash(key), key);return candidate != null && candidate.equals(e);}public final boolean remove(Object o) {if (o instanceof Map.Entry) {Map.Entry<?,?> e = (Map.Entry<?,?>) o;Object key = e.getKey();Object value = e.getValue();return removeNode(hash(key), key, value, true, true) != null;}return false;}public final Spliterator<Map.Entry<K,V>> spliterator() {return Spliterators.spliterator(this, Spliterator.SIZED |Spliterator.ORDERED |Spliterator.DISTINCT);}public final void forEach(Consumer<? super Map.Entry<K,V>> action) {if (action == null)throw new NullPointerException();int mc = modCount;for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)action.accept(e);if (modCount != mc)throw new ConcurrentModificationException();}}
  }

• 特点：LinkedHashMap既保留了HashMap的查找效率，又能够按照元素的插入顺序或访问顺序进行遍历。

3. Hashtable

• 底层实现：Hashtable的底层实现与HashMap类似，也是采用了数组+链表的结构。但是，Hashtable是线程安全的，因为它的所有方法都添加了synchronized关键字来保证线程安全。
• 特点：由于Hashtable是线程安全的，因此在多线程环境下性能较低。此外，Hashtable不允许使用null作为key或value。

综上所述，JDK8中Java的常见集合类各有其底层实现和特性。在选择集合类时，应根据具体的使用场景和需求来选择最合适的集合类。

ps1：ArrayList中为什么要用transient 关键字？

ArrayList中transient Object[] elementData; 为什么要用transient关键字？

在 ArrayList 中，elementData 数组被声明为 transient 的原因主要与 Java 序列化机制 和 ArrayList 的内部优化 有关。以下是具体解释：

---

1. 避免冗余序列化

• ArrayList 的底层数组 elementData 的长度通常会比实际存储的元素数量大（因为扩容时会有预留空间）。例如：

  // 假设 elementData.length = 10，但实际只存了 5 个元素
  Object[] elementData = new Object[10];
  size = 5; // 实际有效元素数量
  

• 如果直接序列化整个 elementData 数组，会连带未使用的 null 槽位一起写入字节流，导致 空间浪费和性能下降。

• 通过 transient 标记后，ArrayList 可以自定义序列化逻辑，只写入实际有效的元素（即 size 范围内的数据）。

---

2. 自定义序列化逻辑

• ArrayList 通过重写 writeObject() 和 readObject() 方法，手动控制序列化过程：

  private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException {// 只序列化实际存储的元素（0 到 size-1）for (int i = 0; i < size; i++) {s.writeObject(elementData[i]);}
  }
  

• 反序列化时，会根据实际元素数量重建数组，避免存储无效的 null 值。

---

3. 兼容性与灵活性

• 如果未来 ArrayList 的底层实现改变（例如改用链表或其他结构），transient 可以确保序列化格式不受影响，因为序列化逻辑完全由类自身控制。

---

对比：非 transient 的后果

如果 elementData 不是 transient，序列化时会直接调用 ObjectOutputStream 的默认数组序列化逻辑，导致：

1. 写入整个数组（包括未使用的 null 槽位）。
2. 反序列化后，数组长度可能与原 ArrayList 的扩容状态不一致（破坏内部优化）。

---

总结

关键点	说明
避免冗余数据	只序列化有效元素，节省空间和带宽。
自定义序列化	通过 writeObject/readObject 精确控制数据写入和读取。
隐藏实现细节	即使内部数组扩容策略变化，序列化格式仍保持兼容。

这种设计体现了 Java 集合框架对性能和资源利用的优化思想。

ps2：LinkedList中的modCount有啥用？

在Java的LinkedList中，modCount变量扮演着记录集合修改次数的关键角色。具体来说，modCount的用途和意义体现在以下几个方面：

一、记录修改次数

• modCount是一个整型变量，它用于记录对LinkedList结构进行修改的次数。这里的修改操作包括但不限于添加、删除元素等。
• 每次对LinkedList进行增删改操作时，modCount的值都会增加1。

二、支持快速失败（fail-fast）行为

• LinkedList实现了Iterator接口，允许通过迭代器遍历集合中的元素。
• 在创建迭代器时，迭代器的内部会记录当前的modCount值（通常通过成员变量expectedModCount来保存）。
• 在迭代过程中，如果集合的结构被修改（即modCount发生变化），迭代器的expectedModCount与集合当前的modCount就会不一致。
• 此时，迭代器会检测到不一致并立即抛出ConcurrentModificationException异常，从而快速失败。这种机制有助于及早发现并发修改问题，避免潜在的数据不一致。

三、确保线程安全性的辅助手段

• 虽然LinkedList本身不是线程安全的，但modCount在一定程度上为开发者提供了一种检测并发修改的手段。
• 通过比较迭代前后的modCount值，开发者可以判断集合是否在迭代过程中被修改过。

示例代码分析

List<String> myList = new LinkedList<>();
myList.add("a");
myList.add("b");
Iterator<String> iterator = myList.iterator();
while (iterator.hasNext()) {String element = iterator.next();if ("a".equals(element)) {myList.remove(element); // 这将导致ConcurrentModificationException}
}

在上述代码中，如果在迭代过程中尝试修改LinkedList（如删除元素"a"），由于modCount的变化，迭代器会抛出ConcurrentModificationException。

综上所述，modCount在LinkedList中主要用于记录集合的修改次数，并支持迭代器的快速失败行为。它是确保集合在迭代过程中数据一致性的一种重要机制。