12.3 JCF中的表和优先队列

JCF提供了操作类似于表的集合，称为map，因为它们的元素都包含(键，值)对，其中键用于检索对应的值，换言之，键映射值。JCF把map与集合区分开来，集合用于保存单个值，例如List和Queue。在JCF中，单值集合包含在有三个分支的层次结构中，这三个分支分别用于集合、列表和队列。Map用于保存两个值：键和它映射的值。JCF将map归为第二层，其中包含HashMap和TreeMap。

还要注意，这里的(键，值)对与本章前面和上一章使用的查找关键字略有区别。查找关键字的值内嵌在元素中，而(键，值)对中的键是独立的组件。

JCF为优先队列提供了一个类PriorityQueue，但不直接支持堆或堆算法。PriorityQueue类在本节的最后讨论。

12.3.1 JCF的Map接口

JCF提供的Map接口是map组件层次结构的根。Map接口为许多其他接口、抽象类以及JCF中各种map的实现打下了基础。

Map接口为将键映射到值上的对象创建类提供了必需的架构。它假设这些键-值是唯一的，每个键都可以唯一地映射一个值。下面是Map接口的部分代码：

public interface Map<K, V> {

void clear();

// Removes all mappings from this map(optional operation).

boolean containsKey(object key);

// Returns true if this map contains a mapping for the specified key.

boolean containsValue(object value);

// Returns true if this map maps one or more keys to the specified value.

Set<Map.Entry<K, V>> entrySet();

// Returns a set view of the mappings contained in this map.

V get(object key);

// Returns the value to which this map maps the specified key.

boolean isEmpty();

// Returns true if this map contains no key-value mappings.

Set<K> keySet();

// Returns a set view of the keys contained in this map.

V put(K key, V value);

// Associates the specified value with the specified key in

// this map (optional operation).

V remove(object key);

// Removes the mapping for this key from this map if it is

// present (optional operation).

int size();

// Returns the number of key-value mappings in this map.

Collection<V> values();

// Returns a collection view of the values contained in this map.

} // end Map

注意Map接口提供的方法有：添加(键，值)对的put方法、按键检索值的get方法、按键删除值的remove方法。该接口还提供了把map的所有键作为一个集合来检索的keySet方法、把map的所有值作为一个集合来检索的values方法、以及把map的所有项作为一个集合来检索的entrySet方法。这些方法的执行结果常常称为map的集合值，因为它们从map中返回了集合。注意keySet方法和entrySet方法返回一个Set，Set是Collection的一个子接口。Set接口详见下一节。

如果要按键值以升序返回集合，就应使用SortedMap接口。SortedMap的任意实现方案都允许对键进行自然排序，或提供了Comparator对象，以构建有序的map实例。

entrySet方法把map项返回为Map.Entry<K,V>的集合，如下所示：

public static interface Map.Entry<K,V> {

boolean equals(Object o);

//Compares the specified object with this entry for equality.

K getKey();

// Returns the key corresponding to this entry.

V getValue();

// Returns the value corresponding to this entry.

int hashCode();

// Returns the hash code value for this map emtry.

V setValue(V value);

// Replaces the value corresponding to this entry with the

// specified value (optional operation).

} // end Map.Entry

entrySet方法是唯一使用该数据类型返回map项的方法，所以，如果要以这种方式处理Map中的项，就必须检索这个集合，用set迭代器遍历结果。

创建好map中的一项后，其键-值就不应修改，所以应将它实现为一个不可更改的对象。如果允许修改这个值，map的行为就是不确定的。如果为Map中已有的一个键添加了一项，就要删除最初的映射，把新项插入map，保持map中的唯一键-值关系。

JCF的两个map常用实现方案是HashMap和TreeMap。类HashMap为Map接口提供了散列表实现方案，散列表详见下一章。类TreeMap为SortedMap接口提供了红-黑树实现方案。红-黑树也在下一章讨论。下一节的最后将介绍一个使用类HashMap的例子。

12.3.2 JCF的Set接口

Set接口与Map类似，也是一个有序集合，但它只存储单值数据项。Set和Collection的区别是，Set不允许有重复的元素，重复的元素可用equals方法的结果来确定。下面是Set接口的部分代码：

