JAVA:容器

Java中有一些对象被称为容器(container)容器中可以包含多个对象,每个对象称为容器中的一个元素。容器是用对象封装的数据结构(data structure)。
java容器

1
2
3
4
5
6
7
8
9
10
11
12
Array
Collection
├-List
│ ├-LinkedList
│ ├-ArrayList
│ └-Vector
│  └Stack
└-Set
Map
├-Hashtable
├-HashMap
└-WeakHashMap

数组

数组(array)是最常见的数据结构。数组是相同类型元素的有序集合,并有固定的大小(可容纳固定数目的元素)。数组可以根据下标(index)来随机存取(random access)元素。在内存中,数组通常是一段连续的存储单元。

1
2
Human[] persons = new Human[2];
String[] names = {"Tom", "Jerry", "Luffy"};

在说明类型时

  1. 在类型说明(Human)后面增加一个[],来说明是一个数组。
  2. 使用new创建容器时,需要说明数组的大小。
  3. 我们可以使用 数组名[下标] 的方式来调用某个元素。
  4. 我们可以逐个的初始化数组的元素,
  5. 也可以在声明的同时使用{}初始化数组。

对于非基本类型的数组,比如Human[],数组中存储的是对象的引用。

我们可以调用System.arraycopy()方法来有效的复制数组

Collection

Collection只是一个接口(Interface), 不是类(Class)
表(List)和集合(Set)是java.util中定义的两个接口(interface)。这两个接口都继承自Collection接口。通过实施接口,我们可以获得相应的容器。接口不能实例化, 必须通过类实施(implements )接口才可以.

Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素(Elements)。一些 Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接继承自Collection的类,Java SDK提供的类都是继承自Collection的“子接口”如List和Set
我们之前都是使用类(class)来说明引用的类型。事实上,我们也可以用接口(interface)来说明引用的类型。该类型引用所指向的对象必须实施了该接口。

List

List是有序的元素集合,所以可以使用下标来说明元素的位置。集合中的元素可以相等;
List主要分成两类

  • LinkedList实现了List接口,允许null元素。此外LinkedList提供额外的get,remove,insert方法在 LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈(stack),队列(queue)或双向队列(deque)。 List<Integer> l1 = new ArrayList<Integer>();
  •  ArrayList实现了可变大小的数组。它允许所有元素,包括null。ArrayList没有同步。 size,isEmpty,get,set方法运行时间为常数。但是add方法开销为分摊的常数,添加n个元素需要O(n)的时间。其他的方法运行时间为线性。
      每个ArrayList实例都有一个容量(Capacity),即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加,但是增长算法并没有定义。当需要插入大量元素时,在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。

Set接口

  Set是一种不包含重复的元素的Collection,即任意的两个元素e1和e2都有e1.equals(e2)=false,Set最多有一个null元素。
  很明显,Set的构造函数有一个约束条件,传入的Collection参数不能包含重复的元素。
  请注意:必须小心操作可变对象(Mutable Object)。如果一个Set中的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题。
  常用的Set是HashSet
Set<Integer> s1 = new HashSet<Integer>();
HashSet利用Hash函数进行了查询效率上的优化,其contain()方法经常被使用,以用于判断相关元素是否已经被添加过。

Map

Map是键值对的集合。Map中的每个元素是一个键值对,即一个键(key)和它对应的对象值(value)。对于Map容器,我们可以通过键来找到对应的对象。

Map<String, Integer> m1 = new HashMap<String, Integer>();

Map中提供了产生Collection的方法,以支持方便的对键值对的值域进行操作。

Collection<V> values()   Returns:a collection view of the values contained in this map.

接口和实施分离

Java中,容器的接口与实施分离。
Set<Integer> s1 = new HashSet<Integer>();
接口为我们提供了合法的操作。在效果层面上看,不同的实施都有相同的效果。当然,不同的情境下,实施的细节将决定运行效率。

由于多态的缘故, s1在执行的时候还是会调用HashSet的对象方法

Collection的iterator

迭代器

Interator

我们经常用到遍历容器对象的功能,用于访问、或者删除等,使用迭代器和多态可以在不使用容器真实类型的情况下遍历容器对象。

迭代器是一个对象,它的工作是遍历并选择序列中的对象,而客户端程序员不必知道或关心该序列底层的结构。此外,迭代器通常被称为轻量级对象:创建它的代价小。因此,经常可以见到对迭代器有些奇怪的限制;例如,Java的Iterator只能单向移动,这个Iterator只能用来:

  1. 使用方法iterator()要求容器返回一个Iterator。Iterator将准备好返回序列的第一个元素。
  2. 使用next()获得序列中的下一个元素。
  3. 使用hasNext()检查序列中是否还有元素。
  4. 使用remove()将迭代器新近返回的元素删除。

Iterator仅用于遍历集合,Iterator本身并不提供盛装对象的能力,如果需要创建Iterator对象,则必须有一个被迭代的集合。

Iterator必须依附于Collection对象,有一个Iterator对象,则必然有一个怀之关联的Collection对象。Iterator提供了2个方法来迭代访问Collection集合里的元素。

结论:当使用Iterator对集合元素进行迭代时,Iterator并不是把集合元素本身传给了迭代变量,而是把集合元素的值传给了迭代变量,所以修改迭代变量的值对集合元素本身没有任何改变。

ListIterator

ListIterator是一个更加强大的Iterator的子类型,它只能用于各种List类的访问。尽管Iterator只能向前移动,但是ListIterator可以双向移动。它还可以产生相对于迭代器在列表中指向的当前位置的前一个和后一个元素的索引,并且可以使用set()方法替换它访问过的最后一个元素。你可以通过调用listIterator()方法产生一个指向List开始处的ListInterator,并且还可以通过调用listInterator(n)方法创建一个一开始就指向列表索引为n的元素处的ListIterator。

不论Collection的实际类型如何,它都支持一个iterator()的方法,该方法返回一个迭代子,使用该迭代子即可逐一访问Collection中每一个元素。典型的用法如下:

1
2
3
4
    Iterator it = collection.iterator(); // 获得一个迭代子
    while(it.hasNext()) {
      Object obj = it.next(); // 得到下一个元素
    }

此外不同的容器还涉及同步和异步的信息
详情参考 同步容器