Java 集合框架分析-概述

在android项目开发过程中,总会使用到Collection,对于一些基础的使用方法还是可以的,但是涉及到较深层次的就有点力不从心了,所以打算开始彻底地学习一下java集合方面的知识点,做个记录总结,本次分析是基于JavaJDK:1.7.0_79,分析工具:AndroidStudio2.0。

相关文章
1、Java集合框架分析-HashMap
2、Java集合框架分析-LinkedHashMap
3、Java集合框架分析-ArrayList
4、Java集合框架分析-LinkedList
5、Java集合框架分析-Iterator
6、Java集合框架分析-HashSet

首先来看下java集合框架的总图,在网上找了两张关于集合框架的架构图:

以下内容是基于以上架构图进行分析总结:

集合框架主要分为两大类:Collection和Map。

Collection

Collection是List、Set等集合高度抽象出来的接口,它包含了这些集合的基本操作,它主要又分为两大部分:List和Set。

List接口通常表示一个列表(数组、队列、链表、栈等),其中的元素可以重复,常用实现类为ArrayList和LinkedList,另外还有不常用的Vector。另外,LinkedList还是实现了Queue接口,因此也可以作为队列使用。

Set接口通常表示一个集合,其中的元素不允许重复(通过hashcode和equals函数保证),常用实现类有HashSet和TreeSet,HashSet是通过Map中的HashMap实现的,而TreeSet是通过Map中的TreeMap实现的。另外,TreeSet还实现了SortedSet接口,因此是有序的集合(集合中的元素要实现Comparable接口,并覆写Compartor函数才行)。

我们看到,抽象类AbstractCollection、AbstractList和AbstractSet分别实现了Collection、List和Set接口,这就是在Java集合框架中用的很多的适配器设计模式,用这些抽象类去实现接口,在抽象类中实现接口中的若干或全部方法,这样下面的一些类只需直接继承该抽象类,并实现自己需要的方法即可,而不用实现接口中的全部抽象方法。

AbstractList继承AbstractCollection实现List

1
2
3
4
5
6
7
8
9
10
11
/**
 * {@code AbstractList} is an abstract implementation of the {@code List} interface, optimized
 * for a backing store which supports random access. This implementation does
 * not support adding or replacing. A subclass must implement the abstract
 * methods {@code get()} and {@code size()}, and to create a
 * modifiable {@code List} it's necessary to override the {@code add()} method that
 * currently throws an {@code UnsupportedOperationException}.
 *
 * @since 1.2
 */
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {}

AbstractSet 继承AbstractCollection实现Set

1
2
3
4
5
6
7
8
/**
 * An AbstractSet is an abstract implementation of the Set interface. This
 * implementation does not support adding. A subclass must implement the
 * abstract methods iterator() and size().
 *
 * @since 1.2
 */
public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E> {}

AbstractCollection实现Collection

1
2
3
4
5
6
7
8
9
10
/**
 * Class {@code AbstractCollection} is an abstract implementation of the {@code
 * Collection} interface. A subclass must implement the abstract methods {@code
 * iterator()} and {@code size()} to create an immutable collection. To create a
 * modifiable collection it's necessary to override the {@code add()} method that
 * currently throws an {@code UnsupportedOperationException}.
 *
 * @since 1.2
 */
public abstract class AbstractCollection<E> implements Collection<E>{}

Map

Map是一个映射接口,其中的每个元素都是一个key-value键值对,同样抽象类AbstractMap通过适配器模式实现了Map接口中的大部分函数,TreeMap、HashMap、WeakHashMap等实现类都通过继承AbstractMap来实现,另外,不常用的HashTable直接实现了Map接口,它和Vector都是JDK1.0就引入的集合类。

TreeMap继承AbstractMap实现NavigableMap

1
2
3
4
5
/*
* @since 1.2
 */
public class TreeMap<K, V> extends AbstractMap<K, V>
        implements SortedMap<K, V>, NavigableMap<K, V>, Cloneable, Serializable {}
1
public interface NavigableMap<K,V> extends SortedMap<K,V> {}

SortedMap接口继承Map接口

1
2
3
4
5
/**
 * A map that has its keys ordered. The sorting is according to either the
 * natural ordering of its keys or the ordering given by a specified comparator.
 */
public interface SortedMap<K,V> extends Map<K,V> {}

HashMap继承AbstractMap

1
public class HashMap<K, V> extends AbstractMap<K, V> implements Cloneable, Serializable {}

WeakHashMap继承AbstractMap

