认识达内从这里开始

昆明IT培训的老师给关于ArrayList的实现和原理，做一个记录和总结吧

public class arraylist<E> {

/**

* 存放集合的元素

* 

*/

private transient Object[] elementData;

/**元素的大小*/

private int size;

定义了一个泛型类，一个object的数组和一个私有变量来记录该集合的元素数量，

1    /**

2     *根据指定大小初始化

3     * @param initialCapacity

4     */

5    public arraylist(int initialCapacity){

6        super();

7        if(initialCapacity<=0){

8            //抛异常

9            throw new IllegalArgumentException("初始化参数不能小于0");

10        }else{

11            //初始化数组

12            this.elementData=new Object[initialCapacity];

13        }

14    }

15    /**

16     *默认初始化

17     */

18    public arraylist(){

19        this(10);

20    }

21    /**

22     *根据一个集合类初始化

23     * @param c一个必须继承了Collection接口的类

24     */

25    public arraylist(Collection<? extends E> c){

26        //初始化

27        elementData=c.toArray();

28        size=elementData.length;

29        //如果不是任意类型的数组就转换Objec类型

30        if (elementData.getClass() != Object[].class){

31            elementData=Arrays.copyOf(elementData,size, Object[].class);

32        }

33    }

34    

3个初始化方法，根据默认大小进行数组的初始化，给定大小初始化和传递一个继承了Collection集合接口的类进行转换赋值初始化

1 /**

2     *扩容集合

3     * @param minCapacity

4     */

5    public void ensureCapacity(int minCapacity){

6        /**当前数组的大小 */

7        int oldCapacity = elementData.length; 

8        if (minCapacity > oldCapacity) {

9            /**

10             * oldData虽然没有被使用，但是这是关于内存管理的原因和Arrays.copyOf()方法不是线程安全

11             * oldData在if的生命周期内引用elementData这个变量，所以不会被GC回收掉

12             *当Arrays.copyOf()方法在把elementData复制到newCapacity时，就可以防止新的内存或是其他线程分配内存是elementData内存被侵占修改

13             *当结束是离开if，oldData周期就结束被回收

14             */

15            Object oldData[] = elementData; 

16            int newCapacity = (oldCapacity * 3)/2 + 1; //增加50%+1

17                if (newCapacity < minCapacity) 

18                    newCapacity = minCapacity; 

19          //使用Arrays.copyOf把集合的元素复制并生成一个新的数组

20          elementData = Arrays.copyOf(elementData, newCapacity); 

21        } 

22    }

这是一个核心的方法，集合的扩容，其实是对数组的扩容，minCapacity集合的大小，进行对比判断是否应该进行扩容，使用了Arrays.copyOf()方法进行扩容，

这个方法把第一个参数的内容复制到一个新的数组中，数组的大小是第二个参数，并返回一个新的数组，关于oldData的变量上文有详细的注释

1 /**

2     *检查索引是否出界

3     * @param index

4     */

5    private void RangeCheck(int index){

6        if(index > size || index < 0){

7            throw new IndexOutOfBoundsException("下标超出,Index: " + index + ", Size: " +size);

8        }

9    }

一个下标的检索是否出1 /**

2     *添加元素

3     *将指定的元素添加到集合的末尾

4     * @param e添加的元素

5     * @return

6     */

7    public boolean add(E e){

8        ensureCapacity(size+1);

9        elementData[size]=e;

10        size++;

11        return true;

12    }

添加元素，先进行扩容，在赋值，然后元素加一，注意size+1字段size并没有加一，这里进行的是算术的运算，所以在后面才需要进行自增

1 /**

2     *添加元素

3     *将元素添加到指定的位置

4     * @param index指定的索引下标

5     * @param element元素

6     * @return

7     */

8    public boolean add(int index, E element){

9        RangeCheck(index);

10        ensureCapacity(size+1);

11        //将elementData中从Index位置开始、长度为size-index的元素， 

12        //拷贝到从下标为index+1位置开始的新的elementData数组中。 

13        //即将当前位于该位置的元素以及所有后续元素右移一个位置。

14        System.arraycopy(elementData, index, elementData, index+1, size-index);

15        elementData[index]=element;

16        size++;//元素加一

17        return true;

18    }

这里不同的是System.arraycopy(elementData, index, elementData, index+1, size-index);

这是一个c的内部方法，这个也是整个ArrayList的核心所在，也Arrays.copyOf()的内部实现原理

1 /**

2     *添加全部元素

3     * 按照指定collection的迭代器所返回的元素顺序，将该collection中的所有元素添加到此列表的尾部。 

4     * @param c

5     * @return

6     */

7    public boolean addAll(Collection < ? extends E>c){

8        Object[] newElement=c.toArray();

9        int elementLength=newElement.length;

10        ensureCapacity(size+elementLength);

11        //从newElement 0的下标开始，elementLength个元素，elementData size的下标

12        System.arraycopy(newElement, 0, elementData, size, elementLength);

13        size+=elementLength;

14        return elementLength!=0;

15    }

基本上其他方法都只是根据不同的情况进行不同的处理，比如通过接口把数据对象传递进来然后获取长度进行扩容，在把数据使用System,arraycopy复制到新的数组中

1 /**

2     *指定位置，添加全部元素

3     * @param index插入位置的下标

4     * @param c插入的元素集合

5     * @return

6     */

7    public boolean addAll(int index, Collection<? extends E> c){

8        if(index > size || index < 0){

9            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " +size);

10        }

11        Object[] newElement=c.toArray();

12        int elementLength=newElement.length;

13        ensureCapacity(size+elementLength);

14        int numMoved=size-index;

15        //判断插入的位置是否在数组中间

16        if(numMoved>0){

17            //把index插入位置的后面的所有元素往后移

18            //elementData index下标开始的numMoved个元素插入到elementData的index+elementLength位置

19            System.arraycopy(elementData, index, elementData, index+elementLength, umMoved);

20        }

21        //把newElement里从0开始的elementLength个元素添加到elementData index开始的位置

22        System.arraycopy(newElement, 0, elementData, index, elementLength);

23        size += elementLength;

24        return elementLength != 0;

25    }

26    

27    /**

28     *指定下标赋值

29     * @param index

30     * @param element

31     * @return

32     */

33    public E set(int index,E element){

34        RangeCheck(index);

35        E oldElement=(E)elementData[index];

36        elementData[index]=element;

37        return oldElement;

38    }

39    

40    /**

41     *根据下标取值

42     * @param index

43     * @return

44     */

45    public E get(int index){

46        RangeCheck(index);

47        return (E)elementData[index];

48    }

49    

50    /**

51     *根据下标移除元素

52     * @param index

53     */

54    public E remove(int index){

55        RangeCheck(index);

56        E oldElement=(E)elementData[index];

57        /**移除的下标后面的元素数量 */

58        int numMoved=size-index-1;

59        //如果在数组范围内就进行移动

60        if(numMoved>0)

61            System.arraycopy(elementData, index+1, elementData, index, numMoved);

62        //移除

63        elementData[--size]=null;

64        return oldElement;

65    }

66    

67    /**

68     *根据元素移除

69     * @param obj

70     * @return

71     */

72    public boolean remove(Object obj){

73        //Arraylist允许存放null,所以也要进行判断处理

74        if(obj==null){

75            for(int index=0;index<size;index++){

76                if(elementData[index]==null){

77                     remove(index);

78                     return true;

79                }

80            }

81        }else{

82            for(int index=0;index<size;index++){

83                if(obj.equals(elementData[index])){

84                     remove(index);

85                     return true;

86                }

87            }

88        }

89        return false;

90    }

91    

92    /**

93     *根据下标移除指定范围内的元素

94     * @param fromIndex开始

95     * @param toIndex结束

96     */

97    protected void removeRange(int fromIndex, int toIndex){

98        RangeCheck(fromIndex);

99        RangeCheck(toIndex);

100        //要移动的元素数

101        int numMoved = size - toIndex;

102        //把toIndex后面的元素移动到fromIndex

103        System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);

104        //要移除的元素数量

105        int newSize=size-(toIndex-fromIndex);

106        while(size!=newSize){

107            elementData[--size]=null;

108        }

109    }

110    

111    /**

112     *把数组容量调整到实际的容量

113     */

114    public void trimToSize(){

115        int leng=elementData.length;

116        if(size<leng){

117            Object[] old=elementData;

118            elementData=Arrays.copyOf(elementData, size);

119        }

120    }

121    /**

122     *把集合元素转换成数组

123     * @return

124     */

125    public Object[] toArray(){

126        return Arrays.copyOf(elementData, size);

127    }

128    

129    public <T>T[] toArray(T[] a){

130        if(a.length<size){

131            return (T[]) Arrays.copyOf(elementData,size, a.getClass());

132        }

133        //把集合元素复制到a数组中

134        System.arraycopy(elementData, 0, a, 0, size);

135         if (a.length > size){

136             for(int index=size;index<a.length;index++){

137                 a[index] = null;

138             }

139         }

140          return a; 

141    }

基本上都是对数组进行操作和使用c的方法进行赋值移动等，代码可以完美运行，这里昆明IT培训的老师提醒要注意的和难点就会是System,arraycopy和Arrayist.copy()这2个方法。