原文链接: 

简化体系图

1.最顶层的Collection接口,

里面定义了一些抽象方法,源码如下:

1. package java.util;
2. publicinterfaceCollection<E>extendsIterable<E>{
3. int size();    //返回元素个数
4. boolean isEmpty();    //是否为空
5. boolean contains(Object o);    //判断是否包含某元素
6. Iterator<E> iterator();    //返回迭代器
7. Object[] toArray();    //转为数组对象
8. <T> T[] toArray(T[] a);    //转为特定类型的数组对象
9. boolean add(E e);    //插入某元素
10. boolean remove(Object o);    //删除某元素
11. boolean containsAll(Collection<?> c);    //判断是否包含指定collection中的所有元素
12. boolean addAll(Collection<?extends E> c);    //插入指定collection中的所有元素
13. boolean removeAll(Collection<?> c);    //移除此collection中那些也包含在指定collectiion中的元素
14. boolean retainAll(Collection<?> c);    //仅保留此collection中那些也包含在指定collection中的元素
15. void clear();    //移除所有元素
16. boolean equals(Object o);    //比较此collection与指定对象是否相等
17. int hashCode();    //返回此collection的hash值
18. }

Collection接口继承了Iterable接口,内部就一个抽象方法,用来返回迭代器,源码如下:

1. package java.lang;
2. import java.util.Iterator;
3. publicinterfaceIterable<T>{
4. Iterator<T> iterator();    //返回迭代器
5. }

迭代器接口

IteraTor源码如下:

1. package java.util;
2. publicinterfaceIterator<E>{
3. boolean hasNext();    //是否含有下一个元素
4. E next();    //返回迭代的下一个元素
5. void remove();    //从迭代器指向的collection中移除迭代器返回的最后一个元素
6. }

·抽象类AbstractCollection,实现了Collection接口

在AbstractCollection抽象类里,实现了下列方法:

在java的API文档里面标明可选操作的方法,在子类中如果需要则需要重写该方法,否则会报new UnsupportedOperationException();

1. boolean isEmpty()方法,源码如下,

这里并没有提供size()的实现,所以需要在子类中实现size()方法

1. publicboolean isEmpty(){
2. return size()==0;
3. }

2. boolean contains(Object o),在该方法中,允许传入null值,如果元素中有null,则返回true

实现原理:取迭代器,如果传入null,则循环判断是否有null元素,有则true;如果传入不为null,则遍历迭代器,利用equals()方法进行判断是否相等;同样的iterator()方法需要在子类中实现.

1. publicboolean contains(Object o){
2. Iterator<E> e = iterator();
3. if(o==null){
4. while(e.hasNext())
5. if(e.next()==null)
6. returntrue;
7. }else{
8. while(e.hasNext())
9. if(o.equals(e.next()))
10. returntrue;
11. }
12. returnfalse;
13. }

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

1. publicboolean addAll(Collection<?extends E> c){
2. boolean modified =false;
3. Iterator<?extends E> e = c.iterator();
4. while(e.hasNext()){
5. if(add(e.next()))
6. modified =true;
7. }
8. return modified;
9. }

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接口的方法此处省略):

1. package java.util;
2. publicinterfaceList<E>extendsCollection<E>{
3. //...继承自Collection的抽象方法省略
4. E get(int index);//返回列表中指定位置的元素
5. E set(int index, E element);//用指定元素替换列表中指定位置的元素
6. void add(int index, E element);//在列表的指定位置插入元素
7. E remove(int index);//删除指定位置上的元素
8. int indexOf(Object o);//返回此列表中第一次出现的指定元素的索引；如果此列表不包含该元素，则返回 -1
9. int lastIndexOf(Object o);//返回此列表中最后出现的指定元素的索引；如果列表不包含此元素，则返回 -1
10. ListIterator<E> listIterator();//返回此列表元素的列表迭代器（按适当顺序）
11. ListIterator<E> listIterator(int index);//返回列表中元素的列表迭代器（按适当顺序），从列表的指定位置开始
12. List<E> subList(int fromIndex,int toIndex);//返回列表中指定的 fromIndex（包括 ）和 toIndex（不包括）之间的子列表
13. }

