版权声明：
作者：WangJY
出处：http://www.imrookie.cn
本文版权归作者所有，转载请指明出处，否则保留追究法律责任的权利。
下图为java集合框架的结构图：
本文主要介绍集合大家族中的Collection这一部分。（源码版本为1.6）
1.最顶层的Collection接口
里面定义了一些抽象方法,源码如下:
package java.util;
public interface Collection<E> extends Iterable<E> {
int size(); //返回元素个数
boolean isEmpty(); //是否为空
boolean contains(Object o); //判断是否包含某元素
Iterator<E> iterator(); //返回迭代器
Object[] toArray(); //转为数组对象
<T> T[] toArray(T[] a); //转为特定类型的数组对象
boolean add(E e); //插入某元素
boolean remove(Object o); //删除某元素
boolean containsAll(Collection<?> c); //判断是否包含指定collection中的所有元素
boolean addAll(Collection<? extends E> c); //插入指定collection中的所有元素
boolean removeAll(Collection<?> c); //移除此collection中那些也包含在指定collectiion中的元素
boolean retainAll(Collection<?> c); //仅保留此collection中那些也包含在指定collection中的元素
void clear(); //移除所有元素
boolean equals(Object o); //比较此collection与指定对象是否相等
int hashCode(); //返回此collection的hash值
}Collection接口继承了Iterable接口,内部就一个抽象方法,用来返回迭代器,源码如下:
package java.lang;
import java.util.Iterator;
public interface Iterable<T> {
Iterator<T> iterator(); //返回迭代器
}迭代器接口Iterator源码如下:
package java.util;
public interface Iterator<E> {
boolean hasNext(); //是否含有下一个元素
E next(); //返回迭代的下一个元素
void remove(); //从迭代器指向的collection中移除迭代器返回的最后一个元素
}·抽象类AbstractCollection,实现了Collection接口
在AbstractCollection抽象类里,实现了下列方法:
在java的API文档里面标明可选操作的方法,在子类中如果需要则需要重写该方法,否则会报new UnsupportedOperationException();
1. boolean isEmpty()方法,源码如下,这里并没有提供size()的实现,所以需要在子类中实现size()方法
public boolean isEmpty() {
return size() == 0;
}2. boolean contains(Object o),在该方法中,允许传入null值,如果元素中有null,则返回true
实现原理:取迭代器,如果传入null,则循环判断是否有null元素,有则true;如果传入不为null,则遍历迭代器,利用equals()方法进行判断是否相等;同样的iterator()方法需要在子类中实现.
public boolean contains(Object o) {
Iterator<E> e = iterator();
if (o==null) {
while (e.hasNext())
if (e.next()==null)
return true;
} else {
while (e.hasNext())
if (o.equals(e.next()))
return true;
}
return false;
}3. Object[] toArray()和<T> T[] toArray(T[] a)方法;
4. boolean remove(Object o) 移除某元素,实现类似于contains(Object o)方法,先找到该元素,然后调用迭代器的remove()方法,然后返回true,如果没有该元素,返回false;
5. boolean containsAll(Collection<?> c) 判断全部包含,处理过程:取形参c的迭代器,遍历该形参迭代器,循环调用contains(Object o)方法判断,有一个不包含则返回false;
6. boolean addAll(Collection<? extends E> c) ,从源码看,只要有一个插入成功就返回true
public boolean addAll(Collection<? extends E> c) {
boolean modified = false;
Iterator<? extends E> e = c.iterator();
while (e.hasNext()) {
if (add(e.next()))
modified = true;
}
return modified;
}7. boolean removeAll(Collection<?> c) 和addAll类似,有一个移除了就返回true;
8. boolean retainAll(Collection<?> c) 和removeAll类似,有一个删除就返回true;
9. void clear() 处理过程:循环调用迭代器的remove();
10. String toString() 重写了toString()方法
2.Collection接口下的3个子接口,List,Set,Queue
2.1 List接口
List接口继承了Collection接口,源码如下(继承自Collection接口的方法此处省略):
package java.util;
public interface List<E> extends Collection<E> {
//...继承自Collection的抽象方法省略
E get(int index); //返回列表中指定位置的元素
E set(int index, E element); //用指定元素替换列表中指定位置的元素
void add(int index, E element); //在列表的指定位置插入元素
E remove(int index); //删除指定位置上的元素
int indexOf(Object o); //返回此列表中第一次出现的指定元素的索引；如果此列表不包含该元素，则返回 -1
int lastIndexOf(Object o); //返回此列表中最后出现的指定元素的索引；如果列表不包含此元素，则返回 -1
ListIterator<E> listIterator(); //返回此列表元素的列表迭代器（按适当顺序）
ListIterator<E> listIterator(int index); //返回列表中元素的列表迭代器（按适当顺序），从列表的指定位置开始
List<E> subList(int fromIndex, int toIndex); //返回列表中指定的 fromIndex（包括 ）和 toIndex（不包括）之间的子列表
}可以看到,listIterator()方法返回了list列表迭代器,来看下源码:
ListIterator接口:
ListIterator列表迭代器接口,继承了Iterator接口:
package java.util;
public interface ListIterator<E> extends Iterator<E> {
//继承自Iterator接口的方法就不显示了
boolean hasNext();
E next();
boolean hasPrevious(); //如果以逆向遍历列表，列表迭代器有多个元素，则返回 true,也就是判断是否存在上一个元素
E previous(); //返回上一个元素
int nextIndex(); //下一个元素的索引
int previousIndex(); //上一个元素的索引
void remove(); //从列表中移除由 next 或 previous 返回的最后一个元素
void set(E e); //用指定元素替换next或previous返回的最后一个元素
void add(E e); //将指定的元素插入列表
}抽象类AbstractList
AbstractList继承自AbstractCollection,实现了List接口
在AbstractList抽象类中,实现了iterator()方法和listIterator()方法,因为很多方法基于这两个方法来实现,比如AbstractList里的indexOf和lastIndexOf方法等;
1.内部类Itr,实现了Iterator接口,一起看下源码(分析写在注释部分):
private class Itr implements Iterator<E> {
int cursor = 0; //当前游标位置
int lastRet = -1; //上一个操作的元素索引
int expectedModCount = modCount; //预期修改数,初始化为外部类的修改数的值,用来作并发判断
public boolean hasNext() {
return cursor != size();
}
//可以看出,iterator中并没有元素容器,他是靠cursor属性和lastRet属性来控制读取和删除操作的
public E next() {
checkForComodification();
try {
E next = get(cursor);
lastRet = cursor++;
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
//注意: 不可以连续使用该方法,否则会因为lastRet属性被重置为-1而报异常
public void remove() {
if (lastRet == -1)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor--;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}
//此用法用来判断外部修改数和iterator修改数是否一致,不一致会报异常
//所以,在使用iterator期间不可以用非iterator方法对list做操作
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}注意: 在list中使用iterator时千万不要使用非iterator方法对list进行改动,否则会报异常:java.util.ConcurrentModificationException
2.内部类ListItr,继承了Itr,实现了ListIterator接口;
在Itr的基础上,多了一些方法,支持向前读,插入,set等操作;
提供了一个带参构造函数,设置cursor参数的值.
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
public E previous() {
checkForComodification();
try {
int i = cursor - 1;
E previous = get(i);
lastRet = cursor = i;
return previous;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor-1;
}
public void set(E e) {
if (lastRet == -1)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.set(lastRet, e);
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
AbstractList.this.add(cursor++, e); //在当前游标索引处插入元素,然后光标自增1
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}2.1.1 ArrayList类
ArrayList类继承自AbstractList类,实现了List,RandomAccess,Cloneable,java.io.Serializable接口,是可序列化的.
在ArrayList中使用对象数组来作为存储容器,使用transient关键字修饰,transient关键字具有以下特征:
1、transient关键字只能修饰变量，而不能修饰方法和类。注意，本地变量是不能被transient关键字修饰的。
2、被transient关键字修饰的变量不再能被序列化，一个静态变量不管是否被transient修饰，均不能被序列化。
3、一旦变量被transient修饰，变量将不再是对象持久化的一部分，该变量内容在序列化后无法获得访问。也可以认为在将持久化的对象反序列化后，被transient修饰的变量将按照普通类成员变量一样被初始化
ArrayList类提供了3个构造方法:
1.带参构造方法,参数为容器初始化大小
2.无参构造方法,默认容器大小为10，jdk1.8源码中默认为一个静态的空数组，当第一次进行add操作时，在确保容量的方法中设置为默认大小（10）
3.带参构造方法,参数为Collection实例
ArrayList类中的重要属性包括:
private transient Object[] elementData; //容器 private int size; //记录元素个数 protected transient int modCount = 0; //结构上改动的次数,例如扩容操作,继承自AbstractList父类
ArrayList类中的常用方法:
1. 扩容 public void ensureCapacity(int minCapacity)
从源码中可以看出,当传入参数大于当前容量时有效,该方法扩容至少为 原容量的1.5倍+1并取整
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}2. 将此 ArrayList 实例的容量调整为列表的当前大小 public void trimToSize()
也就是把容器的大小调整为size属性大小
3. indexOf(Object o) 返回某对象在数组容器中第一次出现的索引,没有该元素则返回-1
参数可以是null
4. lastIndexOf(Object o) 返回某对象在数组容器中最后一次出现的索引,没有该元素则返回-1
参数可以是null
5. 克隆方法Object clone()
因为超类中的clone()方法是浅拷贝的,所以要实现深拷贝,要在super.clone()之后,将引用变量重新赋值;
public Object clone() {
try {
ArrayList<E> v = (ArrayList<E>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError();
}
}6. 转为数组
Object[] toArray() 和
public <T> T[] toArray(T[] a)
7. 取值 get(int index)
8. 设置某索引对应的元素 set(int index, E element)
该方法返回该索引上的旧值
在末尾添加元素 boolean add(E e)
9. 在指定索引位置插入元素 add(int index, E element)
原理: 数组容器从该索引位置整体向后挪动1位,然后给改索引位置赋值
System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length) 复制指定的数组到目标数组
参数1: 要复制的原始数组
参数2: 从哪开始拷贝
参数3: 目的地数组
参数4: 开始存放的位置,也就是复制的元素从哪个索引开始放
参数5: 拷贝长度
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
ensureCapacity(size+1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}类似的还有:
插入全部 addAll(Collection<? extends E> c)
从指定索引开始插入全部 addAll(int index, Collection<? extends E> c)
10. 移除某个索引上的元素remove(int index),返回被移除的元素
和上面的方法一样,需要整体移动数组容器;
同样的:
remove(Object o)方法是先找到对应元素的索引,然后整体移动
removeRange(int fromIndex, int toIndex) 移除索引fromIndex到toIndex的元素
11. 清空集合 clear()
循环给数组容器的元素赋值null
ArrayList中没有重写iterator()方法和listIterator()方法,继承的父类AbstractList中的方法.
2.1.2 LinkedList类
双向链表的数据结构.
类中有一个核心属性header,他是列表的头,初始化时会将上下节点都指向自身（在jdk1.8中header改为了first和last，分别记录链表的头和尾）
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;
public LinkedList() {
header.next = header.previous = header;
}
...存放元素的容器为Entry对象（jdk1.8中为Node，内部属性类似，构造函数中参数顺序变为上一个-当前-下一个）,Entry是LinkedList的静态内部类,源码如下:
private static class Entry<E> {
E element; //存放元素本身
Entry<E> next; //指向下一个Entry
Entry<E> previous; //上一个Entry
//构造函数形参分别表示: 元素,下一个Entry,上一个Entry
Entry(E element, Entry<E> next, Entry<E> previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}插入数据核心方法 addBefore(E e,Entry<E> entry),在某个entry前插入元素:
private Entry<E> addBefore(E e, Entry<E> entry) {
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
newEntry.previous.next = newEntry; //将上一个节点的下节点指向e
newEntry.next.previous = newEntry; //将下一个节点的上节点指向e
size++;
modCount++;
return newEntry;
}add(e)方法就是通过 addBefore(e,header)在header节点前插入 实现的
get(int index) 根据索引查找元素时会判断header正向和反向哪个离索引更近,然后向更近的方向遍历,源码如下:
//调用私有方法entry(i)找到对应索引的节点
public E get(int index) {
return entry(index).element;
}
private Entry<E> entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
Entry<E> e = header;
//>>位移运算,可以理解为除以2
//当索引在前半部分,就遍历下个节点,一直遍历到该索引的节点
//在后半部分,就遍历上个节点
if (index < (size >> 1)) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}删除元素核心方法如下:
删除元素,不论是删除第一个还是最后一个,又或是根据索引删除,或者根据元素删除,步骤大致如下:
1.找到该元素对应的节点,然后调用remove(Object o)方法,该方法核心步骤主要做2,3两步操作;
2.让该节点的上下节点互相指向对方;
3.然后置空该节点的元素和上下节点应用;
注意:该方法会返回被删除元素
private E remove(Entry<E> e) {
if (e == header)
throw new NoSuchElementException();
E result = e.element;
//下面2行让上下节点互相指向对方
e.previous.next = e.next;
e.next.previous = e.previous;
//置空被删除节点的属性
e.next = e.previous = null;
e.element = null;
size--;
modCount++;
return result;
}LinkedList重写了listIterator(int index)方法,内部也存在个私有的内部类ListItr,和AbstractList抽象类中的实现类似,只是由操作索引换成了操作Entry节点,内部还有个nextIndex属性,记录下一个元素的索引,还有个next属性,记录下一个节点.
与ArrayList类似，连续调用remove会报异常IllegalStateException（jdk1.8）
2.2 Set接口
首先,来看下Set接口源码:
package java.util;
public interface Set<E> extends Collection<E> {
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean retainAll(Collection<?> c);
boolean removeAll(Collection<?> c);
void clear();
boolean equals(Object o);
int hashCode();
}没啥特殊的方法.基本全是Collection里面的.
AbstractSet抽象类
继承了AbstractCollection抽象类,实现了Set接口
里面就3个方法hashCode(),equals(),removeAll(ollection<?> c)
package java.util;
public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E> {
protected AbstractSet() {
}
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Set))
return false;
Collection c = (Collection) o;
if (c.size() != size())
return false;
try {
return containsAll(c);
} catch (ClassCastException unused) {
return false;
} catch (NullPointerException unused) {
return false;
}
}
public int hashCode() {
int h = 0;
Iterator<E> i = iterator();
while (i.hasNext()) {
E obj = i.next();
if (obj != null)
h += obj.hashCode();
}
return h;
}
public boolean removeAll(Collection<?> c) {
boolean modified = false;
if (size() > c.size()) {
for (Iterator<?> i = c.iterator(); i.hasNext(); )
modified |= remove(i.next()); // a |= b; 相当于 a = a | b;
} else {
for (Iterator<?> i = iterator(); i.hasNext(); ) {
if (c.contains(i.next())) {
i.remove();
modified = true;
}
}
}
return modified;
}
}2.2.1 HashSet类
继承了AbstractSet抽象类,实现了Set,Cloneable,和序列化接口
基于HashMap实现的,关于HashMap的介绍看 ★★集合框架--Map
package java.util;
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L;
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<E,Object>();
}
public HashSet(Collection<? extends E> c) {
map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<E,Object>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<E,Object>(initialCapacity);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}
public Iterator<E> iterator() {
return map.keySet().iterator();
}
public int size() {
return map.size();
}
public boolean isEmpty() {
return map.isEmpty();
}
public boolean contains(Object o) {
return map.containsKey(o);
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
public void clear() {
map.clear();
}
public Object clone() {
try {
HashSet<E> newSet = (HashSet<E>) super.clone();
newSet.map = (HashMap<E, Object>) map.clone();
return newSet;
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
}
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
s.defaultWriteObject();
s.writeInt(map.capacity());
s.writeFloat(map.loadFactor());
s.writeInt(map.size());
for (Iterator i=map.keySet().iterator(); i.hasNext(); )
s.writeObject(i.next());
}
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
s.defaultReadObject();
int capacity = s.readInt();
float loadFactor = s.readFloat();
map = (((HashSet)this) instanceof LinkedHashSet ?
new LinkedHashMap<E,Object>(capacity, loadFactor) :
new HashMap<E,Object>(capacity, loadFactor));
int size = s.readInt();
for (int i=0; i<size; i++) {
E e = (E) s.readObject();
map.put(e, PRESENT);
}
}
}