郑州做网站排名公司哪家好,led高端网站建设,织梦网站排行榜,wordpress无法更新本篇内容包括#xff1a;ArrayList 概述、ArrayList 的扩容机制#xff08;包含源码部分#xff09;、如何在遍历 ArrayList 时正确的移除一个元素、ArrayList 的构造方法及常用方法、关于 Array 与 ArrayList 的区别、关于 CopyOnWriteArrayList、关于 Fail Fast 与 Fail S… 本篇内容包括ArrayList 概述、ArrayList 的扩容机制包含源码部分、如何在遍历 ArrayList 时正确的移除一个元素、ArrayList 的构造方法及常用方法、关于 Array 与 ArrayList 的区别、关于 CopyOnWriteArrayList、关于 Fail Fast 与 Fail Safe 机制 文章目录一、ArrayList 概述二、ArrayList 的扩容1、ArrayList 的扩容机制源码2、在遍历 ArrayList 时移除一个元素三、ArrayList 的使用1、构造方法2、常用方法四、相关知识点1、关于 Array 与 ArrayList 的区别2、关于 CopyOnWriteArrayList3、关于 Fail Fast4、关于 Fail Safe一、ArrayList 概述 ArrayList 是最常用的 List 实现类内部是通过数组实现的它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔当数组大小不满足时需要增加存储能力就要将已经有数组的数据复制到新的存储空间中。当从 ArrayList 的中间位置插入或者删除元素时需要对数组进行复制、移动、代价比较高。因此它适合随机查找和遍历不适合插入和删除。 ArrayList 是基于数组实现的相当于动态数组相当于动态数组其容量能动态增长类似于 C 语言中的动态申请内存动态增长内存。
ArrayList 的每个实例都有一个容量该容量是指用来存储列表元素的数组的大小。它总是大于等于列表的大小。随着向 ArrayList 中不断添加元素其容量也自动增长。自动增长会带来数据向新数组的重新拷贝因此如果可预知数据量的多少可在构造 ArrayList 时指定其容量。
ArrayList 在被添加大量元素前应用程序可以使用 ensureCapacity() 操作来指定 ArrayList 实例的容量这可以减少递增式再分配的数量。
ArrayList 是非线程安全的只能在单线程环境下使用多线程环境下可以考虑用 Collections.synchronizedList(List l) 函数返回一个线程安全的 ArrayList 类也可以使用 java.util.concurrent 并发包下的 CopyOnWriteArrayList 类。 二、ArrayList 的扩容
1、ArrayList 的扩容机制源码
ArrayList 底层是一个 Object 数组 elementData用于存放插入的数据
private transient Object[] elementData; // 存储ArrayList中的元素
/*** 定义元素个数*/
private int size();我们知道数组需要使用着一块连续的内存空间因此数组的大小一旦被规定就无法改变。那如果我们不断的往里面添加数据的话ArrayList 是如何进行扩容的呢
public boolean add(E e) {// 确认elementData容量是否足够ensureCapacityInternal(size 1); // 第一次调用add()方法时size0elementData[size] e;return true;}ArrayList 添加元素时会先调用 ensureCapacityInternal(int minCapacity) 方法对数组容量进行检查判断剩余空间是否足够不够时则进行扩容
private void ensureCapacityInternal(int minCapacity) {// 如果elementData为{}即第一次调用add(E e)重新定义minCapacity的值赋值为DEFAULT_CAPACITY10// 即第一次调用add(E e)方法时定义底层数组elementData的长度为10if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity Math.max(DEFAULT_CAPACITY, minCapacity);}// 判断是否需要扩容ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {modCount;// 第一次进入时minCapacity10,elementData.length0,对数组进行扩容// 之后再进入时minCapacitysize1elementData.length10(每次扩容后会改变)// 需要minCapacityelementData.length成立才能扩容if (minCapacity - elementData.length 0){grow(minCapacity);}
}ArrayList 通过 grow(minCapacity) 方法对数组进行扩容
private void grow(int minCapacity) {// 将数组长度赋值给oldCapacityint oldCapacity elementData.length;// 将oldCapacity右移一位再加上oldCapacity即相当于newCapacity1.5oldCapacity(不考虑精度损失)int newCapacity oldCapacity (oldCapacity 1);// 如果newCapacity还是小于minCapacity直接将minCapacity赋值给newCapacityif (newCapacity - minCapacity 0)newCapacity minCapacity;// 特殊情况newCapacity的值过大直接将整型最大值赋给newCapacity// 即newCapacityInteger.MAX_VALUEif (newCapacity - MAX_ARRAY_SIZE 0)newCapacity hugeCapacity(minCapacity);// 将elementData的数据拷贝到扩容后的数组elementData Arrays.copyOf(elementData, newCapacity);
}// 如果大于临界值进行整型最大值的分配
private static int hugeCapacity(int minCapacity) {if (minCapacity 0) {// overflowthrow new OutOfMemoryError();}return (minCapacity MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}总结ArrayList 在添加元素时会进行一个判断当「元素个数1 当前数组长度size 1 elementData.length」时进行扩容扩容后的数组大小是原大小的 1.5 倍oldCapacity (oldCapacity 1)。最后将旧数组进行复制调用 Arrays.copyof()再调用 System.arraycopy() 达到扩容的目的此时新旧列表的 size 大小相同但 elementData 的长度即容量不同。
2、在遍历 ArrayList 时移除一个元素
在遍历 ArrayList 时移除一个元素这是一个比较经典的面试题这里最常用的有 2 种方式
方式一在 for 循环中使用倒序遍历 remove 删除元素.
假设按照从 0 到 size-1 下标来删有相邻且相同的两个元素删除第一个数组长度会 -1 并且所有元素往前移动一位那么第二个就到第一个元素的位置此时控值 for 循环的下标 i 已经 1 相当于直接就跳过了第二个重复元素而倒叙可以避免此类情况。
方式二使用迭代器遍历 ArrayList 并删除元素推荐。
Eg
ListString strs new ArrayList();
strs.add(1)
strs.add(2)
strs.add(3)
strs.add(4)
strs.add(5)
strs.add(6)IteratorString iter strs.iterator();
while(iter.hasNext()) {if (iter.next().toString().equals(1)) {iter.remove();}
}
System.out.println(strs);三、ArrayList 的使用
1、构造方法
方法名方法说明public ArrayList()无参构造函数此构造函数用于创建一个空列表其初始容量足以容纳10个元素public ArrayList(int initialCapacity)此构造函数用于创建具有初始容量的空列表public ArrayList(Collection? extends E c)此构造函数用于创建包含指定集合的元素的列表
2、常用方法
方法名方法说明boolean add(E e)此方法将指定的元素追加到此列表末尾void add(int index, E element)此方法将指定的元素插入此列表中的指定位置boolean addAll(Collection? extends E c)此方法按指定集合迭代器的返回顺序将指定集合中所有元素加到列表末尾boolean addAll(int index, Collection? extends E c)此方法从指定位置开始将指定集合中的所有元素插入此列表E get(int index)此方法返回此列表中指定位置的元素E set(int index, E element)此方法返回此列表中指定位置的元素并使用参数中的元素进行替换E remove(int index)此方法返回此列表中指定位置的元素并删除此指定位置的元素boolean remove(Object o)此方法从该列表中删除指定元素的第一个匹配项如果存在void clear()此方法将从此列表中删除所有元素Object clone()此方法返回此ArrayList实例的浅表副本boolean contains(Object o)如果此列表包含指定的元素则此方法返回trueboolean isEmpty()如果此列表为空则此方法返回truevoid ensureCapacity(int minCapacity)此方法增加了此列表的容量int size()此方法返回此列表中的元素数Object[] toArray()此方法以适当的顺序从第一个元素到最后一个元素返回包含此列表中所有元素的数组T T[] toArray(T[] a)此方法以适当的顺序从第一个元素到最后一个元素返回包含此列表中所有元素的数组; 返回数组的运行时类型是指定数组的运行时类型void trimToSize()此方法将此ArrayList实例的容量修剪为列表的当前大小void sort(Comparator? super E c)此方法对列表内对象以指定方式进行排序ListE subList(int fromIndex, int toIndex)此方法将截取集合的一部分并返回一个List集合四、相关知识点
1、关于 Array 与 ArrayList 的区别
包含类型Array 既可以包含基本类型也可以包含对象类型而 ArrayList 只能包含对象类型。实例声明Array 作为变量在声明的时必须进行实例化至少得初始化数组的大小而 ArrayList 可以只是先声明。初始大小Array 对象创建后的数组大小是固定的而 ArrayList 的大小可以动态指定也就是说该对象的空间可以任意增加。方法特性Arraylist 提供了更多的方法和特性比如添加全部addAll()删除全部removeAll()返回迭代器iterator()等等。
2、关于 CopyOnWriteArrayList
Java 并发包中的并发 List 只有 CopyOnWriteArrayList。CopyOnWriteArrayList 是一个线程安全的 ArrayList对其进行的修改操作都是在底层的一个复制数组快照上进行的也就是使用了写时复制策略。
写时复制CopyOnWrite简称 COW思想是计算机程序涉及领域中的一种优化策略。其核心思想是如果多个调用者Callers同时要求相同的资源如内存或者磁盘上的数据存储他们会共同获取相同的指针指向相同的资源直到某个调用者视图修改资源内容时系统才会真正复制一份专用的副本给调用者而其他调用者所见到的最初的资源仍然保持不变。这个过程对其他调用者都是透明的。样做的好处就是可以对 CopyOnWrite 容器进行并发的读而不需要加锁因为当前容器不会被修改。
从 Jdk1.5 开始 Java 并发包里提供了两个使用 CopyOnWrite 机制实现的并发容器它们是 CopyOnWriteArrayList 和 CopyOnWriteArraySet。
CopyOnWriteArrayList 中 add 方法添加的时候是需要加锁的保证同步避免了多线程写的时候复制出多个副本。读的时候不需要加锁如果读的时候有其他线程正在向 CopyOnWriteArrayList 添加数据还是可以读到旧的数据。
写时复制的缺点
内存占用问题。由于 CopyOnWrite 的写时复制机制在进行写操作的时候内存里会同时驻扎两个对象的内存。CopyOnWrite 容器不能保证数据的实时一致性可能读取到旧数据。
3、关于 Fail Fast
Fail Fast 是 Java 集合的一种错误机制。当多个线程对同一个集合进行操作时就有可能会产生 fast-fail 事件。例如当线程 A 正通过 iterator 遍历集合另一个线程 B 修改了集合的内容此时 modCount记录集合操作过程的修改次数会加 1不等于 expectedModCount那么线程 A 访问集合的时候就会抛出 Concurrent Modification Exception产生 fast-fail 事件。边遍历边修改集合也会产生 fast-fail 事件。
解决方法
使用 Colletions.synchronizedList 方法或在修改集合内容的地方加上 synchronized。这样的话增删集合内容的同步锁会阻塞遍历操作缺点是会影响性能。使用 CopyOnWriteArrayList 来替换 ArrayList。在对 CopyOnWriteArrayList 进行修改操作的时候会拷贝一个新的数组对新的数组进行操作操作完成后再把引用移到新的数组。
4、关于 Fail Safe
Fail Safe 也是 Java 集合的一种机制采用安全失败机制的集合容器EgCopyOnWriteArrayList在遍历时不是直接在集合内容上访问的而是先复制原有集合内容在拷贝的集合上进行遍历。
原理由于迭代时是对原集合的拷贝进行遍历所以在遍历过程中对原集合所作的修改并不能被迭代器检测到所以不会触发 Concurrent Modification Exception。缺点基于拷贝内容的优点是避免了 Concurrent Modification Exception但同样地迭代器并不能访问到修改后的内容即迭代器遍历的是开始遍历那一刻拿到的集合拷贝在遍历期间原集合发生的修改迭代器是不知道的。
Psjava.util.concurrent 包下的容器都是 Fail Safe 的可以在多线程下并发使用并发修改。
