Java集合框架

一、集合框架简介
  数据结构是以某种形式将数据组织在一起的集合。数据结构不权存储数据，还支持那些访问和处理数据的操作。Java提供了几个能更有效地组织和操作数据的数据结构，这些数据结构通常称为Java集合框架。
  在面向对象思想里，一种数据结构也被认为是一个容器，它是一个能存储其他对象的对象，这里的其它对象指数据或者元素，有此人将数据结构称为容器对象。Java集合框架支持以下两种类型的容器：
    一种是为了存储一个元素组合，简称为集合（collection）。
    另一种是为了存储键值对，称为图（map）。
  collection和map结构图如下：


二、集合
  Java集合框架支持三种类型的集合：规则集（Set）、线性表（List）和队列（Queue）。
1. Collection接口和AbstractCollection类
  Collection接口是处理对象集合的根接口。AbstractCollection类是提供Collection接口部分实现的便利抽象类。除了size方法和iterator方法外，它实现Collection接口中的所有方法。

2. Collection中的公共方法
  1）public boolean add(E e) //向集合中增加元素
  2）public boolean addAll(Collection<? Extends E> c) //将集合c中的所有元素添加到这个集合
  3）public void clear() //删除集合中的所有元素
  4）public boolean contains(Object o) //判断是否有元素o
  5）public boolean containsAll(Collection<?> c) //判断是否有集合c中的所有元素
  6）public boolean equals(Object o) //对象比较
  7）public int hashCode() //返回hash码
  8）public boolean isEmpty() //判断集合的元素是否为空
  9）public Iterator<E> iterator() //返回集合中元素的迭代器
  10）public boolean remove(Object o) //从集合中删除元素o
  11）boolean removeAll(Collection<?> c) //从集合中删除集合c中存在的所有元素
  12）public boolean retainAll(Collection<?> c) //保留集合c中存在的内容
  13）public int size() //返回集合的元素个数
  14）public Object[] toArray() //将集合转化为对象数组

三、规则集（Set）
  规则集不能存储重复的元素。
1. Set接口和AbstractSet类
  Set接口扩展了Collection接口，它没有引入新的方法或常量，只是规定Set的实例不包含重复的元素。AbstractSet类是一个便利类，它扩展AbstractCollection类并实现Set接口。Set接口三个具体类是：散列类HashSet、链式散列集LinkedHashSet和树形集TreeSet。

2. 散列集HashSet
  HashSet类是一个用于实现Set接口的具体类，同样不能有重复的元素，且字符串在插入时没有按照插入时的顺序存储。如果需要顺序存储就要用到后面说到的LinkedHashSet类。HashSet的创建方式有：
    Set<String> set1 = new HashSet<String>();
    Set<String> set2 = new HashSet<String>(set1);
    Set<String> set3 = new HashSet<String>(16);
    Set<String> set4 = new HashSet<String>(16, 0.75f);
  说一下上面的第4种方式 ，其中16表示容量，0.75表示客座率，客座率的作用是当容量超过16*0.75=12时，容量自动翻倍变成32。
  考虑到效率的因素，添加到散列集中的对象必须以一种正确分散散列码的方式来实现hashCode方法。两个不相等的对象可能会有相同的散列码，因此你应该实现hashCode方法以避免出现太多这样的情况。

3. 链式散列集LinkedHashSet
  LinkedHashSet是一个用链表实现来扩展HashSet类的类，它支持对规则集内的元素排序，可以按照元素被插入时的顺序提取。它的创建方式和上面的HashSet完全相同。

