如何实现一个支持快照功能的迭代器呢?
主要就是对于快照两个字的理解,就是我们创建迭代器的时候,其实是对这个集合创建了一个快照,然后增删这个容器的元素的时候,快照中的元素不会做相对应的改动,迭代器遍历的对象是快照而不是容器,避免了因为其他线程的增删而导致的报错问题
我们,举一个列子来说明上面的话,假设有一个集合list,其中有3 8 2三个元素,在创建迭代器iter1之后,容器list删除了 3 8,只剩下了 2,但是iter1遍历出来的,还是3 8 2
整体的代码执行如下
| List<Integer> list = new ArrayList<>();
list.add(3); list.add(8); list.add(2); Iterator<Integer> iter1 = list.iterator();//snapshot: 3, 8, 2 list.remove(new Integer(2));//list：3, 8 Iterator<Integer> iter2 = list.iterator();//snapshot: 3, 8 list.remove(new Integer(3));//list：8 Iterator<Integer> iter3 = list.iterator();//snapshot: 3 // 输出结果：3 8 2 while (iter1.hasNext()) { System.out.print(iter1.next() + ” “); } System.out.println(); // 输出结果：3 8 while (iter2.hasNext()) { System.out.print(iter1.next() + ” “); } System.out.println(); // 输出结果：8 while (iter3.hasNext()) { System.out.print(iter1.next() + ” “); } System.out.println(); |
如何实现上面的功能呢?其中包含 ArrayList SnapshotArrayIterator两个类,我们先给出了几个关键的接口,具体的实现并没有给出
| public ArrayList<E> implements List<E> {
// TODO: 成员变量、私有函数等随便你定义 @Override public void add(E obj) { //TODO: 由你来完善 } @Override public void remove(E obj) { // TODO: 由你来完善 } @Override public Iterator<E> iterator() { return new SnapshotArrayIterator(this); } } public class SnapshotArrayIterator<E> implements Iterator<E> { // TODO: 成员变量、私有函数等随便你定义 @Override public boolean hasNext() { // TODO: 由你来完善 } @Override public E next() {//返回当前元素，并且游标后移一位 // TODO: 由你来完善 } } |
对应的接口的实现的方案有两种
1.在迭代器类中定义一个成员变量 snaplot来存储快照,在创建迭代器的时候,都拷贝一份到快照中,后续的遍历操作基于这个迭代器自己的快照
| public class SnapshotArrayIterator<E> implements Iterator<E> {
private int cursor; private ArrayList<E> snapshot; public SnapshotArrayIterator(ArrayList<E> arrayList) { this.cursor = 0; this.snapshot = new ArrayList<>(); this.snapshot.addAll(arrayList); } @Override public boolean hasNext() { return cursor < snapshot.size(); } @Override public E next() { E currentItem = snapshot.get(cursor); cursor++; return currentItem; } } |
这样的实现足够的简单,但是有一种缺陷,就是每次的创建迭代器,都会拷贝一份新的集合
导致增加占用率,但是庆幸的是,Java的拷贝是浅拷贝,只是拷贝了对象的引用罢了
但是这种的实现方式,并不支持删除,或者说删除后不好进行同步回来
2.利用时间戳来进行保存,我们可以为每一个元素保存一个添加时间戳addTimeStamp和一个删除时间戳delTimeStamp,当元素加入集合的时候,设置加入时间,删除的时候,设置删除时间
然后当更新了删除时间后,就不会在遍历中显示出来
然后在显示的时候,只有迭代器中的元素,满足了addTimeStamp<snapshotTimeStamp<delTimeStamp的时候,才是属于这个迭代器的快照
如果是 addTimeStamp>snapshotTimeStamp的时候,说明是创建了迭代器之后才加入的,不属于这个迭代器的快照,如果元素的delTimeStamp<snapshotTimeStamp,说明在之前就被删除了,也不属于这个快照
这样就在不拷贝容器的情况下,利用简单的MVCC多版本并发控制实现了快照功能,具体的代码如下
| public class ArrayList<E> implements List<E> {
private static final int DEFAULT_CAPACITY = 10; private int actualSize; //不包含标记删除元素 private int totalSize; //包含标记删除元素 private Object[] elements; private long[] addTimestamps; private long[] delTimestamps; public ArrayList() { this.elements = new Object[DEFAULT_CAPACITY]; this.addTimestamps = new long[DEFAULT_CAPACITY]; this.delTimestamps = new long[DEFAULT_CAPACITY]; this.totalSize = 0; this.actualSize = 0; } @Override public void add(E obj) { elements[totalSize] = obj; addTimestamps[totalSize] = System.currentTimeMillis(); delTimestamps[totalSize] = Long.MAX_VALUE; totalSize++; actualSize++; } @Override public void remove(E obj) { for (int i = 0; i < totalSize; ++i) { if (elements[i].equals(obj)) { delTimestamps[i] = System.currentTimeMillis(); actualSize–; } } } public int actualSize() { return this.actualSize; } public int totalSize() { return this.totalSize; } public E get(int i) { if (i >= totalSize) { throw new IndexOutOfBoundsException(); } return (E)elements[i]; } public long getAddTimestamp(int i) { if (i >= totalSize) { throw new IndexOutOfBoundsException(); } return addTimestamps[i]; } public long getDelTimestamp(int i) { if (i >= totalSize) { throw new IndexOutOfBoundsException(); } return delTimestamps[i]; } } public class SnapshotArrayIterator<E> implements Iterator<E> { private long snapshotTimestamp; private int cursorInAll; // 在整个容器中的下标，而非快照中的下标 private int leftCount; // 快照中还有几个元素未被遍历 private ArrayList<E> arrayList; public SnapshotArrayIterator(ArrayList<E> arrayList) { this.snapshotTimestamp = System.currentTimeMillis(); this.cursorInAll = 0; this.leftCount = arrayList.actualSize();; this.arrayList = arrayList; justNext(); // 先跳到这个迭代器快照的第一个元素 } @Override public boolean hasNext() { return this.leftCount >= 0; // 注意是>=, 而非> } @Override public E next() { E currentItem = arrayList.get(cursorInAll); justNext(); return currentItem; } private void justNext() { while (cursorInAll < arrayList.totalSize()) { long addTimestamp = arrayList.getAddTimestamp(cursorInAll); long delTimestamp = arrayList.getDelTimestamp(cursorInAll); if (snapshotTimestamp > addTimestamp && snapshotTimestamp < delTimestamp) { leftCount–; break; } cursorInAll++; } } } |
上面是很好的解决了一个问题,但是引入了一个新的问题,ArrayList底层依赖于数组,这种逻辑删除的方式导致没法很好的根据下标去获取到对应元素了
那么,如何既支持遍历,又支持随机访问呢?
可以使用双数组来进行存储,一个支持标记删除,用于遍历,一个不支持标记删除,进行随机访问
课后思考
对于今天给出的方案二中,删除元素只是标记删除,被删除的元素在没有迭代器使用的情况下,也不会数组中真正的移除,导致不必要的占用,如何优化
对于这个问题,实现起来并不难,就是修改两个标记集合中对应的时间,修改为两个展示用的集合大小,但是难点在于什么时候去调用删除的方法,如何去知道什么时候迭代器没有调用,首先我想到了先去利用一个集合将所有的迭代器保存,在调用删除方法的时候检查这个迭代器数组,只有自己或者没有数组的时候,进行删除,但是带来一个问题,如何知道迭代器结束了呢?编写一个结束方法?这样每次迭代完成都需要调用,是否是太繁琐了?那么,只能考虑让线程结束后自动回收了,那么就是一个弱引用的数组.当然,这并不是最好的方法,因为线程很长,迭代很短,那么我想着,是否可以在每次调用remove的时候,将要remove的元素放在一个集合中,然后每几次添加触发一次gc,清除迭代器,那么接下来的实现就很清晰了,有两种方式,一种是等待所有的迭代器都清空了,在将remove集合中的所有元素批量remove掉,或者是在remove集合中的元素数量到达一定程度的时候,将整个类加上锁,让迭代器和正常的修改都阻塞,然后删除后放开,不过事先更难,我的整体思路就差不多走到这了