interface Set<T> extends Collection<T>{

boolean add(T o);

// Adds the specified element to this set if it is not

// already preset(optional operation).

boolean addAll(Collection<? extends T> c);

// Adds all of the elements in the specified collection to this set

// if they are not already preset(optional operation).

void clear();

// Removes all of the elements from this set(optional operation).

boolean contains(object o);

// Returns true if this set contains the specified element.

boolean isEmpty();

// Returns true if this map contains no elements.

Iterator<E> iterator();

// Returns an iterator over the elements in this set.

boolean remove(object o);

// Removes the specified element from this set,

// if it is present (optional operation).

boolean removeAll(Collection<?> c);

// Removes from this set all of the its elements that are contained

// in the specified collection (optional operation).

boolean retainAll(Collection<?> c);

// Retains only the elements in this set that are contained

// in the specified collection (optional operation).

int size();

// Returns the number of elements in this set(its cardinality).

} // end Set

与Map接口的键一样，最好将Set中的元素也指定为不可变，如果把对象插入set后，其值可以修改，Set的行为就是不确定的。因为实现方案无法确定对象的值是否改为与Set中已有的某个值相同。如果要将set的元素用于排序，可以使用子接口SortedSet。

JCF的两个Set常见实现方案是HashSet和TreeSet。类HashSet使用HashMap，为Set接口提供了散列表实现方案，散列表详见下一章。类TreeSet使用SortedSet接口的TreeMap实现方案。

注意Set没有并、差、交等数学操作，这些操作可使用addAll、retainAll和removeAll方法来实现，如下所示：

HashSet <Integer> setA = new HashSet <Integer>();

setA.add(2);

setA.add(3);

setA.add(5);

setA.add(8);

System.out.println("setA => " + setA);

HashSet <Integer> setB = new HashSet<Integer>();

setB.add(1);

setB.add(3);

setB.add(7);

setB.add(8);

System.out.println("setB => " + setB);

// Set union

HashSet <Integer> unionSet = new HashSet<Integer>(setA);

unionSet.addAll(setB);

System.out.println("setA union setB => " + unionSet);

// Set intersection

HashSet <Integer> intSet = new HashSet<Integer>(setA);

unionSet.retainAll(setB);

System.out.println("setA intersect setB => " + intSet);

// Set difference (setA – setB)

HashSet <Integer> diffSet = new HashSet<Integer>(setA);

unionSet.retainAll(setB);

System.out.println("setA - setB => " + diffSet);

这段代码的输出如下：

setA => [2,8,3,5]

setB => [9,1,3,7]

setA union setB =>[2,9,8,1,3,7,5]

setA intersect setB =>[3]

setA - setB =>[2,8,5]

下面的程序创建了电话本的两个版本，一个版本未排序（使用HashMap），另一个排好了序（使用SortedMap）。在处理电话本时，还使用了HashSet和Set：

import java.util.*;

