精华内容
下载资源
问答
  • ArrayList底层实现原理

    2019-07-23 10:02:00
    ArrayList底层实现原理 ArrayList 的实现原理 ArrayList 概述 ArrayList 可以理解为动态数组,用 MSDN 中的说法,就是 Array 的复杂版本。与 Java 中的数组相比,它的容量能动态增长。ArrayList 是 List 接口的可...

    ArrayList底层实现原理

    ArrayList 的实现原理

    ArrayList 概述

    ArrayList 可以理解为动态数组,用 MSDN 中的说法,就是 Array 的复杂版本。与 Java 中的数组相比,它的容量能动态增长。ArrayList 是 List 接口的可变数组的实现。实现了所有可选列表操作,并允许包括 null 在内的所有元素。除了实现 List 接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。(此类大致上等同于 Vector 类,除了此类是不同步的。)
    每个 ArrayList 实例都有一个容量,该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素,其容量也自动增长。自动增长会带来数据向新数组的重新拷贝,因此,如果可预知数据量的多少,可在构造 ArrayList 时指定其容量。在添加大量元素前,应用程序也可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量,这可以减少递增式再分配的数量。
    注意,此实现不是同步的。如果多个线程同时访问一个 ArrayList 实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步。(结构上的修改是指任何添加或删除一个或多个元素的操作,或者显式调整底层数组的大小;仅仅设置元素的值不是结构上的修改。)
    我们先学习了解其内部的实现原理,才能更好的理解其应用。

    ArrayList 的实现

    对于 ArrayList 而言,它实现 List 接口、底层使用数组保存所有元素。其操作基本上是对数组的操作。下面我们来分析 ArrayList 的源代码:

    实现的接口

    public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    {
    }

    ArrayList 继承了 AbstractList,实现了 List。它是一个数组队列,提供了相关的添加、删除、修改、遍历等功能。
    ArrayList 实现了 RandmoAccess 接口,即提供了随机访问功能。RandmoAccess 是 java 中用来被 List 实现,为 List 提供快速访问功能的。在 ArrayList 中,我们即可以通过元素的序号快速获取元素对象;这就是快速随机访问。
    ArrayList 实现了 Cloneable 接口,即覆盖了函数 clone(),能被克隆。 ArrayList 实现 java.io.Serializable 接口,这意味着 ArrayList 支持序列化,能通过序列化去传输。

    底层使用数组实现

    /**
    * The array buffer into which the elements of the ArrayList are stored.
    * The capacity of the ArrayList is the length of this array buffer.
    */
    private transient Object[] elementData;

    构造方法

    /**
         * Constructs an empty list with an initial capacity of ten.
         */
        public ArrayList() {
            this(10);
        }
        /**
         * Constructs an empty list with the specified initial capacity.
         *
         * @param  initialCapacity  the initial capacity of the list
         * @throws IllegalArgumentException if the specified initial capacity
         *         is negative
         */
        public ArrayList(int initialCapacity) {
            super();
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            this.elementData = new Object[initialCapacity];
        }
        /**
         * Constructs a list containing the elements of the specified
         * collection, in the order they are returned by the collection's
         * iterator.
         *
         * @param c the collection whose elements are to be placed into this list
         * @throws NullPointerException if the specified collection is null
         */
        public ArrayList(Collection<? extends E> c) {
            elementData = c.toArray();
            size = elementData.length;
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        }

    ArrayList 提供了三种方式的构造器:

    1. public ArrayList()可以构造一个默认初始容量为10的空列表;
    2. public ArrayList(int initialCapacity)构造一个指定初始容量的空列表;
    3. public ArrayList(Collection<? extends E> c)构造一个包含指定 collection 的元素的列表,这些元素按照该collection的迭代器返回它们的顺序排列的。

      存储

      ArrayList 中提供了多种添加元素的方法,下面将一一进行讲解:
      1.set(int index, E element):该方法首先调用rangeCheck(index)来校验 index 变量是否超出数组范围,超出则抛出异常。而后,取出原 index 位置的值,并且将新的 element 放入 Index 位置,返回 oldValue。
    /**
         * Replaces the element at the specified position in this list with
         * the specified element.
         *
         * @param index index of the element to replace
         * @param element element to be stored at the specified position
         * @return the element previously at the specified position
         * @throws IndexOutOfBoundsException {@inheritDoc}
         */
        public E set(int index, E element) {
            rangeCheck(index);
            E oldValue = elementData(index);
            elementData[index] = element;
            return oldValue;
        }
        /**
          * Checks if the given index is in range.  If not, throws an appropriate
          * runtime exception.  This method does *not* check if the index is
          * negative: It is always used immediately prior to an array access,
          * which throws an ArrayIndexOutOfBoundsException if index is negative.
          */
          private void rangeCheck(int index) {
            if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
          }

    2.add(E e):该方法是将指定的元素添加到列表的尾部。当容量不足时,会调用 grow 方法增长容量。

    /**
         * Appends the specified element to the end of this list.
         *
         * @param e element to be appended to this list
         * @return <tt>true</tt> (as specified by {@link Collection#add})
         */
        public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }
        private void ensureCapacityInternal(int minCapacity) {
            modCount++;
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
        private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 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);
        }

    3.add(int index, E element):在 index 位置插入 element。

    /**
         * Inserts the specified element at the specified position in this
         * list. Shifts the element currently at that position (if any) and
         * any subsequent elements to the right (adds one to their indices).
         *
         * @param index index at which the specified element is to be inserted
         * @param element element to be inserted
         * @throws IndexOutOfBoundsException {@inheritDoc}
         */
        public void add(int index, E element) {
            rangeCheckForAdd(index);
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);
            elementData[index] = element;
            size++;
        }

    4.addAll(Collection<? extends E> c) 和 addAll(int index, Collection<? extends E> c):将特定 Collection 中的元素添加到 Arraylist 末尾。

    /**
         * Appends all of the elements in the specified collection to the end of
         * this list, in the order that they are returned by the
         * specified collection's Iterator.  The behavior of this operation is
         * undefined if the specified collection is modified while the operation
         * is in progress.  (This implies that the behavior of this call is
         * undefined if the specified collection is this list, and this
         * list is nonempty.)
         *
         * @param c collection containing elements to be added to this list
         * @return <tt>true</tt> if this list changed as a result of the call
         * @throws NullPointerException if the specified collection is null
         */
        public boolean addAll(Collection<? extends E> c) {
            Object[] a = c.toArray();
            int numNew = a.length;
            ensureCapacityInternal(size + numNew);  // Increments modCount
            System.arraycopy(a, 0, elementData, size, numNew);
            size += numNew;
            return numNew != 0;
        }
        /**
         * Inserts all of the elements in the specified collection into this
         * list, starting at the specified position.  Shifts the element
         * currently at that position (if any) and any subsequent elements to
         * the right (increases their indices).  The new elements will appear
         * in the list in the order that they are returned by the
         * specified collection's iterator.
         *
         * @param index index at which to insert the first element from the
         *              specified collection
         * @param c collection containing elements to be added to this list
         * @return <tt>true</tt> if this list changed as a result of the call
         * @throws IndexOutOfBoundsException {@inheritDoc}
         * @throws NullPointerException if the specified collection is null
         */
        public boolean addAll(int index, Collection<? extends E> c) {
            rangeCheckForAdd(index);
            Object[] a = c.toArray();
            int numNew = a.length;
            ensureCapacityInternal(size + numNew);  // Increments modCount
            int numMoved = size - index;
            if (numMoved > 0)
                System.arraycopy(elementData, index, elementData, index + numNew,
                                 numMoved);
            System.arraycopy(a, 0, elementData, index, numNew);
            size += numNew;
            return numNew != 0;
        }

    在 ArrayList 的存储方法,其核心本质是在数组的某个位置将元素添加进入。但其中又会涉及到关于数组容量不够而增长等因素。

    读取

    这个方法就比较简单了,ArrayList 能够支持随机访问的原因也是很显然的,因为它内部的数据结构是数组,而数组本身就是支持随机访问。该方法首先会判断输入的index值是否越界,然后将数组的 index 位置的元素返回即可。

    /**
    * Returns the element at the specified position in this list.
    *
    * @param  index index of the element to return
    * @return the element at the specified position in this list
    * @throws IndexOutOfBoundsException {@inheritDoc}
    */
    public E get(int index) {
        rangeCheck(index);
        return (E) elementData[index];
    }
    private void rangeCheck(int index) {
        if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    删除

    ArrayList 提供了根据下标或者指定对象两种方式的删除功能。需要注意的是该方法的返回值并不相同,如下:

    /**
         * Removes the element at the specified position in this list.
         * Shifts any subsequent elements to the left (subtracts one from their
         * indices).
         *
         * @param index the index of the element to be removed
         * @return the element that was removed from the list
         * @throws IndexOutOfBoundsException {@inheritDoc}
         */
        public E remove(int index) {
            rangeCheck(index);
            modCount++;
            E oldValue = elementData(index);
            int numMoved = size - index - 1;
            if (numMoved > 0)
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            elementData[--size] = null; // Let gc do its work
            return oldValue;
        }
    /**
         * Removes the first occurrence of the specified element from this list,
         * if it is present.  If the list does not contain the element, it is
         * unchanged.  More formally, removes the element with the lowest index
         * <tt>i</tt> such that
         * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
         * (if such an element exists).  Returns <tt>true</tt> if this list
         * contained the specified element (or equivalently, if this list
         * changed as a result of the call).
         *
         * @param o element to be removed from this list, if present
         * @return <tt>true</tt> if this list contained the specified element
         */
        public boolean remove(Object o) {
            if (o == null) {
                for (int index = 0; index < size; index++)
                    if (elementData[index] == null) {
                        fastRemove(index);
                        return true;
                    }
            } else {
                for (int index = 0; index < size; index++)
                    if (o.equals(elementData[index])) {
                        fastRemove(index);
                        return true;
                    }
            }
            return false;
        }

    注意:从数组中移除元素的操作,也会导致被移除的元素以后的所有元素的向左移动一个位置。

    调整数组容量

    从上面介绍的向 ArrayList 中存储元素的代码中,我们看到,每当向数组中添加元素时,都要去检查添加后元素的个数是否会超出当前数组的长度,如果超出,数组将会进行扩容,以满足添加数据的需求。数组扩容有两个方法,其中开发者可以通过一个 public 的方法ensureCapacity(int minCapacity)来增加 ArrayList 的容量,而在存储元素等操作过程中,如果遇到容量不足,会调用priavte方法private void ensureCapacityInternal(int minCapacity)实现。

    public void ensureCapacity(int minCapacity) {
            if (minCapacity > 0)
                ensureCapacityInternal(minCapacity);
        }
        private void ensureCapacityInternal(int minCapacity) {
            modCount++;
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
        /**
         * Increases the capacity to ensure that it can hold at least the
         * number of elements specified by the minimum capacity argument.
         *
         * @param minCapacity the desired minimum capacity
         */
        private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 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);
        }

    从上述代码中可以看出,数组进行扩容时,会将老数组中的元素重新拷贝一份到新的数组中,每次数组容量的增长大约是其原容量的 1.5 倍(从int newCapacity = oldCapacity + (oldCapacity >> 1)这行代码得出)。这种操作的代价是很高的,因此在实际使用时,我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时,要在构造 ArrayList 实例时,就指定其容量,以避免数组扩容的发生。或者根据实际需求,通过调用ensureCapacity 方法来手动增加 ArrayList 实例的容量。

    Fail-Fast 机制

    ArrayList 也采用了快速失败的机制,通过记录 modCount 参数来实现。在面对并发的修改时,迭代器很快就会完全失败,而不是冒着在将来某个不确定时间发生任意不确定行为的风险。 关于 Fail-Fast 的更详细的介绍,我在之前将 HashMap 中已经提到。

    转载于:https://www.cnblogs.com/fightingcode/p/11229998.html

    展开全文
  • ArrayList 底层实现原理

    2021-06-08 13:54:06
    ArrayList 底层实现原理 本文基于 JDK 11 讲解;©CopyRight 思思不羡仙;Date: 2021-6 1. 成员变量 private static final int DEFAULT_CAPACITY = 10; 构造函数数值缺省时默认大小 private static final ...

    本文基于 JDK 11 讲解;©CopyRight 思思不羡仙;Date: 2021-6

    1. 成员变量

    • private static final int DEFAULT_CAPACITY = 10; 构造函数数值缺省时默认大小

    • private static final Object[] EMPTY_ELEMENTDATA = {}; 当构造函数指出大小为0时将其赋值给 elemetData 数组

    • private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; 当构造函数未指出大小时将其赋值给 elemetData 数组

    • transient Object[] elemetData; ArrayList 底层数据结构(指定不被序列化的对象数组)

    • private int size; 实际ArrayList中存放的元素的个数,默认为0个元素

    • private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE – 8; 对象数组的最大数组容量为 Integer.MAX_VALUE – 8

    2. 构造方法

    无参构造

    public ArrayList() {
    	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    

    此处将 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 赋值给了 elementData,为何不使用 EMPTY_ELEMENTDATA ,原因在于后续为了区别第一次调用 add 方法进行数组扩增时的大小,后文将详细解释

    有参构造

    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: "+ initialCapacity);
    	}
    }
    

    此处的 initialCapacity 为期望设置的 ArrayList 数组大小,由于是用户输入,故需要判断其值是否符合要求,若大于0则直接创建容量为 initialCapacity 的新数组,如果等于0将 EMPTY_ELEMENTDATA 赋值给 elementData ,若小于0则直接抛出异常

    3. 添加元素

    // 公有add方法
    public boolean add(E e) {
    	modCount++;
    	add(e, elementData, size);
    	return true;
    }
    
    // 私有add方法
    private void add(E e, Object[] elementData, int s) {
    	if (s == elementData.length){
            elementData = grow();
        }
    	elementData[s] = e;
    	size = s + 1;
    }
    

    ​ 此处不难发现,用户调用公有add方法时主要完成了三件事,将 modCount 增加一(迭代时,将 expectedModCount 设为 modCount,若迭代过程中对集合进行了操作,易知 expectedModCount 与 modCount 数值不等,则会抛出 ConcurrentModificationException 异常),在私有 add 方法中,首先判断长度是否与实际大小相同,如果相同则调用 grow 方法进行扩增,否则将 elementData 最后一个空位置填入需要添加的元素,并将实际大小加一

    4. 扩容机制

    private Object[] grow(int minCapacity) {
    	return elementData = Arrays.copyOf(elementData, newCapacity(minCapacity));
    }
    
    private Object[] grow() {
    	return grow(size + 1);
    }
    

    ​ 书接上回,当实际大小与对象数组大小相同时调用扩增方法 grow 后,grow 方法会调用 newCapacity 方法进行扩增,并传入最小容量为 size + 1,并调用Arrays.copyOf 方法将原数组复制至扩增的新数组

    private int newCapacity(int minCapacity) {
    	int oldCapacity = elementData.length;
    	int newCapacity = oldCapacity + (oldCapacity >> 1);
    	if (newCapacity - minCapacity <= 0) {
           if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
               return Math.max(DEFAULT_CAPACITY, minCapacity);
           }  
           if (minCapacity < 0){
               throw new OutOfMemoryError();
           }      
           return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0) ? newCapacity : hugeCapacity(minCapacity);
    }
    
    private static int hugeCapacity(int minCapacity) {
    	if (minCapacity < 0){
    		throw new OutOfMemoryError();
    	}
    	return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }
    
    

    说明:二进制下使用 >>(右移运算符)相当于十进制除以 2

    此处的 newCapacity 方法将新容量设为(还未扩增)原对象数组长度的 1.5 倍后进行了三个判断,我们逐个说明:

    • 判断扩增是否足够?
      • 是:进行下一步操作
      • 否:是否超出最大值 MAX_ARRAY_SIZE,如果没有则直接赋值为所需容量,如果超出则调用 hugeCapacity 方法
    • 判断是否为初始化还未添加元素的数组?
      • 此处回答了为何需要单独设立两个空的对象数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATAEMPTY_ELEMENTDATA,如果 elementData 为前者的地址值,则说明是调用的无参构造方法,第一次扩增若放入的数据小于10,则直接扩增为10,反之扩增至所需容量最小值(此处不一定是 grow方法调用的该方法,也可以是一次添加多个元素的方法,故这样写提高通用性),如果是指定了大小的并且小于指定大小,则直接扩增至所需容量最小值
    • 判断最小容量是否小于 0 ?
      • 是:说明内存溢出了(请自行了解),抛出 OutOfMemoryError 异常
      • 否:返回最小容量

    5. 查找元素

    indexOf(Object o) 方法

    public int indexOf(Object o) {
    	return indexOfRange(o, 0, size);
    }
    
    int indexOfRange(Object o, int start, int end) {
    	Object[] es = elementData;
    	if (o == null) {
    		for (int i = start; i < end; i++) {
    			if (es[i] == null) {
    				return i;
    			}
            }
        } else {
    		for (int i = start; i < end; i++) {
    			if (o.equals(es[i])) {
    				return i;
    			}
    		}
    	}
        return -1;
    }
    

    此方法会调用 indexOfRange 方法来查找 Object o 的位置,分两种情况:

    1. o 为 null ,则直接与 null 比较
    2. o 不为 null ,则调用 o 的 equals 方法

    直到找到后返回元素位置,否则返回 -1

    get(int index) 方法

    public E get(int index) {
    	Objects.checkIndex(index, size);
        return elementData(index);
    }
    

    此方法返回指定 List 下标的对象,首先先检查传入 index 数值是否在 [0,size) 中(Objects.checkIndex 方法做的就是这件事),如果不抛出异常 IndexOutOfBoundsException 则返回数组的第 index 位元素

    6. 删除元素

    public E remove(int index) {
    	Objects.checkIndex(index, size);
    	final Object[] es = elementData;
    	@SuppressWarnings("unchecked") E oldValue = (E) es[index];
    	fastRemove(es, index);
    	return oldValue;
    }
    
    private void fastRemove(Object[] es, int i) {
    	modCount++;
    	final int newSize;
    	if ((newSize = size - 1) > i){
            System.arraycopy(es, i + 1, es, i, newSize - i);
        }
    	es[size = newSize] = null;
    }
    

    执行 remove 方法时,首先检查下标是否正确,如果正确,则调用 fastRemove 方法进行删除操作,fastRemove 方法的思路就是将需要删除的后面的元素全部向前移动一个元素位置,然后将最后一个元素(等于前一个元素)赋值为 null

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,034
精华内容 413
关键字:

arraylist底层实现原理