4. 树形集TreeSet
  SortedSet接口是Set的一个子接口，它可以确保规则集中的元素是有序的，它还提供了以下方法：
    first() //返回规则集中的第一个元素
    last() //返回规则集中的最后一个元素
    headSet(e) //返回规则集中元素小于e的元素
    tailSet(e) //返回规则集中元素大于e的元素

  NavigableSet接口是SortedSet接口的一个子接口，它增加了如下方法：
    lower(e) //返回小于元素e的元素
    floor(e) //返回小于等于元素e的元素
    ceiling(e) //返回大于等于元素e的元素
    higher(e) //返回大于元素e的元素
    pollFirst() //删除并返回规则集中的第一个元素
    pollLast() //删除并返回规则集中的最后一个元素

  TreeSet是实现了SortedSet接口的一个具体类，在创建TreeSet对象时只要对象是可以互相比较的，就可以将它们添加到一个树形集中。每次给TreeSet对象添加元素的时候，树形集中的元素都会被重新排序。通常先将元素放入HashSet中，然后一次性赋给TreeSet，这样就只用排一次序。

四、线性表（List）
  线性表不仅可以存储重复元素，而且允许用户指定它们存储的位置，用户可以用下标来访问元素。
1. List接口
  List接口扩展了Collection接口，它增加了面向位置的操作，并且增加了一个能够遍历线性表的新列表迭代器。AbstractList类提供了List接口的部分实现。List接口中的新方法如下：
  public void add(int index, E element) //在指定的位置处加入一个元素
  public boolean addAll(int index, Collection<? extends E> c) //在指定的位置加入一组元素
  public E get(int index) //通过索引位置可以取出单个元素
  public int indexOf(E element) //返回第一个匹配的元素的下标
  public int lastIndexOf(E element) //返回最后一个匹配的元素的下标
  public listIterator<E> listIterator() //返回元素列表迭代器
  public E remove(int index) //删除指定位置元素
  public E set(int index, E element) //设置指定位置元素
  public List<E> subList(int index1, int index2) //返回子列表

2. 数组线性表类ArrayList
  ArrayList是List接口的一个具体类，它用数组存储元素，这个数组是动态创建的。如果元素个数超过了数组的容量，就创建一个更大的新数组，并将当前数组中的所有元素都复制到新数组中。注意容量不能自动减小，但可以手动设置减小（trimToSize()）。
  如果需要通过下标随机访问元素，但是除了在末尾处之外不能在其它位置插入或删除元素，就应该选择ArrayList类。如果不需要在线性表中插入或删除元素，那么数组是效率最高的数据结构。
  ArrayList创建方式有：
    List<String> list1 = new ArrayList<String>();
    List<String> list2 = new ArrayList<String>(list1);
    List<String> list3 = new ArrayList<String>(100);

3. 链表类LinkedList
  LinkedList也是List接口的一个具体类，但他同时也实现了Deque接口，它是在一个链表里存储元素。
  如果应用程序需要在线性表的任意位置上插入或删除元素，就应该选择LinkedList类。
  LinkedList可以通过无参构造函数和传递一个Collection来创建，它还增加了如下方法：
  public void addFirst(E e) //将元素添加到列表头
  public void addLast(E e) //将元素添加到列表尾
  public E getFirst() //返回表头元素
  public E getLast() //返回表尾元素
  public E removeFirst() //返回和删除表头元素
  public E removeLast() //返回和删除表尾元素

