devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【ArrayList】JDK1.8源码详细注释 以及如何实现线程安全的链表

作者：IT小白 | 2024-08-14 20:18:48

赞

踩

【ArrayList】JDK1.8源码详细注释 以及如何实现线程安全的链表

ArrayList(JDK8)

  • ArrayList有四个内部类，成员内部类Itr，成员内部类ListItr，静态内部类SubList，ArrayListSpliterator（暂时用不到）
  • Itr是Iterator的实现类，支持正向遍历，ArrayList的iterator方法返回一个Itr对象
  • ListItr是ListIterator的实现类，支持双向遍历，ArrayList的listIterator方法返回一个ListIterator类对象

Itr

  1. 增强 for 遍历数组时, 被编译成普通 for 循环, 增强 for 遍历集合时, 被编译成使用 Iterator; 无论是数组还是集合, 只用增强 for 都无法修改原本引用的指向;

  2. 单步迭代中, 不允许多次调用迭代器的 remove 方法; 逻辑上来说, 你迭代一次, 当然只能判断当前的对象是不是需要被删除, 干嘛要多次删除? 其次, 这样也能让迭代器的代码逻辑更简洁, 避免很多边界条件的判断, 也能避免很多潜在的错误;

  3. 如果要通过循环删除 List 中的所有元素, 可以这样做

    for(int i = 0; i < list.size(); i++){
    list.remove(i);
    i--;
}

// 或者
// removeIf 的本质就是迭代器实现的;
list.removeIf(i->true);

// 或者通过迭代器;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
// ArrayList的
public Iterator<E> iterator() {
	return new Itr();
}
// 作为ArrayList的成员内部类
private class Itr implements Iterator<E> {
	int cursor;       // index of next element to return
	int lastRet = -1; // index of last element returned; -1 if no such
    // 显式赋值，让自己的expectedModCount = ArrayList.this.modCount
    // 在内部类的成员方法和构造函数中，隐含了ArrayList.this和this传参
	int expectedModCount = modCount;

	// prevent creating a synthetic constructor
	Itr() {}

	public boolean hasNext() {
        // ArrayList.this.size
    	return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        // 创建一个引用指向外围类对象的底层数组，方便后面使用
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

	public void remove() {
	    if (lastRet < 0)
	        throw new IllegalStateException();
	    checkForComodification();
	    try {
            // 局部内部类对象依附于外围类对象而存在，持有外围类对象指针ArrayList.this
            // 这里修改了所依附的外围类对象arrayList的modCount
	        ArrayList.this.remove(lastRet);
            // 删除时cursor要往前移动一位
	        cursor = lastRet;
            // 防止连续删除
	        lastRet = -1;
            // 更新自己的modCount
	        expectedModCount = modCount;
	    } catch (IndexOutOfBoundsException ex) {
	        throw new ConcurrentModificationException();
	    }
	}

	final void checkForComodification() {
	    if (modCount != expectedModCount)
	        throw new ConcurrentModificationException();
	}
}

  • 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

sublist

public List<E> subList(int fromIndex, int toIndex) {
	subListRangeCheck(fromIndex, toIndex, size);
	return new SubList<>(this, fromIndex, toIndex);
}

// 本身也实现了AbstracList，有add，remove等等常见方法，不再列出
// 但是要记住它的add，remove等等方法修改的都是源ArrayList！
// 重点看iterator()方法返回的匿名内部类对象
private static class SubList<E> extends AbstractList<E> implements RandomAccess {
    // 如果是从ArrayList投影来的，让root指向源集合
	private final ArrayList<E> root;
    // 如果是Sublist又subList来的，让parent = 源Sublist, root = parent.root
    // 从SubList再截取时，行为比较特殊，会继续向上去找源ArrayList，迭代器依旧在ArrayList上进行，像        双亲委派模型
	private final SubList<E> parent;
    // 在源中的偏移量，例如从ArrayList第二个元素截取，offset = 1
	private final int offset;
    // sublist的长度
	private int size;
	
    // 从ArrayList截取Sublist
	public SubList(ArrayList<E> root, int fromIndex, int toIndex) {
	    this.root = root;
	    this.parent = null;
	    this.offset = fromIndex;
	    this.size = toIndex - fromIndex;
        // this.modCount是从AbstractList继承来的
	    this.modCount = root.modCount;
	}

    // Sublist自己可以继续sublist
    public List<E> subList(int fromIndex, int toIndex) {
	    subListRangeCheck(fromIndex, toIndex, size);
	    return new SubList<>(this, fromIndex, toIndex);
	}
	
