OnePotSake Blog
0%

ArrayList 底层原理

发表于 更新于 分类于 ， ， ， ，
本文字数： 6.8k 阅读时长 ≈ 6 分钟

ArrayList 底层原理

List作为有序集合的典型代表经常使用,但底层原理一直是看别人的总结,有道是实践出真知…

层级结构,数据结构

扩容机制,自身特点

通过idea 工具看出其层次结构

层次结构图

层次结构解析

Iterable:泛型迭代器接口,一共3个方法,无参数构造/foreach循环/spliterator(分割并行处理,效果比迭代器快)

Collection:集合常用接口.集成集合常用方法;

AbstractCollectior:具体实现collection接口,重点finishToArray方法,hugeCapacity方法.

hugeCapacity用于将元素复制到新的集合中.

hugeCapacity扩容代码,扩容为原有空间大小的1.5倍.

List: 继承原有Collection方法,同时扩展部分自己的具体实现操作(default 方法)

AbstractList: ArrayList 主要继承的类.其具体实现接口

以下接口并未有实际的实现方法,那为什么又要调用这些接口呢?

Randomaccess快速访问标记接口,无实现方法,有 这格个标记默认采用for循环遍历,效率比iteator快.

Serializable:实例化标记接口,所谓实例化是指在数据传输过程中需要将数据进行转换二进制方便网络传输,所以我们在写类时,一般进行网络通信的数据都会实现序列化.传输完成后根据序列化内容还可以进行反序列化,还原

Cloneable:拷贝标记接口,支持通过clone方法拷贝复制数据,数据的复制默认方式是浅拷贝形式.

具体属性:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Default initial capacity. 默认集合大小
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * Shared empty array instance used for empty instances. 用于共享空实例数据数组
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added. 用于共享空实例数据数组,(与上面类似有何用处?)
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
   数组数据缓冲区存储到ArrayList中,在初次未制定长度时将未空,第一次添加数据时,将扩容至10.
   由于是缓冲数据并未实现实例化方法.
 */
transient Object[] elementData; // non-private to simplify nested class access

/**
 * The size of the ArrayList (the number of elements it contains).
 *  
 * @serial
 */
private int size;

存储数据结构

从上看出底层采用Object[]数组存储,数组作为一个集合,我们知道数组在分配内存时是一块完整的区域,数据之间有顺序关系的.缺省值大小是10,而且这格数组是动态的,我们超过原有空间大小就要进行扩容.ArrayList是线程不安全的.在多线程环境下很容易进行验证.

通过一个线程向list 中添加元素,结果却各不相同,可见线程执行时各个ArrayList不可见

查找方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

E elementData(int index) {
        return (E) elementData[index];
}
-----------------------------------------------------------------------------------------
public E get(int index) {
            rangeCheck(index);
            // 多线程下 fail-fast机制,稍后说明 
            checkForComodification();
            return ArrayList.this.elementData(offset + index);
}

 private void checkForComodification() {
            if (ArrayList.this.modCount != this.modCount)
                throw new ConcurrentModificationException();
}

遍历方法,若采用for循环,则跟上面的获取方法是一致的.

1
2
3
4
5
6
default void forEach(Consumer<? super T> action) {
    Objects.requireNonNull(action);
    for (T t : this) {
        action.accept(t);
    }
}

新增(方法)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

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

private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
-----------------------------------------------------------------------------------------
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;
}
---------------------------------------------------------------------------------------- 
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;
}


public void add(E e) {
            checkForComodification();
            try {
                int i = cursor;
                ArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
}
----------------------------------------------------------------------------------------  public void add(int index, E e) {
            rangeCheckForAdd(index);
            checkForComodification();
            parent.add(parentOffset + index, e);
            this.modCount = parent.modCount;
            this.size++;
}
----------------------------------------------------------------------------------------   
 public boolean addAll(Collection<? extends E> c) {
            return addAll(this.size, c);
        }
----------------------------------------------------------------------------------------
public boolean addAll(int index, Collection<? extends E> c) {
            rangeCheckForAdd(index);
            int cSize = c.size();
            if (cSize==0)
                return false;

            checkForComodification();
            parent.addAll(parentOffset + index, c);
            this.modCount = parent.modCount;
            this.size += cSize;
            return true;
}

修改

1
2
3
4
5
6
7
public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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; // clear to let GC do its work

    return oldValue;
}
-------------感谢您的阅读,若您觉得文章有纰漏欢迎沟通讨论-------------