4. 向量类Vector和栈类Stack
  Vector类实现了List接口，除了包含用于访问和修改向量的同步方法之外，Vector类与ArrayList类是一样的。对于许多不需要同步的应用程序来说，使用ArrayList比使用Vector效率更高。类主要方法有：
    Vector() //创建一个默认为10的空向量
    Vector(Collection<? Extends E> c) //创建来自现有集合的向量
    Vector(int ca) //创建指定初始容量的向量
    Vector(int ca, int in) //创建指定初始容量和增加的向量
    public void addElement(E e) //在向量的末尾追加一个向量
    public int capacity() //返回向量的当前容量
    public void copyInto(Object[] array) //将向量中的元素复制给数组
    public E elementAt(int index) //返回指定下标处的对象
    public Enumeration<E> elements() //返回向量的枚举
    public void ensureCapacity() //增加向量的容量
    public E firstElement() //返回向量的第一个元素
    public void insertElementAt(E e, int index) //将e插入指定下标处
    public E lastElement() //返回向量的最后一个元素
    public void removeAllElement() //删除向量中的所有元素
    public boolean removeElement(O o) //删除向量中第一个匹配的元素
    public void removeElementAt(int index) //删除指定下标处的元素
    public void setElement(E e,int index) //在指定下标处设置一个新元素
    public void setSize(int newSize) //设置向量的新尺度
    public void trimToSize() //将向量的容量缩小到它的尺寸

  Stack类是Vector类的一个扩展，类主要方法如下：
    Stack() //创建一个空栈
    public boolean empty() //栈为空返回true
    public E peek() //返回栈顶元素
    public E pop() //返回并删除栈顶元素
    public E push(o) //在栈顶增加一个元素
    public int search(o) //返回指定元素在栈中的位置 

五、队列（Queue）
  队列是一种先进先出的数据结构。元素被追加到队列末尾，然后从队列头删除。在优先队列中，元素被赋予优先级。
1. Queue接口
  Queue接口扩展Collection接口的同时增加了插入、提取和检验操作。如下：
    public boolean offer(E e) //向队列中插入一个元素
    public E poll() //获取并删除队列头，队列为空返回null
    public E remove() //获取并删除队列头，队列为空抛出一个异常
    public E peek() //获取但不删除队列头，队列为空返回null
    public E element() //获取但不删除队列头，队列为空抛出一个异常

2. 双端队列Deque接口
  Deque接口扩展了Queue接口，它支持在两端插入和删除元素。

3. 链表LinkedList类
  LinkedList类也实现了Deque接口，可以使用LinkedList创建一个队列，使用方法在上面的List接口下面已提到。

4. 优先队列PriorityQueue类
  PriorityQueue类实现了一个优先队列，默认情况（不指定Comparator）下优先队列使用Comparable以元素的自然顺序（元素的ASCII值大小）进行排序，拥有最小数值的元素被赋予最高优先级，因此最先从队列中删除。如果几个元素具在相同的最高优先级，其中的任意一个都可以从队列中删除。
    PriorityQueue() //创建一个初始容量为11的默认优先队列
    PriorityQueue(int i) //创建一个指定容量的优先队列
    PriorityQueue(Collection<? extends E> c) //创建一个指定集合的优先队列
    PriorityQueue(int i, Comparator<? super E> c) //创建一个指定容量和比较器的优先队列

六、图
  图是一种按键值存储的元素，图中不能有重复的键，键很像下标，但键可以是任意类型的对象。
1. Map接口和AbstractMap类
  Map接口是图的根接口，AbstractMap类是图的一个便利类，它实现了除entrySet方法之外的所有方法。Map接口提供了查询、更新和获取集合的值和集合的键值的方法。如下：
    public void clear //删除图中所有的条目
    public boolean containsKey(K k) //存在指定键返回true
    public boolean containsValue(V v) //存在指定值返回true
    public Set<Map.Entry<K,V>> entrySet() //返回一个包含图中条目的规则集，Entry是Map接口的一个内部接口
    public V get(K k) //返回指定键对应的值
    public boolean isEmpty() //图为空返回true
    public Set<K> keySet() //返回包含图中键的一个规则集
    public V put(K k, V v) //将一个键值对放入Map
    public void putAll(Map<? extends K,?extends V> m) //将m中所有的条目放入Map中
    public V remove(K k) //删除指定键对应的条目
    public int size() //返回图中的条目个数
    public Collection<V> values() //返回一个图中值的集合

2. HashMap类
  HashMap类是Map接口的一个实现类，它的元素是没有顺序的。对于定位一个值、插入一个映射和删除一个映射而言，HashMap类是高效的。

