Collection(一)

¶Collection(一)

¶一. 简述

• 本文是关于 Java Collection 的一一些个人学习概括，先从 Collection 的类结构开始，了解 Collection 包结构设计等。

¶二. 类结构

• 先从整体的Collection UML 图看起:

​ 图 1. Collection 部分类图结构

• 由上图可以看出Collection 接口最主要的几个实现结构都比较类似:抽象类规定的继承自Collection的迭代和继承自Object的通用对象方法，再加上List,Set,Queue等各自数据结构的基本定义，组合成了ArrayList,LinkedList,HashSet,TreeSet这些常用的数据结构。

• 而且从 LinkedList 的设计实现来看，假设要扩充一个循环链表实现的List，只需要增加一个类似Dequeue的CycleQueue定义循环列表所必须的基本方法，再结合继承AbstractList的某个子类就能实现，具有很好的扩展性。

• 比较明显的一个特点是贯穿类结构全程的泛型参数和返回值，Collection接口的泛型设计使得它更具备了通用性，而且也为类型检查提供了遍历，尽可能地避免了不安全转型导致的错误。

• 上图中还可以看到一个直接继承HashSet并实现Set接口的LinkedHashSet,它本身除了构造都是继承过来的方法，实现了和基本的HashSet不同的有序LinkedHashSet,HashSet本身是使用HashMap<K,V>来存储数据的，关于这个会在后续的HashSet笔记中说明。

¶三. 主要方法

• Collection接口本身定义了一个集合数据结构应有的行为，主要是

  • add(E):boolean : 添加泛型元素

    remove(E):boolean : 移除泛型元素

    size():int : 返回集合的元素个数, **TIPS:**和集合内部记录容量的域是分开的，内部域用来做容量判断和扩容等。

    contains(Object):boolean : 判断是否包含Object元素，这里会调用具体Object 实现的 equals 方法,所以没有正确实现 hashCode() 和 equals()方法的对象是无法进行正确判断的。

    iterator():Iterator: 泛型迭代器，对于不能通过下标进行元素获取的集合，提供了迭代方式，进行元素移除也是安全的。

    toArray():Object[] : 将集合转换为具体的对象数组

    ---

  • 从这些方法定义可以看出，一个集合，需要包含添加元素，删除元素，迭代集合，容量查询，包含判断等

¶四. 主要实现

• List 接口: 可重复元素的顺序集合

  • 独有方法：

    • get(int):E : 通过下标获取泛型元素E

      set(int,E):E : 在指定位置插入泛型元素E

      remove(int):E : 重载了remove方法，提供了根据下标移除元素的方法

      indexOf(Object):int : 获得指定元素的下标

      lastIndexOf(Object):int : 获取重复元素的最后一个下标位置

      listIterator():ListIterator: 实现了自己的迭代器方法，ListIterator是List的一个内部类

      …

    • 如果看过ArrayList 的源码实现，就会明白这些根据元素下标操作的方法，是由内部真正存储元素值的数组支撑实现的

    • 和 Collection 的定义的方法相比，对于 List接口的实现类可以更加清晰地预见它会具备什么样的特点

    • 基于索引的操作，可以重复的元素，顺序存储等等

• Set接口: 无序的不可重复集合

  • 独有方法:

    • add(E):boolean : 添加泛型元素,参数数具体的元素

      remove(E):boolean : 移除泛型元素

      contains(Object):boolean : 判断元素是否被包含

      iterator():Iterator: 迭代方法，和 List 接口不一样，Set只是覆盖了迭代方法，返回的还是Iterator<E>

      …

    • 和List 最大的区别就是没有可以通过下标进行操作的方法，意味着无序的存储

    • 而且添加删除元素都是基于具体的对象类型，因此也是需要慎重重写泛型对象的 equals() 和 hashCode()方法，才能正确添加和删除

• Queue接口:顺序队列

  • 独有方法：

    • add(E):boolean : 添加泛型元素，尾插

      remove():boolean : 没有指定下标和参数的移除方法，头出

      poll():E : 删除队头元素并返回该元素

      element():E : 返回队头元素，队列为空时抛出异常

      peek():E : 返回队头元素，队列为空时返回 null

    • 典型的单链表结构，先进先出，头入尾出

• Deque接口：双端队列，允许先进先出(队列)和后进先出(栈)

  • 独有方法

    • addFirst(E) : 头插入，插入失败抛出异常

      addLast(E) : 尾插，插入失败抛出异常

      offerFirst(E) : 在队列头部插入元素，在有界队列中使用推荐使用这个方法进行元素插入

      offerLast(E): 在队列尾部插入元素，同样推荐在有界队列中使用，插入失败不会抛出异常

      removeFirst():E : 移除并返回队头元素，队列为空时抛出异常

      removeLast():E : 移除并返回队尾元素，队列为空时抛出异常

      pollFirst():E : 移除并返回对头元素，队列为空返回 Null

      pollLast():E : 移除并返回队尾元素，队列为空时返回null

      peekFirst():E : 获得队头元素，对列为空时返回null

      peekLast():E : 获得队尾元素,空队列时返回null

      removeFirstOccurrence(Object):boolean : 移除第一次出现在队列中的元素 Object

      removeLastOccurence(Object):boolean : 移除最后一次出现的元素 Object

      push(E) : 压栈,队列容量不足时抛出异常

      pop(E) : 弹栈

      • 有一些方法作用类似，在某些情况下甚至是一样的，区别在于对空队列时的处理，是抛出异常还是返回null
      • 明显的压栈，弹栈方法，让它可以作为栈的父类继承实现

• SortedSet<E>: 通过 E 元素的 Comparable 属性或者创建时提供的Comparator，有序的 Set 集合

  • 独有方法

    • first():E : 返回优先级最低的元素，空集合时抛出异常

      last():E : 返回优先级最高的元素，空集合时抛出异常

      headSet(E):SortedSet: 以所有小于 E 的元素组成 SortedSet 并返回 ，空集合时抛出异常

      tailSet(E):SprtedSet: 以所有大于等于E 的元素组成 SortedSet 并返回

      comparator():Comparator<? extends E> : 返回集合用于排序的 comparator

    • 可排序的 Set 集合,是通过它包含的元素的 comparator() 方法或者默认的比较规则实现的，还包括 equals的方法

    • headSet 和 tailSet 方法分别返回小于参数元素和大于等于参数元素的 SortedSet

  ---

• 以上这几个接口就是Collection 接口的主要实现接口和实现接口的子接口，他们各自重写或者重载的方法，让他们具备了形容指定数据结构的能力

• 这也是构成常用集合数据结构的基础，常用的集合数据结构更加明确地定义了集合的含义，并提供了扩展能力等