可以看到,listIterator()方法返回了list列表迭代器,来看下源码:

ListIterator接口:

ListIterator列表迭代器接口,继承了Iterator接口:

1. package java.util;
2. publicinterfaceListIterator<E>extendsIterator<E>{
3.    //继承自Iterator接口的方法就不显示了
4. boolean hasNext();    
5. E next();
6. boolean hasPrevious();    //如果以逆向遍历列表，列表迭代器有多个元素，则返回 true,也就是判断是否存在上一个元素
7. E previous();    //返回上一个元素
8. int nextIndex();    //下一个元素的索引
9. int previousIndex();    //上一个元素的索引
10. void remove();    //从列表中移除由 next 或 previous 返回的最后一个元素
11. void set(E e);    //用指定元素替换next或previous返回的最后一个元素
12. void add(E e);    //将指定的元素插入列表
13. }

抽象类AbstractList

AbstractList继承自AbstractCollection,实现了List接口

在

AbstractList抽象类中,实现了iterator()方法和

listIterator()方法,因为很多方法基于这两个方法来实现,比如

AbstractList里的

indexOf和lastIndexOf方法等;

1.内部类Itr,实现了Iterator接口,一起看下源码(分析写在注释部分):

1. privateclassItrimplementsIterator<E>{
2. int cursor =0;    //当前游标位置
3. int lastRet =-1;    //上一个操作的元素索引
4. int expectedModCount = modCount;    //预期修改数,初始化为外部类的修改数的值,用来作并发判断
5. publicboolean hasNext(){
6. return cursor != size();
7. }
8. //可以看出,iterator中并没有元素容器,他是靠cursor属性和lastRet属性来控制读取和删除操作的
9. public E next(){
10. checkForComodification();
11. try{
12. E next = get(cursor);
13. lastRet = cursor++;
14. return next;
15. }catch(IndexOutOfBoundsException e){
16. checkForComodification();
17. thrownewNoSuchElementException();
18. }
19. }
20. //注意: 不可以连续使用该方法,否则会因为lastRet属性被重置为-1而报异常
21. publicvoid remove(){
22. if(lastRet ==-1)
23. thrownewIllegalStateException();
24. checkForComodification();
26. try{
27. AbstractList.this.remove(lastRet);
28. if(lastRet < cursor)
29. cursor--;
30. lastRet =-1;
31. expectedModCount = modCount;
32. }catch(IndexOutOfBoundsException e){
33. thrownewConcurrentModificationException();
34. }
35. }
36. //此用法用来判断外部修改数和iterator修改数是否一致,不一致会报异常
37. //所以,在使用iterator期间不可以用非iterator方法对list做操作
38. finalvoid checkForComodification(){
39. if(modCount != expectedModCount)
40. thrownewConcurrentModificationException();
41. }
42. }

注意: 在list中使用iterator时千万不要使用非

iterator方法对list进行改动,否则会报异常:java.util.ConcurrentModificationException

2.内部类ListItr,继承了Itr,实现了ListIterator接口;

在Itr的基础上,多了一些方法,支持向前读,插入,set等操作;

提供了一个带参构造函数,设置cursor参数的值.

