1、数组
类型固定、长度固定
连续的内存空间
顺序存储、随机读取
查询快、新增删除慢。最好初始化的时候就指定数组大小。这样就可以避免一定的数组扩容出现的内存消耗。
import java.util.Arrays;
import java.util.Iterator;
/**
* @author Administrator
* @date 2022-09-11 16:56
* 实现一个数组
*/
public class MyArray<E> implements Iterable<E> {
private Object[] elementData; // Object存放数据
public MyArray(int capacity) // 构造方法 初始化容量大小
{
// 指定长度 初始化数组 new 出一块空间
elementData = new Object[capacity];
}
/**
* 直接添加新元素
* @param element
* @return
*/
public boolean add (E element)
{
int size = elementData.length; // 获取当前数组大小
int newCapacity = size+1; // 扩容+1
// 此处发生性能消耗,新增数据时,需要扩容,整体数据需要复制迁移,实际上arraylist是1.5扩容!
elementData = Arrays.copyOf(elementData,newCapacity); // 把旧的空间复制一份到新的空间并+1
elementData[size]=element;
return true;
}
/**
* set 方法 根据索引位置新增元素
* @param index
* @param element
* @return
*/
public E set (int index ,E element)
{
E oldValue = (E) elementData[index]; // 获取旧位置的元素值
elementData[index] = element; // 新值覆盖旧值
return oldValue; // 返回旧值
}
public E get (int index)
{
return (E) elementData[index]; // 返回对应索引位置的值
}
@Override
public Iterator<E> iterator(){
return new MyIterator();
}
class MyIterator implements Iterator<E>{
int index = 0;
@Override
public boolean hasNext() {
return index != elementData.length;
}
@Override
public E next() {
return (E) elementData[index++]; // 返回下一个元素值并+1
}
@Override
public void remove() {
//
}
}
public static void main(String[] args) {
MyArray<String> myArray= new MyArray<String>(10); // 初始化一个容量为10的数组
myArray.set(0,"q");
myArray.set(2,"w");
myArray.add("新增");
Iterator<String> iterator = myArray.iterator(); // 使用迭代器
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
}
1.1、关于arraylist初始容量和扩容
ArrayList 新增元素的方法有两种,一种是直接将元素加到数组的末尾,另外一种是添加元素到任意位置。
arraylist默认构造器,在不指定大小的时候默认容量为 10。
在超出容量之后,每次扩容为当前容量大小的1.5倍+1。
1.2、关于迭代器
集合的顶层接口Collection
继承Iterable
接口。在Iterable接口
中有一个Iterator方法
,它返回一个Itertator对象
。
public interface Iterable<T> {
/**
* Returns an iterator over elements of type {@code T}.
*
* @return an Iterator.
*/
Iterator<T> iterator();
}
public interface Iterator<E> {
boolean hasNext();
E next();
default void remove() {
throw new UnsupportedOperationException("remove");
}
}
迭代器遍历中调用集合revome()方法触发异常 java.util.ConcurrentModificationException 集合中并发修改的异常.
因为迭代器只负责遍历,它使用的仍然是集合本身的数据,在List集合实现的时候数组的长度size会因为remove发生变化的,同时元素的索引值也会因为remove( )方法的调用而发生变化。那么在遍历的时候的remove就需要对这个点进行复刻,而且如果在迭代器里使用了List原生的remove方法,那么就会引起数值不同步的问题。
在ArrayList
集合的iterator()
方法中,是通过返回Itr
对象来获得迭代器的。Itr
是ArrayList
的一个内部类,它实现了Iterator
接口,代码如下:
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
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
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.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
注意以下的三个属性:
cursor | 索引下标,表示下一个可以访问的元素的索引,默认值为 0 |
---|---|
lastRet | 索引下标,表示上一个元素的索引,默认值为 -1 |
expectedModCount | 对集合修改的次数,初始值为 0 |
我们知道:List的add和remove调用会增加modCount的值。也就是这两个操作会被计入对集合的修改次数。
在迭代器的源码中,有一个方法是用来判断 modCount 和 expectModCount 的值是否相等的,其中modCount的值来自List,expectModCount 是迭代器内定义的变量。那为什么要这么设计呢?
因为arraylist是线程不安全的。
结合iterrator的next方法,我们可以看到,如果没有这个校验,某个线程删除了list的一个元素,此时next方法不知道size变更了,依然去取数组里的数据,会导致数据为null或ArrayIndexOutOfBoundsException异常等问题。
ConcurrentModificationException发生在Iterator( )和next( )方法实现中,每次调用都会检查容器的结构是否发生变化,目的是为了避免共享资源而引发的潜在问题。
观察HashMap和ArrayList底层Iterator#next(), 可以看到fast-fail只会增加或者删除(非Iterator#remove())抛出异常;改变容器中元素的内容不存在这个问题(主要是modCount没发生变化)。
在单线程中使用迭代器,对非线程安全的容器,但是只能用Iterator和remove;否则会抛出异常。
在多线程中使用迭代器,可以使用线程安全的容器来避免异常。
使用普通的for循环遍历,效率虽然比较低下,但是不存在ConcurrentModificationException异常问题,用的也比较少。
所以说如果在使用迭代器的时候,用到了List自带的remove方法,那么modCount改变了,但是迭代器内定义的变量expectedCount却没有改变,这样就会被抛出异常。
综上:我们在使用迭代器的时候,不要混用List本身的remove方法。
Iterator接口有四个方法,hasNext、next、remove和forEachRemaining
其中forEachRemaining是java1.8新增的
这个方法是针对集合中剩余元素的操作
剩余的含义是没有被iterator.next()遍历过的元素
1.3、为什么迭代器在调用remove之前要先调用next
当使用Iterator迭代访问Collection集合元素时,Collection集合里的元素不能被改变,只有通过Iterator的remove()方法删除上一次next()方法返回的集合元素才可以;否则会引发java.util.ConcurrentModificationException异常。
查看next方法的源码可以看到 return (E) elementData[lastRet = i];
这样一行代码,这行代码表示next方法在让数组下标cursor向后移动一位的同时,还会把lastRet的值变成当前返回的元素下标,这样remove方法就可以根据这个下标完成对元素的删除。
原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/tech/java/289254.html