2016-05-23
1、将集合的接口与实现分离
一个队列接口的最小形式可能类似下面这样:
interface Queue<E> //a simplified form of the interface in the standard library
{
void add(e element);
E remove();
int size();
}
这个接口并没说明队列的实现方式。通常有两种实现：循环数组和链表。
每个实现都通过一个实现了Queue接口的类表示。
//TODO:具体实现
class CircularArrayQueue<E> implements Queue<E> //not an actual library class
{
CircularArrayQueue{int capacity) {}
public void add(E element) {}
public E remove() {}
public int size() {}
private E[] elements;
private int head;
private int tail;
}
class LinkedListQueue<E> implements Queue<E> // not an actual library class
{
LinkedListQueue() {}
public void add(E element) {}
public E remove() {}
public int size() {}
private Link head;
private Link tail;
}
当在程序中使用队列时，一旦构建了集合就不需要知道具体实现方式。因此只有在构建集合对象时，使用具体的类才有意义。可以使用接口类型存放集合的引用（父类引用指向子类对象–多态）。
Queue<Customer> expressLane = new CircularArrayQueue<>();
expressLane.add(new Customer("Harry");
利用这种方式，可轻松使用另外一种不同的实现。只需要对程序调用构造器的地方进行修改。
Queue<Customer> expressLane = new LinkedListQueue<>();
expressLane.add(new Customer("Harry");
循环数组比链表更高效，但也需要付出一定的代价。循环数组是一个有界集合，即容量有限。如果程序中要收集的对象数量没有上限，就最好使用链表来实现。
2、迭代器
Iterator接口包含3个方法：
public interface Iterator<E>
{
E next();
boolean hasNext();
void remoce();
}
通过反复调用next方法，可以逐个访问集合中的每一个元素。但如果到达了集合的末尾，next方法将抛出一个NoSuchElementException。因此，需要在调用next之前调用hasNext方法。
Java迭代器查找操作与位置变更是紧密相连的。查找一个元素的唯一方法是调用next，而在执行查找操作的同时，迭代器的位置随之向前移动。
因此，应该将Java迭代器认为是位于两元素之间。当调用next时，迭代器就是越过下一个元素，并返回刚刚越过的那个元素的引用。
3、删除元素
Iterator接口的remove方法将会删除上次调用next方法时返回的元素。大多数情况下，在决定删除某个元素之前应该先看一下这个元素是很具有实际意义的。然而，如果删除指定位置上的元素，仍然需要越过这个元素。具体方法如下：
Iterator<String> it = c.iterator();
it.next(); //Skip over the first element
it.remove(); //now remove it
更重要的是，对next方法和remove方法的调用具有互相依赖性。如果调用remove之前没有调用next将是不合法的。会抛出IllegalStateException异常。
4、链表
链表将每个对象存放在独立的结点中，每个节点还存放着序列中下一个结点的引用。在Java程序设计语言中，所有链表实际上都是双向链接的（doubly linked)–即每个结点还存放着指向前驱结点的引用。
如果多次调用 Iterator.add 方法，将按照提供的次序把元素添加到链表中。他们被依次添加到迭代器当前位置之前。
当用一个刚刚由Iterator方法返回，并指向链表表头的迭代器调用add操作时，新添加的元素将变成列表的新表头。当迭代器越过链表的最后一个元素时（即hasNext返回false)，添加的元素将变成列表的新表尾。如果链表有n个元素，有n+1个位置可以添加新元素这些位置与迭代器的n+1个可能的位置相对应。
set方法用一个新元素取代调用next或previous方法返回的上一个元素。
５、散列集
散列表(hash table)可以快速地查找所需要的对象。散列表为每个对象计算一个整数，称为散列码(hash code)。
在Java中，散列表用链表数组实现。每个列表称为桶(bucket)。要想查找表中对象的位置，就要先计算它的散列码，然后与桶的总数取余，所得到的结果就是保存这个元素的桶的索引。或许在这个桶中没有其他的元素，此时将元素直接插入到桶中就可以了。有时候会遇到桶被占满的情况，这也是不可避免的。此现象被称为散列冲突(hash collision)。这时，需要用新对象与桶中的所有对象进行比较，查看这个对象是否已经存在。
Java集合类库提供了一个HashSet类，set是没有重复元素的元素集合，它实现了基于散列表的集。set的add方法首先在集中查找要添加的对象，如果不存在就添加进去。散列集迭代器将依次访问所有的桶，由于散列将元素分散在表的各个位置上，所以访问他们的顺序几乎是随机的。只有不关心集合中元素的顺序时才应该使用HashSet。
近期评论