1. privateclassListItrextendsItrimplementsListIterator<E>{
2. ListItr(int index){
3. cursor = index;
4. }
6. publicboolean hasPrevious(){
7. return cursor !=0;
8. }
10. public E previous(){
11. checkForComodification();
12. try{
13. int i = cursor -1;
14. E previous = get(i);
15. lastRet = cursor = i;
16. return previous;
17. }catch(IndexOutOfBoundsException e){
18. checkForComodification();
19. thrownewNoSuchElementException();
20. }
21. }
23. publicint nextIndex(){
24. return cursor;
25. }
27. publicint previousIndex(){
28. return cursor-1;
29. }
31. publicvoid set(E e){
32. if(lastRet ==-1)
33. thrownewIllegalStateException();
34. checkForComodification();
36. try{
37. AbstractList.this.set(lastRet, e);
38. expectedModCount = modCount;
39. }catch(IndexOutOfBoundsException ex){
40. thrownewConcurrentModificationException();
41. }
42. }
44. publicvoid add(E e){
45. checkForComodification();
47. try{
48. AbstractList.this.add(cursor++, e);    //在当前游标索引处插入元素,然后光标自增1
49. lastRet =-1;
50. expectedModCount = modCount;
51. }catch(IndexOutOfBoundsException ex){
52. thrownewConcurrentModificationException();
53. }
54. }
55. }

 

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

3.带参构造方法,参数为Collection实例

 

ArrayList类中的重要属性包括:

1. privatetransientObject[] elementData;    //容器
2. privateint size;    //记录元素个数
3. protected transient int modCount = 0;    //结构上改动的次数,例如扩容操作,继承自AbstractList父类

ArrayList类中的常用方法:

1. 扩容 

public

void

ensureCapacity

(

int

minCapacity

)

从源码中可以看出,当传入参数大于当前容量时有效,该方法扩容至少为 原容量的1.5倍+1并取整

1. publicvoid ensureCapacity(int minCapacity){
2. modCount++;
3. int oldCapacity = elementData.length;
4. if(minCapacity > oldCapacity){
5. Object oldData[]= elementData;
6. int newCapacity =(oldCapacity *3)/2+1;
7. if(newCapacity < minCapacity)
8. newCapacity = minCapacity;
9. // minCapacity is usually close to size, so this is a win:
10. elementData =Arrays.copyOf(elementData, newCapacity);
11. }
12. }

2. 将此 ArrayList 实例的容量调整为列表的当前大小

public void trimToSize()

也就是把容器的大小调整为size属性大小

3. indexOf(Object o) 返回某对象在数组容器中第一次出现的索引,没有该元素则返回-1

 

参数可以是null

4. lastIndexOf(Object o) 返回某对象

在数组容器中最后一次出现的索引

,没有该元素则返回-1

参数可以是null

5. 克隆方法

Object clone()

因为超类中的clone()方法是浅拷贝的,所以要实现深拷贝,要在super.clone()之后,将引用变量重新赋值;

1. publicObject clone(){
2. try{
3. ArrayList<E> v =(ArrayList<E>)super.clone();
4. v.elementData =Arrays.copyOf(elementData, size);
5. v.modCount =0;
6. return v;
7. }catch(CloneNotSupportedException e){
8. // this shouldn't happen, since we are Cloneable
9. thrownewInternalError();
10. }
11. }

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: 拷贝长度

1. publicvoid add(int index, E element){
2. if(index > size || index <0)
3. thrownewIndexOutOfBoundsException(
4. "Index: "+index+", Size: "+size);
6. ensureCapacity(size+1);// Increments modCount!!
7. System.arraycopy(elementData, index, elementData, index +1,
8. size - index);
9. elementData[index]= element;
10. size++;
11. }

类似的还有:

插入全部 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,他是列表的头,初始化时会将上下节点都指向自身

