链接：https://pan.baidu.com/s/1shlZaV_asLY-G4ZT3kLuWw 

提取码：dit4 

 

JAVA 集合实现原理及其优化 1 List 集合 该接口： public interface List<E> extends Collection<E> { int size(); boolean isEmpty(); boolean contains(Object o); Object[] toArray(); <T> T[] toArray(T[] a); boolean containsAll(Collection<?> c); boolean addAll(Collection<? extends E> c); boolean addAll(int index, Collection<? extends E> c); boolean removeAll(Collection<?> c); boolean retainAll(Collection<?> c); default void replaceAll(UnaryOperator<E> operator) { Objects.requireNonNull(operator); final ListIterator<E> li = this.listIterator(); while (li.hasNext()) { li.set(operator.apply(li.next())); } }@SuppressWarnings({"unchecked", "rawtypes"}) default void sort(Comparator<? super E> c) { Object[] a = this.toArray(); Arrays.sort(a, (Comparator) c); ListIterator<E> i = this.listIterator(); for (Object e : a) { i.next(); i.set((E) e); } }void clear(); int hashCode(); E get(int index); E set(int index, E element); void add(int index, E element); E remove(int index); int indexOf(Object o); int lastIndexOf(Object o); ListIterator<E> listIterator(); ListIterator<E> listIterator(int index); List<E> subList(int fromIndex, int toIndex); } 2

JAVA 集合实现原理及其优化 逐一来看看它的实现类。 1.2 ArrayList public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable 由于该类方法太多，我们之分析关键的方法。 该类的说明： 1、无序不唯一 上面可知 ArrayList 的继承和实现关系。 基础的默认创建、指定大小创建，是很基础的东西。来看看由该类的三个构造器 创建的 List。 //默认创建一个 ArrayList 集合 List<String> list = new ArrayList<>(); //创建一个初始化长度为 100 的 ArrayList 集合 List<String> initlist = new ArrayList<>(100); //将其他类型的集合转为 ArrayList List<String> setList = new ArrayList<>(new HashSet()); 前两个构造器： /*** 纯空数组，但是指定长度 */ private static final Object[] EMPTY_ELEMENTDATA = {}; /*** 纯空数组，默认长度 */private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /*** 对象数组 */ transient Object[] elementData; /*** 构造得到一个有指定长度的数组 */ public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ 3

JAVA 集合实现原理及其优化 initialCapacity); } }/*** 构造得到一个初始长度为 10 的数组. */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }由于 ArrayList 之上多重继承中有实现了 Collection。也就是提供了将 Collection 下 的 LinkedList、HashSet、LinkedHashSet、TreeSet 转为 ArrayList。 public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } }上面的实现其实不难，是 Arrays.copyOf 方法的利用。 比如： List<String> linklist = new ArrayList<>(new LinkedList<>()); List<String> treelist = new ArrayList<>(new TreeSet<>()); List<String> linktreelist = new ArrayList<>(new LinkedHashSet<String>()); 这样的实现大大方便了我们的集合转换。 1.2.1 ArrayList 的扩容机制。 总体来说，分为两步扩容和添加元素。 扩容：扩大数组的长度(这是核心)。就是把原来的数组复制到空间更大的数 组中去。 添加元素：将新元素添加到扩容后的数组。 每次添加新元素将调用：