Java 中常见的集合类主要有 List、Set 和 Map。这些集合类使用广泛，因此深入了解它们的实现原理非常重要。在 Java 的集合类中，最常用的是 ArrayList、LinkedList、HashSet 和 HashMap，这些集合类的实现基本都依赖于数组和链表。
一、ArrayList 源码
ArrayList 是 Java 中最常用的集合类之一，它底层使用数组实现，它的查询效率比 LinkedList 高。在 ArrayList 中，随机访问元素的时间复杂度为 O(1)，增加或删除元素的时间复杂度为 O(n)。
在 Java 8 版本中，ArrayList 的源码中有一些新的方法，比如 spliterator()，用于提供集合的可分割性和遍历性。另外，还有 sort()和 replaceAll()方法，用于对集合进行排序和替换元素。
下面是 ArrayList 的部分源代码，用于展示 ArrayList 的实现原理。
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { /** * 默认的初始化数组容量大小 */ private static final int DEFAULT_CAPACITY = 10;
/** * 元素实际数量 */ private int size;
/** * 存放元素的数组 */ private Object[] elementData;
/** * ArrayList默认构造函数 */ public ArrayList() { this.elementData = new Object[DEFAULT_CAPACITY]; }
/** * ArrayList带初始化大小的构造函数 */ public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = new Object[]{}; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }
/** * 向ArrayList末尾添加元素 */ public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
/** * 返回ArrayList指定下标的元素 */ @SuppressWarnings("unchecked") public E get(int index) { rangeCheck(index);
return (E) elementData[index]; }
/** * 确保ArrayList容量足够 */ private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); }
ensureExplicitCapacity(minCapacity); }
/** * 确保ArrayList容量足够 */ private void ensureExplicitCapacity(int minCapacity) { modCount++;
if (minCapacity - elementData.length > 0) grow(minCapacity); }
/** * 扩容ArrayList大小 */ private void grow(int minCapacity) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); }
/** * ArrayList迭代器 */ public Iterator<E> iterator() { return new Itr(); }
/** * 内部类Itr，ArrayList的迭代器实现 */ private class Itr implements Iterator<E> { //... }
//...}
复制代码
二、LinkedList 源码
LinkedList 是 Java 中另一个常用的集合类，它底层使用双向链表实现。在 LinkedList 中，插入和删除元素的时间复杂度为 O(1)，获取元素的时间复杂度为 O(n)。
与 ArrayList 不同，LinkedList 还支持栈和队列操作，比如 poll()、offer()和 push()等方法，这些方法可以实现在集合的开头和结尾插入、删除元素。
下面是 LinkedList 的部分源代码，用于展示 LinkedList 的实现原理。
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { /** * 链表长度 */ transient int size = 0;
/** * 链表头部 */ transient Node<E> first;
/** * 链表尾部 */ transient Node<E> last;
/** * 构造一个空链表 */ public LinkedList() { }
/** * 向链表头部插入元素 */ private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; }
/** * 链表中删除指定元素 */ public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }
/** * 链表从头向尾遍历元素 */ public Iterator<E> iterator() { return new ListItr(0); }
/** * 内部类ListItr，链表迭代器的实现 */ private class ListItr implements ListIterator<E> { //... }
/** * 内部类Node，链表中存储节点的实现 */ 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; } }}
复制代码
三、HashSet 源码
HashSet 是 Java 中常用的 Set 集合类，它底层使用 HashMap 来实现。在 HashSet 中，元素的添加、删除和查找操作时间复杂度均为 O(1)。
HashSet 与 HashMap 实现的主要区别是，在 HashSet 中，添加元素是将元素添加到 HashMap 的 key 值上，value 值是一个 FINAL new object()；
下面是 HashSet 的部分源代码，用于展示 HashSet 的实现原理。
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable { /** * 底层使用的HashMap实例 */ private transient HashMap<E,Object> map;
/** * 集合元素的默认值 */ private static final Object PRESENT = new Object();
/** * 构造一个空HashSet */ public HashSet() { map = new HashMap<>(); }
/** * 向HashSet中添加元素 */ public boolean add(E e) { return map.put(e, PRESENT)==null; }
/** * 返回集合的迭代器 */ public Iterator<E> iterator() { return map.keySet().iterator(); }
//...}
复制代码
评论