1
2
3
4
5
6
/*
 * @since 1.2
 * @see HashMap
 * @see WeakReference
 */
public class WeakHashMap<K, V> extends AbstractMap<K, V> implements Map<K, V> {}

Iterator

Iterator是遍历集合的迭代器(不能遍历Map,只用来遍历Collection),Collection的实现类都实现了iterator()函数,它返回一个Iterator对象,用来遍历集合,ListIterator则专门用来遍历List。而Enumeration则是JDK1.0时引入的,作用与Iterator相同,但它的功能比Iterator要少,它只能再Hashtable、Vector和Stack中使用。

####

ListIterator继承Iterator

1
2
3
4
5
/**
 * An ListIterator is used to sequence over a List of objects. ListIterator can
 * move backwards or forwards through the list.
 */
public interface ListIterator<E> extends Iterator<E> {}

相关使用总结

1、HashMap的总结

  1. 基于哈希表的一个Map接口实现,存储的对象是一个键值对对象(Entry<K,V>);值得注意的是HashMap不是线程安全的,如果想要线程安全的HashMap,可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。
  2. HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。
  3. HashMap的底层主要是基于数组和链表来实现的,它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。HashMap中主要是通过key的hashCode来计算hash值的,只要hashCode相同,计算出来的hash值就一样。如果存储的对象对多了,就有可能不同的对象所算出来的hash值是相同的,这就出现了所谓的hash冲突。学过数据结构的同学都知道,解决hash冲突的方法有很多,HashMap底层是通过链表来解决hash冲突的。图中,左边部分即代表哈希表,也称为哈希数组,数组的每个元素都是一个单链表的头节点,链表是用来解决冲突的,如果不同的key映射到了数组的同一位置处,就将其放入单链表中。

2、LinkedHashMap的总结

  1. 由于LinkedHashMap继承自HashMap,所以它不仅像HashMap那样对其进行基于哈希表和单链表的Entry数组+next链表的存储方式,而且还结合了LinkedList的优点,为每个Entry节点增加了前驱和后继,并增加了一个为header头结点,构造了一个双向循环链表。(多一个以header为头结点的双向循环链表,也就是说,每次put进来KV,除了将其保存到对哈希表中的对应位置外,还要将其插入到双向循环链表的尾部。)
  2. LinkedHashMap的属性比HashMap多了一个accessOrder属性。当它false时,表示双向链表中的元素按照Entry插入LinkedHashMap到中的先后顺序排序,即每次put到LinkedHashMap中的Entry都放在双向链表的尾部,这样遍历双向链表时,Entry的输出顺序便和插入的顺序一致,这也是默认的双向链表的存储顺序;当它为true时,表示双向链表中的元素按照访问的先后顺序排列,可以看到,虽然Entry插入链表的顺序依然是按照其put到LinkedHashMap中的顺序,但put和get方法均有调用recordAccess方法(put方法在key相同,覆盖原有的Entry的情况下调用recordAccess方法),该方法判断accessOrder是否为true,如果是,则将当前访问的Entry(put进来的Entry或get出来的Entry)移到双向链表的尾部(key不相同时,put新Entry时,会调用addEntry,它会调用creatEntry,该方法同样将新插入的元素放入到双向链表的尾部,既符合插入的先后顺序,又符合访问的先后顺序,因为这时该Entry也被访问了),否则,什么也不做。
  3. 构造函数中有设置accessOrder的方法,如果我们需要实现LRU算法时,就需要将accessOrder的值设定为TRUE。
  4. 在HashMap的put方法中,如果key不为null时且哈希表中已经在存在时,循环遍历table[i]中的链表时会调用recordAccess方法,而在HashMap中这个方法是个空方法,在LinkedHashMap中则实现了该方法,该方法会判断accessOrder是否为true,如果为true,它会将当前访问的Entry(在这里指put进来的Entry)移动到双向循环链表的尾部,从而实现双向链表中的元素按照访问顺序来排序(最近访问的Entry放到链表的最后,这样多次下来,前面就是最近没有被访问的元素,在实现、LRU算法时,当双向链表中的节点数达到最大值时,将前面的元素删去即可,因为前面的元素是最近最少使用的),否则什么也不做。