    // 从Sublist截取
	private SubList(SubList<E> parent, int fromIndex, int toIndex) {
         // 无论subList几次，root始终指向源ArrayList
	    this.root = parent.root;
	    this.parent = parent;
        // 记录的是相对于源ArrayList的偏移量
	    this.offset = parent.offset + fromIndex;
	    this.size = toIndex - fromIndex;
        // this.modCount = 上级modCount = 。。。最终 = 源ArrayList的modCount 
	    this.modCount = parent.modCount;
	}
    
    // SubList的remove
	public E remove(int index) {
		Objects.checkIndex(index, size);
		checkForComodification();
		E result = root.remove(offset + index);
		// 更新自己的modCount和root的一样， 自己的size-1
		updateSizeAndModCount(-1);
		return result;
	}
    
    // Sublist无论是iterator还是listIterator，返回的都是listIterator子类对象
	public Iterator<E> iterator() {
        // 调用从AbstractList继承的listItoreator
        // 其实现是调用listIterator(0)
	    return listIterator();
	}
	
    // index = 0
	public ListIterator<E> listIterator(int index) {
	    checkForComodification();
	    rangeCheckForAdd(index);
        // 是Sublist的局部内部类
        // 只列出了next方法，其余的方法大同小异，最终也都是在原ArrayList上操作
	    return new ListIterator<E>() 
        {	
	        int cursor = index;
	        int lastRet = -1;
            // 也就是源ArrayList的modCount
	        int expectedModCount = SubList.this.modCount;

	        public boolean hasNext() {
	            return cursor != SubList.this.size;
	        }

	        @SuppressWarnings("unchecked")
	        public E next() {
                // 检查并发修改异常时也是和ArrayList对比
	            checkForComodification();
	            int i = cursor;
	            if (i >= SubList.this.size)
	                throw new NoSuchElementException();
	            Object[] elementData = root.elementData;
	            if (offset + i >= elementData.length)
	                throw new ConcurrentModificationException();
	            cursor = i + 1;
                // 真正遍历时实际上是用 offset + cursor 去遍历源集合
	            return (E) elementData[offset + (lastRet = i)];
	        }

	       
	        public void remove() {
	            if (lastRet < 0)
	                throw new IllegalStateException();
	            checkForComodification();

	            try {
                    // 调用外围类Sublist的remove方法，最终还是修改了原ArrayList
	                SubList.this.remove(lastRet);
	                cursor = lastRet;
	                lastRet = -1;
	                expectedModCount = SubList.this.modCount;
	            } catch (IndexOutOfBoundsException ex) {
	                throw new ConcurrentModificationException();
	            }
	        }

	        final void checkForComodification() {
	            if (root.modCount != expectedModCount)
	                throw new ConcurrentModificationException();
	        }
	    }; // return匿名内部类对象
	} // public ListIterator<E> listIterator(int index)
} // Sublist

  • 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
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120

容量

  • add 和 addAll 会检查容量是否够用，即 size 是否已经 ==capacity 或者能否放得下加入的集合，不够的时候才扩容;

  • 无论add还是 addAll, 扩容机制都是在需要增长到的容量和原容量1.5倍之间选择大的进行扩容；除了无参构造首次扩容有些特殊, 直接扩容到10 ;

  • 如果是无参构造创建的ArrayList，首次添加第一个元素时，扩容到10，如果首次直接使用 addAll 添加集合c，会有特殊判断, 扩容到 max { c.length , 10 }

  • 如果是有参构造，指定多少就立即分配多少, 指定 size == 0 时除外

/**
* 首先区分容量capacity(底层数组能放多少)
* 和大小size(集合的逻辑大小，底层数组实际使用了多少)
*/

// 默认容量10
private static final int DEFAULT_CAPACITY = 10;

// 
private static final Object[] EMPTY_ELEMENTDATA = {};

// 
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};


transient Object[] elementData;


private int size;

// 1. 无参构造时，使用空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA作为底层数组，初次扩容时作为标记
//		初始容量实际上为0
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 2. 有参构造时，如果传入的容量为0，底层使用空数组EMPTY_ELEMENTDATA，初次扩容时和	
//			DEFAULTCAPACITY_EMPTY_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: "+ initialCapacity);
    }
}


// 1. 无参构造首次添加元素时elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; size = 0；	
public boolean add(E e) {
	modCount++;
	add(e, elementData, size);
	return true;
}

// 1. if 条件满足，调用grow扩容
private void add(E e, Object[] elementData, int s) {
	if (s == elementData.length)
		elementData = grow();
	elementData[s] = e;
}

