Java 集合框架系列
Java 集合框架_开篇
Java 集合框架_List
Java 集合框架_ArrayList(源码解析)
Java 集合框架_LinkedList(源码解析)
Java 集合框架_Map
Java 集合框架_AbstractMap
数据结构_哈希表(Java)
Java 集合框架_HashMap中的算法
数据结构_二叉搜索树(Java)详解
Java有三大工具类框架非常值得我们学习，java集合框架，java并发框架，以及java io流框架。
Java 集合框架从顶层接口来说分成两类:
- 一个是列表集合，只包含value。 Collection接口以及它的子类。
- 一个是键值对形式的映射表集合，包含key->value。Map接口以及它的子类。
这一章我们先从Collection接口说起。
一.Collection 接口
public interface Collection<E> extends Iterable<E> {}
它继承了Iterable接口，那么这个接口有什么用呢？
1. Iterable 接口
/**
* 可迭代接口，用来返回 顺序遍历迭代器Iterator和并行遍历迭代器Spliterator。
* @param <T>
*/
public interface Iterable<T> {
Iterator<T> iterator();
// 提供默认实现， 遍历集合每个元素，使它们都调用action.accept方法。
// 因为Iterable接口有iterator方法提供迭代器，所以可以使用高级for循环
default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}
// splitable iterator可分割迭代器， 为了并行遍历数据源中的元素而设计的迭代器
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
}
Iterable接口表示可迭代接口，它会返回一个迭代器Iterator。通过这个迭代器，我们可以遍历集合中元素了。
它接口默认实现的方式，提供一个forEach方法，方便子类遍历集合中元素。
// 不用for循环的方式了。
list.forEach(new Consumer<Integer>() {
@Override
public void accept(Integer integer) {
System.out.print(" integer=="+integer);
}
});
Spliterator<T> 表示并行遍历迭代器，是jdk1.8增加的新方法。
2. 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());
}
}
迭代器Iterator是用来遍历集合中的元素的，通过next()不断获取集合中下一个元素，直到全部获取完毕，通过hasNext()方法来判断。例如：
public static void main(String[] args) {
List<Integer> list = createList();
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
迭代器还有一个remove方法，表示我们可以删除集合中当前遍历到的元素，也就是说迭代器不但可以遍历集合，还可以修改集合。
但是这里为什么提供一个默认实现呢，因为有的集合本身就是不可修改集合，它就强制复写remove方法，而调用remove方法应该抛出异常。所以这里用了jdk1.8新特性，接口中直接提供这个默认实现。
再回到Collection接口，我们想一下，作为一个集合顶层接口，它应该包含哪些方法呢？想到那个对数据数据操作最经典的话，增删改查。
- 添加元素的方法：
boolean add(E e);
boolean addAll(Collection<? extends E> c);
- 删除元素的方法：
boolean remove(Object o);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
void clear();
- 改这个操作在Collection接口没有，因为它没有提供索引，没办法更新对应索引的值。
- 查这个操作在Collection接口，集合中是否包含某些元素，以及返回迭代器遍历集合
boolean contains(Object o);
boolean containsAll(Collection<?> c);
Iterator<E> iterator();
- 其他重要方法：
int size();
boolean isEmpty();
Object[] toArray();
<T> T[] toArray(T[] a);
public interface Collection<E> extends Iterable<E> {
// 添加元素
boolean add(E e);
boolean addAll(Collection<? extends E> c);
// 删除元素
boolean remove(Object o);
boolean removeAll(Collection<?> c);
void clear();
// 只保留c集合中包含的元素
boolean retainAll(Collection<?> c);
// 是否包含某些元素
boolean contains(Object o);
boolean containsAll(Collection<?> c);
// 遍历集合
Iterator<E> iterator();
// 其他重要方法
int size();
boolean isEmpty();
Object[] toArray();
<T> T[] toArray(T[] a);
// 根据filter返回值，删除集合中的元素
default boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
boolean removed = false;
final Iterator<E> each = iterator();
while (each.hasNext()) {
if (filter.test(each.next())) {
each.remove();
removed = true;
}
}
return removed;
}
boolean equals(Object o);
int hashCode();
// 将一个集合转换成Stream，这样可以对集合中的元素进行过滤去重等处理。
@Override
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, 0);
}
default Stream<E> stream() {
return StreamSupport.stream(spliterator(), false);
}
default Stream<E> parallelStream() {
return StreamSupport.stream(spliterator(), true);
}
}
二. AbstractCollection 抽样类
AbstractCollection抽样类实现了Collection接口大部分方法，只剩下iterator()和size()方法需要子类复写，也就是说需要子类提供集合元素。
1. 添加元素
public boolean add(E e) {
throw new UnsupportedOperationException();
}
public boolean addAll(Collection<? extends E> c) {
boolean modified = false;
for (E e : c)
if (add(e))
modified = true;
return modified;
}
add(E e) 方法直接抛出异常，表示AbstractCollection默认是不可修改的集合，子类必须复写这个方法，才能向集合中添加元素。
addAll(Collection<? extends E> c) ，通过for循环，将c集合中每个元素都添加到本集合中。
高级for循环这种格式，默认就是使用迭代器实现的，也就是说只要是Iterable 接口子类，都可以使用高级for循环。
2. 删除元素
public boolean remove(Object o) {
Iterator<E> it = iterator();
// 注意这里，集合中有很多地方都是以o是否为空，分成两部分计算，虽然代码逻辑几乎一样。
if (o==null) {
while (it.hasNext()) {
if (it.next()==null) {
it.remove();
return true;
}
}
} else {
while (it.hasNext()) {
if (o.equals(it.next())) {
it.remove();
return true;
}
}
}
return false;
}
删除单个元素，通过迭代器iterator，遍历集合中元素，如果与o相等，就通过迭代器的remove方法，将它删除。
注意这里会根据被删除元素o是否为空，分成两部分，虽然两部分代码逻辑几乎一模一样。如果设计成在循环中进行两个条件判断，这样也可以，但是会增加比较次数。
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
Iterator<?> it = iterator();
while (it.hasNext()) {
if (c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}
通过迭代器遍历本集合中每个元素，如果c集合中也包含这个元素，那么就删除这个元素。
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
Iterator<E> it = iterator();
while (it.hasNext()) {
if (!c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}
这个方法和removeAll方法正好相反，遍历本集合中每个元素，如果c集合中不包含这个元素，那么就删除这个元素。
public void clear() {
Iterator<E> it = iterator();
while (it.hasNext()) {
it.next();
it.remove();
}
}
删除集合中全部元素。遍历集合中每个元素，得到一个删除一个，最终删除全部元素。
3. 查找元素
public boolean contains(Object o) {
Iterator<E> it = iterator();
if (o==null) {
while (it.hasNext())
if (it.next()==null)
return true;
} else {
while (it.hasNext())
if (o.equals(it.next()))
return true;
}
return false;
}
遍历每个元素，如果有和o对象相等的，就直接返回true。如果遍历全部元素，还是没有找到相等元素，就返回false。
public boolean containsAll(Collection<?> c) {
for (Object e : c)
if (!contains(e))
return false;
return true;
}
是否包含c集合中全部元素。
4. 其他重要方法
public abstract Iterator<E> iterator();
public abstract int size();
这两个方法等待子类复写。
public boolean isEmpty() {
return size() == 0;
}
通过size()方法判断集合是否为空。
public Object[] toArray() {
// 将terator迭代器中的元素全部转换成Object[]，我们必须知道集合元素的大小。
// 但是size()返回值并不是集合元素的数量，所以要分情况
Object[] r = new Object[size()];
Iterator<E> it = iterator();
for (int i = 0; i < r.length; i++) {
// 迭代器已经遍历完成，说明集合元素数量就是i。用Arrays.copyOf(r, i)就可以返回i长度的Object数组了
if (! it.hasNext())
return Arrays.copyOf(r, i);
r[i] = it.next();
}
// 如果it.hasNext()为true，表示集合中还有元素，那么就要扩大r数组，以便将剩余元素都存放进去。
// 如果为false，那么表示集合数量就是size()，直接返回这个r数组。
return it.hasNext() ? finishToArray(r, it) : r;
}
将集合转成Object[]数组，这个方法很重要。要转成数组，那么必须知道数组的大小。
这里需要注意的是size()返回值有可能和集合中元素数量不一样，因为强制约束它们两个值是相同的，要考虑到这种情况。
所以这里我们先创建一个size()长度的Object[]，然后遍历迭代器，将值存入数组对应下标位置。然后就有三种情况：
- 迭代器先遍历完成，就说明集合元素数量小于size()大小，而集合元素数量就是这个i, 然后通过Arrays.copyOf(r, i)方法，返回i长度的数组。
- 迭代器和r数组一起遍历完成，那么集合元素长度就是size(),直接返回这个r数组。
- 迭代器还没有遍历完成，那么就要对r数组进行扩容，存放剩余的集合元素，通过finishToArray(r, it)方法实现。
public <T> T[] toArray(T[] a) {
// Estimate size of array; be prepared to see more or fewer elements
int size = size();
T[] r = a.length >= size ? a :
(T[])java.lang.reflect.Array
.newInstance(a.getClass().getComponentType(), size);
Iterator<E> it = iterator();
for (int i = 0; i < r.length; i++) {
if (! it.hasNext()) { // fewer elements than expected
if (a == r) {
r[i] = null; // null-terminate
} else if (a.length < i) {
return Arrays.copyOf(r, i);
} else {
System.arraycopy(r, 0, a, 0, i);
if (a.length > i) {
a[i] = null;
}
}
return a;
}
r[i] = (T)it.next();
}
// more elements than expected
return it.hasNext() ? finishToArray(r, it) : r;
}
private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
int i = r.length;
while (it.hasNext()) {
int cap = r.length;
// 如果i == cap为true，表示数组已经满了，需要扩充。
if (i == cap) {
// 将数组长度扩充0.5倍。 (cap >> 1) 相当于 cap / 2
int newCap = cap + (cap >> 1) + 1;
// 防止数组长度超出Integer最大值
if (newCap - MAX_ARRAY_SIZE > 0)
newCap = hugeCapacity(cap + 1);
// 将原数组元素新数组中，并返回新数组。
r = Arrays.copyOf(r, newCap);
}
r[i++] = (T)it.next();
}
// trim if overallocated
return (i == r.length) ? r : Arrays.copyOf(r, i);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError
("Required array size too large");
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
总结
Collection 接口
- Collection 接口继承自Iterable接口，Iterable接口表示一个可迭代接口，主要作用就是返回一个迭代器Iterator。
- 顶层迭代器Iterator有三个重要方法：
- boolean hasNext();
- E next();
- void remove()。
用来遍历和移除集合中的元素。
- Collection 接口中重要方法：
- boolean add(E e); 向集合中添加一个元素
- boolean addAll(Collection<? extends E> c); 将集合c中元素都添加到集合中。
- boolean remove(Object o); 从集合中删除o元素，也有可能删除不成功
- boolean removeAll(Collection<?> c); 从集合中删除集合c中包含的元素
- boolean retainAll(Collection<?> c); 只保留c集合中包含的元素
- void clear(); 清除集合中所有元素
- boolean contains(Object o); 判断集合中是否包含元素o
- boolean containsAll(Collection<?> c); 判断集合是否完整包含集合c中全部元素
- Iterator<E> iterator(); 返回迭代器
- int size(); 返回集合数量
- boolean isEmpty(); 判断集合是否为空
- Object[] toArray(); 将集合中元素转换成数组
- <T> T[] toArray(T[] a); 将集合中元素转换成T类型的数组
AbstractCollection 抽样类
- 强制子类复写Iterator<E> iterator() 和int size() 方法
- boolean add(E e) 方法直接抛出异常，如果不复写这个方法，那么集合是不能添加数据的。
- boolean addAll(Collection<? extends E> c) 方法，是遍历集合，然后调用add方法，将元素添加到集合中，所以也会抛出异常。
- remove(Object o) 方法，是调用迭代器的remove()实现的。
- removeAll(Collection<?> c)方法，是通过迭代器遍历集合，然后使用集合c的contains方法，判断元素在集合中是否也存在，是的话就调用迭代器的remove()方法，删除这个元素。
- retainAll(Collection<?> c)方法，与removeAll方法流程大体一样，只不过它是判断集合c中不包含就调用迭代器的remove()方法，删除这个元素。
- void clear(); 通过迭代器遍历集合，然后调用r迭代器的remove()方法，删除每个元素
- boolean contains(Object o); 通过迭代器遍历集合，查看是否有与o相等的元素。
- boolean containsAll(Collection<?> c); 遍历集合c，拿集合c中每个元素调用本集合的contains方法。如果有返回false，那么containsAll方法就直接返回false。只有全部通过才返回true。
- Object[] toArray(); 和<T> T[] toArray(T[] a); 通过迭代器将集合转化成对应数组。
例子
下面用一个例子来表示：
public static void main(String[] args) {
// 创建AbstractCollection实例，需要复写iterator和size，这是一个不可修改集合
Collection<Integer> collection = new AbstractCollection() {
int[] data = {1,2,3,4,5}; // 集合中的元素
@Override
public Iterator iterator() {
return new Iterator() {
int cursor;
@Override
public boolean hasNext() {
return cursor != data.length;
}
@Override
public Object next() {
return data[cursor++];
}
};
}
@Override
public int size() {
return data.length;
}
};
// 遍历集合
for (int i : collection) {
System.out.println(i);
}
// 测试contains方法
System.out.println(collection.contains(3));
System.out.println(collection.contains(10));
List<Integer> other = new ArrayList<>();
other.add(2);
other.add(3);
other = other.subList(0,1);
for (int i : other) {
System.out.println(i);
}
// 测试containsAll方法
System.out.println(collection.containsAll(other));
}
