Java笔记---集合（Collection）
集合用来持有一些对象，被持有的对象称为集合中的元素。Collection是集合的最上层接口，定义了一些集合该有的常规操作。
Jdk中提供了一些集合的具体实现，如有序的集合List、不可重复的集合Set。不过Jdk中实现的集合都没有直接实现Collection，而是又定义更具体的接口List和Set。List是有序的可重复的集合，而Set为不可重复的集合。
Jdk建议所有Collection的实现都应该提供一个无参数和一个带Collection参数的构造方法。Collection参数的构造方法用来创建集新的集合并将指定集合的元素都添加到新集合中。
Collection中定义的接口并不要求都实现，对一些不需要的接口建议抛出一个UnsupportedOperationException异常。例如集合是只读的那么在调用add方法时应该抛出该异常。
集合的具体实现可能对元素的类型做出限制，如不允许为nll或只能是特定的类型，作出限制后若将一个类型不正确的元素添加到集合中时建议抛出NullPointerException、ClassCastException或返回false。但这不是必须的，例如向集合中添加一个类型不正确的元素时因为类型不正确，所以并不会被添加也就不会影响到集合，这时返回成功也是可以的，但若调用者不清楚其中的逻辑这反而产生不友好的体验。
Collection
1、增删查
1.1 boolean add(E e);
向集合中添加元素，若集合因为该操作而发生变化则返回true。
若集合中的元素不允许重复且已存在该元素则建议返回false。
除因元素已存在而不进行添加返回false外，其它任何原因拒绝添加都应该抛出异常，从而保证该调用后元素一定存在于与集合中。
1.2 boolean remove(Object o);
从集合中移除指定的元素（可选），若元素在集合中存在则移除则返回true，若不存在则返回false。
1.3 void clear();
清除集合中的所有元素（可选）
1.4 boolean contains(Object o);
若集合中存在指定元素o则放回true。
一般情况下与较集合中的元素进行比较是否相等使用：(o == null ? e == null : o.equals(e)) 的方式比较。
1.5 Iterator<E> iterator();
返回遍历Collection中所有元素的迭代器, 迭代器的顺序由具体的实现决定。
1.6 Object[] toArray();
新建一个包含所有元素的数组并返回
返回的数组都是新建的，对返回的数组的操作（非元素的操作）不会影响到集合，所以该方法是安全的。
1.7 <T> T[] toArray(T[] a);
将集合中的元素拷贝到指定数组a中并返回。若a的长度小于集合中元素的数量则扩展a。
2、批量增删查：
2.1 boolean addAll(Collection<? extends E> c);
将指定集合中的所有元素添加到集合中（可选），若集合因此发生变化则返回true。
2.2 boolean removeAll(Collection<?> c);
移除所有存在于集合c中的元素（可选），若集合因此发生变化则返回true.
2.3 boolean retainAll(Collection<?> c);
保留所有在c中存在的元素，删除c中不存在的元素（可选）。若集合因该调用发生变化则返回true。
2.4 boolean containsAll(Collection<?> c);
若集合c的元素在集合中都存在则返回true
3、集合的状态:
3.1 int size();
返回集合中元素的数量。
如果数量超过Integer.MAX_VALUE，则返回Integer.MAX_VALUE。
Jdk中各个Collection的实现最大数量限制都未超过Integer.MAX_VALUE。
3.2 boolean isEmpty();
如果Collection中一个元素都没有则返回true
4、其它
4.1 boolean equals(Object o);
比较两个集合是否相等。
Collection没有对equals具体要求，但自己实现时因注意到Collection是个集合，同时保证equals相等时hashCode也相等。
4.2 int hashCode();
返回集合的hashCode。Collection没有对hashCode具体要求，但若自己实现了equals方法则也是应该更新hashCode方法，因为一些地方认为equals相等那么hashCode也是相等的。
二、AbstractCollection
AbstractCollection基于iterator()实现了一些通用的方法，但AbstractCollection本身并没有实现iterator()方法。
public abstract class AbstractCollection<E> implements Collection<E> {
public abstract Iterator<E> iterator();
}
1. public boolean addAll(Collection<? extends E>)
通过多次调用add方法将指定集合中的元素逐个添加。但AbstractCollection并未实现具体add方法。
public boolean addAll(Collection<? extends E> c) {
boolean modified = false;
for (E e : c)
if (add(e))
modified = true;
return modified;
}
public boolean add(E e) {
throw new UnsupportedOperationException();
}
2. public boolean remove(Object o)
通过iterator逐个遍历集合中的元素，查找第一个相等的元素，然后使用iterator的remove方法将其移除，并返回true。AbstractCollection的remove是支持null元素的。
public boolean remove(Object o) {
Iterator<E> it = iterator();
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;
}
3. boolean removeAll(Collection<?> c)
通过集合的iterator遍历每一个元素，判断元素是否在c集合中，若存在则将其移除。
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;
}
4. boolean retainAll(Collection<?> c)
通过集合的iterator遍历每一个元素，判断元素是否在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;
}
5. clear()
遍历所有元素，依次移除
public void clear() {
Iterator<E> it = iterator();
while (it.hasNext()) {
it.next();
it.remove();
}
}
6. boolean contains(Object o)
通过iterator逐个遍历查找第一个相等的元素并返回true，支持null元素
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;
}
7. boolean containsAll(Collection<?> c)
遍历c中的元素逐个调用contains进行查找，不存在则直接返回false。
public boolean containsAll(Collection<?> c) {
for (Object e : c)
if (!contains(e))
return false;
return true;
}
8. public Object[] toArray()
创建一个初始大小为size()的新数组，并通过iterator遍历将集合中的元素并添加到该数组中。若iterator返回的数量大于size()，将数组大小扩展未原来的1.5倍+1。
在AbstractCollection中定义了一个最大容量，若大于最大值则取Integer.MAX_VALUE，返回之前通过Arrays.copyOf将多出来的元素去除。
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
public Object[] toArray() {
Object[] r = new Object[size()];
Iterator<E> it = iterator();
for (int i = 0; i < r.length; i++) {
if (! it.hasNext())
return Arrays.copyOf(r, i);
r[i] = it.next();
}
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;
if (i == cap) {
int newCap = cap + (cap >> 1) + 1;
if (newCap - MAX_ARRAY_SIZE > 0)
newCap = hugeCapacity(cap + 1);
r = Arrays.copyOf(r, newCap);
}
r[i++] = (T)it.next();
}
return (i == r.length) ? r : Arrays.copyOf(r, i);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError
("Required array size too large");
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
9. <T> T[] toArray(T[] a)
转化为指定类型的数组时使用指定的数组，若指定数组小于size()则重新分配一个大小为size的数组。若指定数组的大于size,将集合中的值从0填入数组中到则多余的元素填null。
public <T> T[] toArray(T[] a) {
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()) {
if (a == r) {
r[i] = null;
} 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();
}
return it.hasNext() ? finishToArray(r, it) : r;
}
11. public boolean isEmpty()
通过seize方法来判断集合是否为空。
public boolean isEmpty() {
return size() == 0;
}
public abstract int size();
12. public String toString()
toString调用元素的toString将集合中所有元素拼接到['e1', 'e2']格式的字符串中。
public String toString() {
Iterator<E> it = iterator();
if (! it.hasNext())
return "[]";
StringBuilder sb = new StringBuilder();
sb.append('[');
for (;;) {
E e = it.next();
sb.append(e == this ? "(this Collection)" : e);
if (! it.hasNext())
return sb.append(']').toString();
sb.append(',').append(' ');
}
}