public boolean addAll(Collection<? extends E> c) {
	Object[] a = c.toArray();
	modCount++;
	int numNew = a.length;
	if (numNew == 0)
	    return false;
	Object[] elementData;
	final int s;
    // 如果elementData不足以放下所有元素，扩容
	if (numNew > (elementData = this.elementData).length - (s = size))
	    elementData = grow(s + numNew);
	System.arraycopy(a, 0, elementData, s, numNew);
	size = s + numNew;
	return true;
}

// 1. 调用grow(1) 
private Object[] grow() {
	return grow(size + 1);
}

// 1.1 如果是add方法添加单个元素，minCapacity = 1
// 1.2 如果是addAll方法添加集合c，minCapacity = size + c.length
private Object[] grow(int minCapacity) {
    // 1. oldCapacity = 0
    int oldCapacity = elementData.length;
    // 2. 首次添加单个元素，minCapacity = 1，oldCapacity = 0； minCapacity是指总容量最少为多少
    //		minGrowth = 1； old/2 = 0； 最终增长1
    //		再加一个元素， minGrowth=1；old/2 = 0， 增长1，size=2
    // 		再加，只要是add(E e)，minGrowth就是1， old/2 = 1； 增长1， size = 3
    //		再加，加1； 再加，加2， 直到第五次添加元素， 开始加 > 1
    //	而如果添加多个元素，要对比添加元素个数和原本容量的0.5倍哪个更大
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = 
            ArraysSupport.newLength(oldCapacity,
               					  minCapacity - oldCapacity, /* minimum growth */
                                    oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        // 1. 在minCapacity 和 DEFAULT_CAPACITY(10) 之间选大的那个
        // 		这里只会在无参构造的ArrayList首次扩容的时候执行到
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

// ArraysSupport类
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
	// 在最小需要增量和0.5倍原容量中选择大的那个，加上原容量，作为新容量的大小
    // 例如原容量为10，addAll添加了一个长度为6的集合，那么传入的oldLength = 10；
    // minGrowth = 6，此方法返回 10 + 6
	int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
	if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
	    return prefLength;
	} else {
	    // put code cold in a separate method
	    return hugeLength(oldLength, minGrowth);
	}
}

// 可以手动调用ensureCapacity来无条件扩容，参数是总容量，不是要扩展的容量
// 手动调用时，如果给出的总容量小于现有容量，do nothing
// 如果当前是刚用无参构造构造出的ArrayList还没有扩容过，而且给出的总容量小于等于10的话，不会扩容
// 因为多此一举，反正等到添加第一个元素的时候就会扩容到10
public void ensureCapacity(int minCapacity) {
	if (minCapacity > elementData.length
	    && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
	         && minCapacity <= DEFAULT_CAPACITY)) {
	    modCount++;
	    grow(minCapacity);
	}
}


  • 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
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125

线程安全的 List

一 自己加 Synchronized 进行控制

二 CopyOnWriteArrayList

写时复制的 List; 非常适合读多写少又要求线程安全的场景;

其基本工作原理是，当对列表进行写操作（如添加、删除、更新元素）时，它会 new 数组 + System.ArrayCopy , 创建一个底层数组的副本，然后在新数组上执行写操作。修改完成后，用副本替换掉原有的数组。

其底层数组由 volatile 修饰, 保证可见性;

CopyOnWriteArrayList 的迭代器在迭代的时候，如果数组内容被修改了，CopyOnWriteArrayList 不会报 ConcurrentModificationException 的异常，因为迭代器使用的依然是旧数组，只不过迭代的内容可能已经过时了。迭代器并不支持 remove 方法;

原理是: 创建 COWIterator 的时候, 会将底层数组的引用传进入, 这样, 即使有其他线程更换了底层数组, 也不会影响到当前的迭代器;

remove 方法还是会加锁, 使用的是 ReentrantLock, 整个 list 对象就一个;

三 Collections.synchronizedList()

对 get set add 等等这些方法都加了 synchronized, 和我们自己控制, 没啥区别; synchronized 作用的对象是链表本身;

public E get(int index) {
	synchronized (mutex) {return list.get(index);}
}

  • 1
  • 2
  • 3

需要注意, 拿到 Iterator 进行遍历的时候, 必须手动保证线程安全, 比如可以用 synchronized(list);

不然还是会并发修改异常;

synchronized (list) {
    Iterator i = list.iterator(); // Must be in synchronized block
    while (i.hasNext())
        foo(i.next());
}

  • 1
  • 2
  • 3
  • 4
  • 5
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/980621
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号