<转>集合接口

集合接口

http://blog.csdn.net/zhunj80/archive/2007/08/16/1746695.aspx

.........................

2.1        集合接口

1.       将集合接口与实现方法分开

 

2.       Java库中的集合接口与迭代器接口

大多数集合类的基本接口是Collection接口,该接口配有两个基本方法:

boolean add(Object obj)  将对象添加给集合,集合发生改变返回true,反之false

Iterator iterator()  返回一个能够实现Iterator接口的对象,迭代器

<o:p> </o:p>

Iterator接口配有下面3个基本方法:

Object next()  依次访问集合中各个元素

boolean hasNext()  判断是否有可访问元素

void remove()  删除上次调用next时返回的元素

访问结构:

Iterator iter = col.iterator();

while(iter.hasNext()){

Object obj = iter.next();

Do something with obj

}

可将迭代器看成是位于各个元素之间;当你调用next时,迭代器便越过下一个元素,并且返回它刚越过的那个元素的引用.对next方法与remove方法的调用是相互关联的.如果调用remove方法之前,没有先对next方法进行过一次调用,那么这是不合法的,会抛出一个异常.由于集合接口与迭代器接口都属于通用接口,因此可以编写能在任何种类的集合上运行的公用方法.

由于Collection接口的方法比较多,如果实现Collection接口的每个类都提供这些方法,那将是非常累赘的;为了使实现程序更容易运行,将一些基本方法变成抽象的方法,并根据它们建立一些例行方法,建立了AbstractCollection类;现在实现一个具体的集合类,只需要扩展AbstractCollection类,就可以了.

<o:p> </o:p>

2.2        具体的集合

1.       链接式列表

数组和数组列表有一个重大的缺点,就是从数组中间删除一个元素时,被删除元素后面的所有元素都必须向前移动,插入新元素时也是一样.链接式列表就能解决这些问题;数组是将对象的引用存放在连续的存储位置中,而链接式列表则将每个对象存放在独立的链接中,链接中还存放着下一个链接的索引.Java中,所有的链接列表都是双重链接.链接式列表是个有序集合,add方法将对象添加到列表的尾部,如果想插入对象到列表中间,可使用迭代器负责选位置.

Java中提供了实现Collection接口的LinkedList类,来作为链接式列表.

LinkedList类的listIterator方法返回一个实现ListIterator接口的迭代器对象; 如下方法:

  get(n)  访问某个特定元素

  for(int i = 0; i< list.size();i++){

    do something with list.get(i);

  }

强烈不建议使用此方法结合循环遍历链接式列表,如上代码;因为每次访问某个元素时,都必须从列表的开头重新开始搜索,list对象根本不将位置信息放入高速缓存,因此效率极低.

<o:p> </o:p>

ListIterator有如下方法:

  previous()  反向遍历一个列表

  hasPrevious() 

  add()  将新元素添加到迭代器位置的前面

  remove()

  set(object)  用一个新元素来取代通过调用next或者previous方法而返回的上一个元素.

  nextIndex()  返回下次调用next时返回的元素的整数索引

  previousIndex()  返回下次调用previous时返回的元素的索引

不能在同一行里两次调用remove方法,add方法只根据迭代器的位置来运行,而remove方法与add方法不同,它根据迭代器的状态来运行.若要避免同时修改列表的异常情况,请遵循一个简单原则:可以根据需要将任意数量的迭代器添加给一个容器,让所有这些迭代器都只能阅读程序.

<o:p> </o:p>

如果有大量元素,并且做插入和删除操作,建议使用LinkedList之类链接式列表;如果只有少数元素,并且想要随机访问元素,那么完全可以使用ArrayList之类的数组或集合;

2.       数组列表

List接口用于描述一个有序的集合,有两种途径可以访问各个元素,一个是通过迭代器,另一个是使用get和set方法;前者非常适用链接式列表,后者非常适用数组.

<o:p> </o:p>

Java集合库提供了实现List接口的ArrayList类, ArrayList类封装了一个动态再分配的Object[]数组.

<o:p> </o:p>

ArrayList类的方法是非同步的,而Vector类的方法是同步的;如果是单个线程来访问元素,且需要一个动态数组时,建议使用ArrayList类;如果是多个线程来访问元素,且需要一个动态数组时,建议使用Vector类;如果用单个线程来访问Vector对象,代码将会在同步操作上浪费相当多的时间,这显然是不必要的;此外,数据量少时ArrayList效率高,反之Vector高.

<o:p> </o:p>

3.       散列集

散列表是个链接式列表的阵列,每个列表称为一个散列表元,散列表为每个对象计算出一个整数,称为散列码,不存在重复的多个元素;若要查找表中的某个对象的位置,只要计算出它的散列码,再将它减去以散列表元的总数为模数的值,得出的数就是拥有该元素的散列表元的索引.如果大致知道散列表最终会拥有多少个元素,那么应该将初始散列表元的数量设置为大约是预期元素数量的150%,最好是将散列表的大小设置成一个素数.在Java中,使用加载因子决定何时要对散列表进行再散列.

Java的集合库提供了一个HashSet类,用于根据散列表来实现一个散列集;构造函数如下:

  HashSet(int initialCapacity)

  HashSet(int initialCapacity,float loadFactor)

只有在不在乎集合中的各个元素的顺序时,才能使用散列集.Java增加了一个类LinkedHashSet,用于跟踪添加给散列集的元素顺序;其迭代器会按照元素的插入顺序来访问各个元素.

<o:p> </o:p>

散列函数

hashCode方法是在Object类中定义的,用于计算字符串的散列码;每个对象都有一个默认的散列码,该散列码是由对象的内存地址派生而来的;默认的散列函数不是很有用,因为带有相同内容的对象可能产生不同的散列码.

<o:p> </o:p>

4.       树集

树集是个有序集合,可以按照任何顺序将元素插入该集合,该元素将被纳入它的相应的排序位置;当迭代通过该集合时,各个值将自动按照排序后的顺序出现;将元素添加给树集的速度要比将它添加给散列表慢,但是仍然比添加到数组或链接式列表中的正确位置快.

Java集合库中提供了TreeSet类.

<o:p> </o:p>

对象的比较

树集假设插入的元素是实现Comparable接口的,它定义了一个单一方法compareTo(Object other);但是使用Comparable接口来定义排序有着明显的局限性,即只能实现该接口一次,如排序规则变化后很难适用.在这种情况下,将一个Comparator对象传递给TreeSet构造函数, Comparator接口拥有方法compare(Object a,Object b),对两个对象进行比较;这样当需要比较两个元素时,便可以使用此比较器.

<o:p> </o:p>

5.       映像

映像用于存放许多关键字/值对;

Java库提供了用于映像的通用两个实现方法,即散列映像和树状映像;散列映像用于对关键字进行散列,如HashMap,而树状映像则使用关键字的综合排序顺序,在搜索树中对关键字进行组织,如TreeMap;散列函数或比较函数只能作用于关键字,与关键字相关的值不能进行散列或者比较.

每当将一个对象添加到映像中时,必须提供一个关键字,put(key,object);若要检索一个对象,必须使用该关键字,没有值返回null, get(object);remove()方法用于从映像中删除元素,size()方法用于返回映像中的项目的数量.

Set keySet()  关键字集

Collection values()  值集

Set entrySet()  关键字/值对集,内部对象是Map.Entry.

<o:p> </o:p>

6.       专用的映像类

弱散列映像

Java集合库提供了WeakHashMap类;垃圾收集器负责跟踪活的对象,只要映像对象是活的,