Java集合框架概览以及迭代器
2021-05-07 本文已影响0人
我会有只猫的_2c34
目录介绍
- 1.什么是集合
- 1.1 概念
- 1.2 和数组区别
- 1.3 java集合框架图
- 2.Iterator、Iterable和ListIterator
- 2.1 简介
- 2.2 Iterable接口
- 2.3 Iterator接口
- 2.4 ListIterator接口
- 3.Iterable和ListIterator具体实现(以ArrayList为例)
- 3.1 Iterable具体实现----Itr
- 3.2 ListIterator具体实现----ListItr
- 4.fail-fast机制
- 4.1 简介
- 4.2 如何边遍历边操作集合
1.什么是集合
1.1 概念
- java集合框架的用途是“保存对象”，并将其划分为两个不同的概念：
- （1）Collection。 一个独立的元素序列，这些元素都服从一条或多条规则。List必须按照插入的顺序保存元素，而Set不能有重复的元素。Queue按照排队的规则来确定对象的产生顺序（通常与他们被插入的顺序相同）
- （2）Map。一组成对的“键值对”对象，允许你使用键来查找值。
1.2 集合和数组的区别
- （1）数组长度固定，集合长度不固定
- （2）数组可以储存基本数据类型和引用数据类型，集合只能存储引用数据类型
1.3 java集合框架图
下图是java集合框架的总图：
java集合框架.png
2.Iterator、Iterable和ListIterator
2.1 简介
Collection是java序列集合的根接口，继承Iterable接口；Iterable接口提供foreach能力，并且要求实现者返回一个Iterator，从本质上来说Iterator是java序列容器之间的共性，AbstractCollection等抽象类都是通过Iterator来实现collection接口的方法，由于java的单继承性，我们的类在已经继承其他类的基础上，不能再继承AbstractCollection；而继承Collection代价又略微偏高，可以通过实现Iterable接口来实现一个Collection。
2.2 Iterable接口
Iterable接口是Collection接口的父接口，他要求实现类返回一个迭代器，并且提供foreach遍历的能力。
public interface Iterable<T> {
// 返回一个在一组 T 类型的元素上进行迭代的迭代器。
Iterator<T> iterator();
// foreach遍历
default void forEach(Consumer<? super T> action) {}
// 返回一个可分割的迭代器
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
}
2.3 Iterator接口
Iterator接口的定义也十分简单，提供迭代器往后面元素迭代的能力
public interface Iterator<E> {
// 是否还有元素可以迭代
boolean hasNext();
// 返回迭代的下一个元素
E next();
// 移除迭代器返回的最后一个元素
default void remove() {
throw new UnsupportedOperationException("remove");
}
// 对剩下的元素执行给定操作
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
}
2.4 ListIterator接口
ListIterator是List集合特有的迭代器
public interface ListIterator<E> extends Iterator<E> {
boolean hasNext();
E next();
// 判断游标前面是否有元素
boolean hasPrevious();
// 返回游标前面的元素，同时游标前移一位。
E previous();
// 返回游标后边元素的索引位置，初始为0
int nextIndex();
// 返回游标前面元素的位置，初始时为-1
int previousIndex();
// 删除迭代器最后一次操作的元素
void remove();
// 更新迭代器最后一次操作的元素为 E
void set(E e);
// 在游标前面插入一个元素
void add(E e);
}
3.Iterable和ListIterator具体实现(以ArrayList为例)
3.1 Iterable具体实现----Itr
private class Itr implements Iterator<E> {
// 游标位置
int cursor;
// 上次迭代的位置
int lastRet = -1;
// 用来判断是否fail-fast的变量
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
return cursor != size;
}
public E next() {
// fail-fast校验
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
// 游标+1
cursor = i + 1;
// 更新lastRet并且返回对应元素
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
// 调用外部类的remove方法移除元素
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
// 更新expectedModCount
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
// fail-fast校验
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
3.2 ListIterator具体实现----ListItr
ListItr的实现也并不复杂，主要是对游标进行操作，这里关注一下set()和add()方法的实现，可以看到方法内部也对expectedModCount进行了更新，所以他们也是可以帮助我们完成遍历时对容器的操作的.
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
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();
}
}
}
4.fail-fast机制
4.1 简介
我们在使用Iterator对容器进行迭代时如果修改容器，可能会导致ConcurrentModificationException异常。这是因为在我们的容器类中维护了一个int型的成员变量modCount，每次对容器进行操作时，都会使modCount自增，而在Iterator接口的实现类中，有一个变量expectedModCount，在遍历开始时初始化赋值为modCount。每次遍历时，都会去比较expectedModCount和modCount是否相等，如果不等，就会抛出异常。这就是java的fail-fast机制，该机制主要是用于实现集合的快速失败机制，在Java的集合中，较大一部分集合是存在快速失败机制的。所以要保证在遍历过程中不出错误，我们就应该保证在遍历过程中不会对集合产生结构上的修改，出现了异常错误，我们就应该认真检查程序是否出错而不是catch后不做处理。
// ArrayList中移除元素时modCount自增
public E remove(int index) {
rangeCheck(index);
// modCount自增
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;
}
// ArrayList中Itr校验modCount
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
4.2 如何边遍历边操作集合
这里推荐使用迭代器iterator提供的方法进行操作容器，当然，也有其他方式能够解决这个问题，比如说在遍历时删除元素可以采用倒序遍历的方式，但是都不够通用。
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String next = iterator.next();
if (next.equals("dd")) {
iterator.remove();
}
}
之所以我们能够这样操作的原因是因为在迭代器方法内部，对expectedModCount进行了重新赋值，使得下一次遍历的时候，expectedModCount是等于modCount的.
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
// expectedModCount重新赋值
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