1. publicclassLinkedList<E>
2. extendsAbstractSequentialList<E>
3. implementsList<E>,Deque<E>,Cloneable, java.io.Serializable
4. {
5. privatetransientEntry<E> header =newEntry<E>(null,null,null);
6. privatetransientint size =0;
8. publicLinkedList(){
9. header.next = header.previous = header;
10. }
11. ...

 

存放元素的容器为 Entry对象,Entry是

LinkedList的静态内部类,源码如下:

1. privatestaticclassEntry<E>{
2. E element;    //存放元素本身
3. Entry<E> next;    //指向下一个Entry
4. Entry<E> previous;    //上一个Entry
5.    //构造函数形参分别表示: 元素,下一个Entry,上一个Entry
6. Entry(E element,Entry<E> next,Entry<E> previous){
7. this.element = element;
8. this.next = next;
9. this.previous = previous;
10. }
11. }

 

插入数据核心方法 addBefore(E e,Entry<E> entry),在某个entry前插入元素:

1. privateEntry<E> addBefore(E e,Entry<E> entry){
2. Entry<E> newEntry =newEntry<E>(e, entry, entry.previous);
3. newEntry.previous.next = newEntry;    //将上一个节点的下节点指向e
4. newEntry.next.previous = newEntry;    //将下一个节点的上节点指向e
5. size++;
6. modCount++;
7. return newEntry;
8. }

add(e)方法就是通过 addBefore(e,header)在header节点前插入 实现的

 

get(int index) 根据索引查找元素时会判断header正向和反向哪个离索引更近,然后向更近的方向遍历,源码如下:

1. //调用私有方法entry(i)找到对应索引的节点
2. public E get(int index){
3. return entry(index).element;
4. }
5. privateEntry<E> entry(int index){
6. if(index <0|| index >= size)
7. thrownewIndexOutOfBoundsException("Index: "+index+
8. ", Size: "+size);
9. Entry<E> e = header;
10.        //>>位移运算,可以理解为除以2
11.     //当所以在前半部分,就遍历下个节点,一直遍历到该索引的节点
12.     //在后半部分,就遍历上个节点
13. if(index <(size >>1)){    
14. for(int i =0; i <= index; i++)
15. e = e.next;
16. }else{
17. for(int i = size; i > index; i--)
18. e = e.previous;
19. }
20. return e;
21. }

 

删除元素核心方法如下:

删除元素,不论是删除第一个还是最后一个,又或是根据索引删除,或者根据元素删除,步骤大致如下:

1.找到该元素对应的节点,然后调用remove(Object o)方法,该方法核心步骤主要做2,3两步操作;

2.让该节点的上下节点互相指向对方;

3.然后置空该节点的元素和上下节点应用;

注意:该方法会返回被删除元素

1. private E remove(Entry<E> e){
2. if(e == header)
3. thrownewNoSuchElementException();
5. E result = e.element;
6.    //下面2行让上下节点互相指向对方
7. e.previous.next = e.next;
8. e.next.previous = e.previous;
9.    //置空被删除节点的属性
10. e.next = e.previous =null;
11. e.element =null;
12. size--;
13. modCount++;
14. return result;
15. }

 

LinkedList重写了listIterator(int index)方法,内部也存在个私有的内部类ListItr,和AbstractList抽象类中的实现类似,只是由操作索引换成了操作Entry节点,内部还有个nextIndex属性,记录下一个元素的索引,还有个next属性,记录下一个节点.

 

2.2 Set接口

首先,来看下Set接口源码:

1. package java.util;
2. publicinterfaceSet<E>extendsCollection<E>{
3. int size();
4. boolean isEmpty();
5. boolean contains(Object o);
6. Iterator<E> iterator();
7. Object[] toArray();
8. <T> T[] toArray(T[] a);
9. boolean add(E e);
10. boolean remove(Object o);
11. boolean containsAll(Collection<?> c);
12. boolean addAll(Collection<?extends E> c);
13. boolean retainAll(Collection<?> c);
14. boolean removeAll(Collection<?> c);
15. void clear();
16. boolean equals(Object o);
17. int hashCode();
18. }

没啥特殊的方法.基本全是Collection里面的.

AbstractSet抽象类

继承了AbstractCollection抽象类,实现了Set接口

里面就3个方法hashCode(),equals(),removeAll(

ollection

<?>

c

)

1. package java.util;
2. publicabstractclassAbstractSet<E>extendsAbstractCollection<E>implementsSet<E>{
3. protectedAbstractSet(){
4. }
5. publicboolean equals(Object o){
6. if(o ==this)
7. returntrue;
8. if(!(o instanceofSet))
9. returnfalse;
10. Collection c =(Collection) o;
11. if(c.size()!= size())
12. returnfalse;
13. try{
14. return containsAll(c);
15. }catch(ClassCastException unused){
16. returnfalse;
17. }catch(NullPointerException unused){
18. returnfalse;
19. }
20. }
21. publicint hashCode(){
22. int h =0;
23. Iterator<E> i = iterator();
24. while(i.hasNext()){
25. E obj = i.next();
26. if(obj !=null)
27. h += obj.hashCode();
28. }
29. return h;
30. }
31. publicboolean removeAll(Collection<?> c){
32. boolean modified =false;
33. if(size()> c.size()){
34. for(Iterator<?> i = c.iterator(); i.hasNext();)
35. modified |= remove(i.next());    // a |= b; 相当于 a = a | b;
36. }else{
37. for(Iterator<?> i = iterator(); i.hasNext();){
38. if(c.contains(i.next())){
39. i.remove();
40. modified =true;
41. }
42. }
43. }
44. return modified;
45. }
46. }

 

2.2.1 HashSet类

继承了AbstractSet抽象类,实现了Set,Cloneable,和序列化接口

基于HashMap实现的,关于HashMap的介绍看  ★★集合框架--Map

1. package java.util;
2. publicclassHashSet<E>
3. extendsAbstractSet<E>
4. implementsSet<E>,Cloneable, java.io.Serializable
5. {
6. staticfinallong serialVersionUID =-5024744406713321676L;
7. privatetransientHashMap<E,Object> map;
9. privatestaticfinalObject PRESENT =newObject();
11. publicHashSet(){
12. map =newHashMap<E,Object>();
13. }
15. publicHashSet(Collection<?extends E> c){
16. map =newHashMap<E,Object>(Math.max((int)(c.size()/.75f)+1,16));
17. addAll(c);
18. }
20. publicHashSet(int initialCapacity,float loadFactor){
21. map =newHashMap<E,Object>(initialCapacity, loadFactor);
22. }
24. publicHashSet(int initialCapacity){
25. map =newHashMap<E,Object>(initialCapacity);
26. }
28. HashSet(int initialCapacity,float loadFactor,boolean dummy){
29. map =newLinkedHashMap<E,Object>(initialCapacity, loadFactor);
30. }
32. publicIterator<E> iterator(){
33. return map.keySet().iterator();
34. }
36. publicint size(){
37. return map.size();
38. }
40. publicboolean isEmpty(){
41. return map.isEmpty();
42. }
44. publicboolean contains(Object o){
45. return map.containsKey(o);
46. }
48. publicboolean add(E e){
49. return map.put(e, PRESENT)==null;
50. }
52. publicboolean remove(Object o){
53. return map.remove(o)==PRESENT;
54. }
56. publicvoid clear(){
57. map.clear();
58. }
60. publicObject clone(){
61. try{
62. HashSet<E> newSet =(HashSet<E>)super.clone();
63. newSet.map =(HashMap<E,Object>) map.clone();
64. return newSet;
65. }catch(CloneNotSupportedException e){
66. thrownewInternalError();
67. }
68. }
70. privatevoid writeObject(java.io.ObjectOutputStream s)
71. throws java.io.IOException{
73. s.defaultWriteObject();
75. s.writeInt(map.capacity());
76. s.writeFloat(map.loadFactor());
78. s.writeInt(map.size());
80. for(Iterator i=map.keySet().iterator(); i.hasNext();)
81. s.writeObject(i.next());
82. }
84. privatevoid readObject(java.io.ObjectInputStream s)
85. throws java.io.IOException,ClassNotFoundException{
87. s.defaultReadObject();
89. int capacity = s.readInt();
90. float loadFactor = s.readFloat();
91. map =(((HashSet)this)instanceofLinkedHashSet?
92. newLinkedHashMap<E,Object>(capacity, loadFactor):
93. newHashMap<E,Object>(capacity, loadFactor));
95. int size = s.readInt();
97. for(int i=0; i<size; i++){
98. E e =(E) s.readObject();
99. map.put(e, PRESENT);
100. }
101. }
102. }