3. LinkedHashMap类
  LinkedHashMap类用链表实现来扩展了HashMap类，它支持图中条目的排序。它的两种创建方式如下：
    LinkedHashMap() //按插入图的顺序来排序
    LinkedHashMap(M m) //指定一个Map来创建
    LinkedHashMap(initialCapacity,loadFactor,true) //按它们最后一次被访问时的顺序，前两个参数分别是初始容量和客座率。

4. TreeMap类
  SortedMap接口扩展了Map接口，并保持映射以键升序的顺序排列，附加了firstKey、lastKey、HeadMap、tailMap方法。

  NavigableMap接口扩展了SortedMap接口，以提供导航方法lowerKey、floorKey、ceilingKey、hightKey来分别返回小于、小于等于、大于等于、大于某个给定键的键，方法pollFirstEntry和pollLastEntry分别删除和返回树图中的第一个和最后一个条目。

  TreeMap类实现了NavigableMap接口，它在遍历排好顺序的键时最很高效的，键可以使用Comparable接口或Comparator接口来排序。它的两种创建方式如下：
    TreeMap() //假定元素类实现了Comparable接口，则可以用Comparable接口的compareTo方法对图内的元素进行比较。
    TreeMap(M m) //指定一个Map来创建
    TreeMap(Comparator c) //使用比较器中的compare方法按键进行排序。

5. HashTable类
  HashTable也实现了Map接口，除了具有同步功能外与HashMap的用法是一样的。

七、集合框架的操作
1. 比较器接口Comparator
  有时需要将元素插入到一个树形集中，这些元素可能不是java.lang.Comparable（如String、Integer等已实现Comparable的compareTo方法）的实例，这时可以定义一个比较器来比较这些元素。只需创建一个实现java.util.Comparator接口的类，实现以下两个方法即可：
  public int compare(Object e1, Object e2); //如果e1小于e2返回一个负值，如果e1大于e2返回一个正值，若两者相等则返回0。
  public boolean equals(Object e); //如果指定的对象也是一个比较器，并且与这个比较器且有相同的排序，则返回true。

2. Collections工具类
  Collections类提供了一些对集合进行操作的静态方法，如下：
    public void sort(List l) //对指定的列表进行排序
    public void sort(List l, Comparator c) //使用c对指定列表排序
    public int binarySearch(List l, K k) //使用二分查找搜索有充列表中的键
    public int binarySearch(List l, K k, Comparator c) //利用比较器并使用二分查找搜索有序列表中的键
    public void reverse(List l) //颠倒指定的列表
    public Comparator reverseOrder() //返回逆序的比较器
    public void shuffle(List l) //随机打乱指定的列表
    public void shuffle(List l, Random r) //用随机对象打乱指定列表
    public void copy(List l1, List l2) //将源列表复制给目标列表
    public List nCopies(int n, O o) //返回包含n个对象o的副本列表
    public void fill(List l, O o) //用对象填充列表
    public Object max(Collection c) //返回集合中最大对象
    public Object max(Collection c, Comparator c) //按比较器返回集合中最大对象
    public Object min(Collection c) //返回集合中最小对象
    public Object min(Collection c, Comparator c) //按比较器返回集合中最小对象
    public boolean disjoint(Collection c1, Collection c2) //如果c1和c2没有公共元素则返回true
    public int frequency(Collection c, O o) //返回集合中指定元素的出现次数
   
3. 规则集和线性表的性能
  规则集比线性集更加高效。
  如果应用程序用规则集Set就足够，那就用规则集。
  如果程序不需要特别的顺序就选择散列集HashSet。
  在线性表中除了结尾以外的任意位置上进行插入或删除操作，链式线性表会比数组线性表更加有效。

评论

2 楼 ccii 2014-04-26  

tjzx 写道

总结非常不错。图表一目了然

 

1 楼 tjzx 2014-04-25  

总结非常不错。图表一目了然