3、ArrayList的总结

  1. ArrayList底层是基于数组来实现的,可以通过下标准确的找到目标元素,因此查找的效率高;但是添加或删除元素会涉及到大量元素的位置移动,效率低。
  2. ArrayList提供了三种不同的构造方法,无参数的构造方法默认在底层生成一个长度为10的Object类型的数组,当集合中添加的元素个数大于10,数组会自动进行扩容,即生成一个新的数组,并将原数组的元素放到新数组中。
  3. ensureCapacity方法对数组进行扩容,它会生成一个新数组,长度是原数组的1.5倍+1,随着向ArrayList中不断添加元素,当数组长度无法满足需要时,重复该过程。
  4. ArrayList不是同步的(也就是说不是线程安全的,同HashMap、LinkedHashMap一样),如果多个线程同时访问一个ArrayList实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步,在多线程环境下,可以使用Collections.synchronizedList方法声明一个线程安全的ArrayList,例如:List arraylist = Collections.synchronizedList(new ArrayList());

4、LinkedList的总结

  1. 从源码中可以看出,LinkedList的实现是基于双向循环链表的。却别与ArrayList的数组,以及HashMap的线性表和散列表以及LinkedHashMap的线性表和散列表以及双向循环链表。
  2. 我们在搜索链表中的数据时,都会进行判断是否为null的情况,所以LinkedList是允许元素为null的情况的。
  3. LinkedList是基于链表实现的,因此不存在容量不足的问题,所以这里没有扩容的方法。
  4. 源码中还实现了栈和队列的操作方法,因此也可以作为栈、队列和双端队列来使用。
  5. LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。 实现 List 接口,能对它进行队列操作。实现 Deque 接口,即能将LinkedList当作双端队列使用。实现了Cloneable接口,即覆盖了函数clone(),能克隆。实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。同时LinkedList 是非同步的。

Arrays和Collections是用来操作数组、集合的两个工具类。

以上内容是针对开头的那张图进行概括,下面一系列文章进行相关源码的分析,敬请期待!


参考链接:

1、http://blog.csdn.net/ns_code/article/details/35564663
2、http://www.cnblogs.com/hzmark/archive/2012/12/17/CollectionBase.html
3、http://www.cnblogs.com/hzmark/archive/2013/01/05/JavaCollectionSum.html


附录

关于uml图的补充说明:

在UML类图中,常见的有以下几种关系: 泛化(Generalization), 实现(Realization),关联(Association),聚合(Aggregation),组合(Composition),依赖(Dependency)

1. 泛化(Generalization)
【泛化关系】:是一种继承关系,表示一般与特殊的关系,它指定了子类如何特化父类的所有特征和行为。
【箭头指向】:带三角箭头的实线,箭头指向父类

2. 实现(Realization)
【实现关系】:是一种类与接口的关系,表示类是接口所有特征和行为的实现.
【箭头指向】:带三角箭头的虚线,箭头指向接口

3. 关联(Association)
【关联关系】:是一种拥有的关系,它使一个类知道另一个类的属性和方法;如:老师与学生,丈夫与妻子关联可以是双向的,也可以是单向的。双向的关联可以有两个箭头或者没有箭头,单向的关联有一个箭头。
【代码体现】:成员变量
【箭头及指向】:带普通箭头的实心线,指向被拥有者

4. 聚合(Aggregation)
【聚合关系】:是整体与部分的关系,且部分可以离开整体而单独存在。如车和轮胎是整体和部分的关系,轮胎离开车仍然可以存在。 聚合关系是关联关系的一种,是强的关联关系;关联和聚合在语法上无法区分,必须考察具体的逻辑关系。
【代码体现】:成员变量
【箭头及指向】:带空心菱形的实心线,菱形指向整体

5. 组合(Composition)
【组合关系】:是整体与部分的关系,但部分不能离开整体而单独存在。如公司和部门是整体和部分的关系,没有公司就不存在部门。 组合关系是关联关系的一种,是比聚合关系还要强的关系,它要求普通的聚合关系中代表整体的对象负责代表部分的对象的生命周期。
【代码体现】:成员变量
【箭头及指向】:带实心菱形的实线,菱形指向整体

6. 依赖(Dependency)
【依赖关系】:是一种使用的关系,即一个类的实现需要另一个类的协助,所以要尽量不使用双向的互相依赖.
【代码表现】:局部变量、方法的参数或者对静态方法的调用
【箭头及指向】:带箭头的虚线,指向被使用者

各种关系的强弱顺序:
泛化 = 实现 > 组合 > 聚合 > 关联 > 依赖


关于作者:

1. 简书 http://www.jianshu.com/users/18281bdb07ce/latest_articles

2. 博客 http://crazyandcoder.github.io/

3. github https://github.com/crazyandcoder

4. 掘金 https://juejin.im/user/56b96af96240b8005865df59/share