public class MapSetExample {

static public void main(String[] args) {

// create some data for the keys, use names

String[] name = {"Smith, Jackson",

"Prichard, Marlene",

"Hayden, Sarah",

"Recoreds, Hal";

"Prichard, Marlene"};

// create corresponding values for the keys

String[] phone = {"212-555-4444",

"806—555-6565",

"401-555-5220",

"445-555-3241",

"715-555-9087"};

// Declare a map to contain the names and phone numbers

HashMap<String, String> phonebook = new HashMap<String, String>();

// Insert the names and phone numbers pairs into the map.

// When the duplicate key "Prichard, Marlene" is inserted, should

// replace original entry.

for (int i=0; i<name.length; i++) {

phonebook.put(name[i[, phone[i]];

} //end for

// print the contents of the map

Set<Map.Entry<String, String>> resultSet = phonebook.entrySet();

Iterator< Map.Entry<String, String>> iter = resultSet.iterator();

Map.Entry<String, String> entry;

System.out.println("Contents of the phone book, using HashMap");

While (iter.hasNext()) {

Entry = iter.next();

System.out.println(entry.getKey() + "\t\t" + entry.getValue());

} //end while

System.out.println("\n");

//Retrieve a map value

System.out.println("Search for " + name[2]);

System.out.println(" – phone number is " +

phonebook.get(name[2]));

//Declare a sorted map to contain the names and phone numbers

TreeMap<String, String> phonebookSorted =

new TreeMap<String, String>();

//Insert the names and phone numbers pairs into the map

// When the duplicate key "Prichard, Marlene" is inserted, should

// replace original entry.

for (int i=0; i<name.length; i++) {

phonebookSorted.put(name[i[, phone[i]];

} //end for

// print the contents of the map

Set<Map.Entry<String, String>> sortedSet = phonebookSorted.entrySet();

iter = sortedSet.iterator();

System.out.println("Contents of the sorted phone book, using TreeMap");

While (iter.hasNext()) {

entry = iter.next();

System.out.println(entry.getKey() + "\t\t" + entry.getValue());

} //end while

} //end main

} //end MapSetExample

这个程序的输出如下：

Contents of the phone book, using HashMap

Recoreds, Hal 445-555-3241

Smith, Jackson 212-555-4444

Hayden, Sarah 401-555-5220

Prichard, Marlene 715-555-9087

Search for Hayden, Sarah

– phone number is 401-555-5220

Contents of the sorted phone book, using TreeMap

Hayden, Sarah 401-555-5220

Prichard, Marlene 715-555-9087

Recoreds, Hal 445-555-3241

Smith, Jackson 212-555-4444

12.3.3 JCF的PriorityQueue类

PriorityQueue类是抽象类AbstractQueue的一个实现。PriorityQueue类有一个数据类型参数，用于传送有序的元素。与SortedMap和SortedTree一样，PriorityQueue类也依赖Comparable接口提供的元素的自然顺序，或使用在创建优先队列时提供的Comparator对象。队列中的元素以升序排列。

在使用任一检索或删除操作时，优先队列都处理最小的元素(位于队列头)。在队列中添加新元素时，要保证维持优先队列中元素的升序顺序。

下面是PriorityQueue类的部分代码：

public class PriorityQueue<T> extends Abstract Queue<T>

implements Serializable {

PriorityQueue(int initialCapacity)

// Creates a PriorityQueue with the specified initial capacity

// that orders its elements according to their

// natural ordering (using Comparable).

PriorityQueue(int initialCapacity, Comparator<? Super T> comparator)

// Creates a PriorityQueue with the specified initial capacity

// that orders its elements according to the specified comparator.

// other constructor available…

boolean add(T o)

// Adds the specified element to this queue.

void clear();

// Removes all elements from the priority queue.

boolean contains(object o);

// Returns true if this priority queue contains the specified element.

Comparator<? Super T> comparator()

// Returns the comparator used to order this collection, or

// null if this collection is sorted according to its elements

// natural ordering (using Comparable).

T element()

// Retrieves, but does not remove, the head of this priority queue.

Iterator<E> iterator();

// Returns an iterator over the elements in this priority queue.

boolean offer(E o);

// Inserts the specified element into this priority queuee.

T peek();

// Retrieves, but does not remove, the head of this queue.

// returning null if this queue is empty.

T poll();

// Retrieves and removes the head of this queue, or null

// if this queue is empty.

boolean remove(object o);

// Removes a single instance of the specified element from this queue

// if it is present.

int size();

// Returns the number of elements in this queue.

} //end PriorityQueue

可以为优先队列提供一个初始容量，该容量可根据需要增长。在该实现中，修改优先队列内容的方法（offer、poll、remove和add）需要O(log(n))时间，remove和contains方法需要O(n)时间，检索方法（peek、element和size）需要O(1)时间。

与JCF中的其他类一样，该实现也为插入、检索和删除操作提供了两个不同的方法。在决定哪个版本更适合应用程序时，应仔细查看规范。例如，peek和element方法都可以进行检索，但不能从优先队列中删除元素。它们的区别是，如果优先队列为空，peek返回null，而element会抛出NoSuchElementException异常。

下面的程序演示了整数值优先队列的用法：

static public void main(String[] args) {

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(10);

pq.offer(87);

pq.offer(2);

pq.offer(10);

pq.offer(5);

System.out.println("The elements will be processed in this order: ");

System.out.println(pq.remove());

While(!pq.isEmpty()) {

System.out.println("," + pq.remove());

}