Jkyo Chen Blog

第十三章 集合

集合 #

集合接口 #

将集合的接口与实现分离 #

//一个队列接口的最小形式可能类似下面这样：
interface Queue {
	void add(E element);
	E remove();
	int size();
}

Java类库中的集合接口和迭代器接口 #

//Collection接口的两个基本方法。
public interface Collection {
	boolean add(E element);
	//如果添加元素确实改变了集合就返回true，如果集合没有发生变化就返回false。
	//如果试图想集中添加一个已经存在的对象，这个添加请求就没有实效，因为集中不允许有重复的对象。

	Iterator iterator();
	//iterator方法用于返回一个实现了Iterator接口的对象。可以使用这个迭代器对象依次返回集合中的元素。
	...
}

迭代器 #

public interface Iterator {
	E next();
	boolean hasNext();
	void remove();
}

Collection c = ...;
Iterator iter = c.iterator();
while (iter.hasNext()) {
	String element = iter.next();
	do something with element
}

//从Java SE 5.0起，这个循环可以采用一种更优雅的缩写方法。用" for each "循环可以更加简练地表示同样的循环操作：
for(String element : c) {
	do something with element
}
//编译器简单地将" for each "循环翻译为带有迭代器的循环。
//" for each "循环可以与实现了Iterable接口的对象一起工作，这个接口只包含一个方法：
public interface Iterable {
	Iterator iterator();
}

删除元素 #

泛型实用方法 #

API java.util.Collection 1.2
	Iterator iterator()
	//返回一个用于访问集合中每个元素的迭代器

	int size()
	boolean isEmpty()
	boolean contains(Object obj)
	boolean containsAll(Collection other)
	boolean add(Object element)
	boolean addAll(Collection other)
	//将other集合中的所有元素添加到这个集合。如果由于这个调用改变了集合，返回true。
	boolean remove(Object obj)
	boolean removeAll(Collection other)
	//从这个集合中删除other集合中存在的所有元素。如果由于这个调用改变了集合，返回true。
	void clear()
	boolean retainAll(Collection other)
	//从这个集合中删除所有与other集合中的元素不同的元素。如果由于这个调用改变了集合，返回true
	Object[] toArray()
	//返回这个集合的对象数组
	 T[] toArray(T[] arrayToFill)
	//返回这个集合的对象数组。如果arrayToFill足够大，就将集合中的元素填入这个数组中。
	//剩余空间填补null；否则，分配一个新数组，其成员类型与ArrayToFill的成员类型相同，其长度等于集合的大小，并添入集合元素。

	java.util.Iterator 1.2
	boolean hasNext()
	//如果存在可访问的元素，返回true
	E next()
	//返回将要访问的下一个对象。如果已经到达了集合的尾部，将抛出一个NoSuchElement Exception
	void remove()
	//删除上次访问的对象。这个方法必须紧跟在访问一个元素之后执行。如果上次访问之后，集合已经发生了变化，这个方法将抛出一个IllegalStateException

具体的集合 #

链表 #

//set方法用一个新元素调用next或previous方法返回的上一个元素。
//将用一个新值取代链表的第一个元素
ListIteratorM iter = list.listIterator();
String oldValue = iter.next();
iter.set(newValue);
//linkedList/LinkedListTest.java
package linkedList;
import java.util.*;

public class LinkedListTest {
	public static void main(String[] args) {
		List a = new LinkedList<>();
		a.add("Amy");
		a.add("Carl");
		a.add("Erica");

		List b = new LinkedList<>();
		b.add("Bob");
		b.add("Dong");
		b.add("Frances");
		b.add("Gloria");

		// merge the words from b into a
		ListIterator aIter = a.listIterator();
		Iterator bIter = b.iterator();

		while (bIter.hasNext()) {
			if (aIter.hasNext()) aIter.next();
			aIter.add(bIter.next());
		}
		System.out.println(a);

		// remove every second word from b
		bIter = b.iterator();
		while (bIter.hasNext()) {
			bIter.next();
			if (bIter.hasNext()) {
				bIter.next();
				bIter.remove();
			}
		}
		System.out.println(b);

		// bulk operation: remove all words in b from a
		a.removeAll(b);

		System.out.println(a);// 通过调用AbstractCollection类中的toString方法打印出链表a中的所有元素。
	}
}

//绘制迭代器示意图
API java.util.List 1.2
	ListIterator listIterator()
	ListIterator listIterator(int index)
	//返回一个列表迭代器，以便用来访问列表中的元素，这个元素时第一次调用next返回的给定索引的元素。
	void add(int i, E element)
	void addAll(int i, Collection elements)
	E remove(int i)
	//删除给定位置的元素并返回这个元素
	E get(int i)
	E set(int i, E element)
	//用新元素取代给定位置的元素，并返回原来那个元素
	int indexOf(Object element)
	//返回与指定元素相等的元素在列表中第一次出现的位置，如果没有这样的元素将返回-1
	int lastIndexOf(Object element)
	//返回最后一次出现的位置

	java.util.ListIterator 1.2
	void add(E newElement)
	//在当前位置前添加已给元素
	void set(E newElement)
	//用新元素取代next或previous上次访问的元素。如果在next或previous上次调用之后列表结构被修改了，将抛出一个IllegalStateException异常。
	boolean hasPrevious()
	//当反向迭代列表时，还有可供访问的元素，返回true
	E previous()
	//返回前一个对象。如果已经到达了列表的头部，就抛出一个NoSuchElementException异常
	int nextIndex()
	//返回下一次调用next方法时将返回的元素索引。
	int previousIndex()

	java.util.LinkedList 1.2
	LinkedList()
	//构造一个空链表
	LinkedList(Collection elements)
	//构造一个链表，并将集合中欧所有的元素添加到这个链表中
	void addFirst(E element)
	void addLast(E element)
	//将某个元素添加到列表的头部或尾部。
	E removeFirst()
	E removeLast()
	//删除并返回列表头部或尾部的元素

数组列表 #

散列集 #

set/SetTest.java

package set;
import java.util.*;

public class SetTest {
	public static void main(String[] args) {
		Set words = new HashSet<>(); // HashSet implements Set
		long totalTime = 0;

		Scanner in = new Scanner(System.in);
		while(in.hasNext()) {
			String word = in.next();
			long callTime = System.currentTimeMillis();
			words.add(word);
			callTime = System.currentTimeMillis() - callTime;
			totalTime += callTime;
		}

		Iterator iter = words.iterator();
		for(int i = 1; i <= 20 && iter.hasNext(); i++)
			System.out.println(iter.next());
		System.out.println("....")';
		System.out.println(words.size() + " distinct words. " + totalTime + " milliseconds. ");
	}
}
API	java.util.HashSet 1.2

	HashSet()
	//构造一个空散列表
	HashSet(Collection elements)
	//构造一个散列集，并将集合中的所有元素添加到这个散列集中。

	HashSet(int initialCapacity)
	//构造一个空的具有指定容量(桶数)的散列集
	HashSet(int initialCapacity, float loadFactor)
	//构造一个具有指定容量和装填因子(一个0.0~1.0之间的数值，确定散列表填充的百分比，当大于这个百分比时，散列表进行再散列)的散列集。

	java.lang.Object 1.0

	int hashCode()
	//返回这个对象的散列码，散列码可以是任何整数，包括正数或负数。equals和hashCode的定义必须兼容，即如果x.equals(y)为true，x.hashCode()必须等于y.hashCode()

树集 #

API java.util.TreeSet 1.2

	TreeSet()
	//构造一个空数集
	TreeSet(Collection

对象的比较 #

//创建了两个Item对象的树集。
//第一个按照部件编号排序，这是Item对象的默认顺序。
//第二个通过使用一个定制的比较器来按照描述信息排序。
// treeSet/TreeSetTest.java

package treeSet;

public class TreeSetTest {
	public static void main(String[] args) {
		SortedSet parts = new TreeSet<>();
		parts.add(new Item("Toaster", 1234));
		parts.add(new Item("Widget", 4562));
		parts.add(new Item("Modem", 9912));
		System.out.println(parts);

		SortedSet sortByDescription = new TreeSet<>(new Comparetor {
			public int compare(Item a, Item b) {
				String descrA = a.getDescription();
				String descrB = b.getDescription();
				return descrA.compareTo(descrB);
			}
		});

		SortByDescription.addAll(parts);
		System.out.println(sortByDescription);
	}
}

//treeSet/Item.java

package treeSet;

import java.util.*;

public class Item implements Comparable {
	private String description;
	private int partNumber;

	public Item(String aDescription, int aPartNumber) {
		description = aDescription;
		partNumber = aPartNumber;
	}

	public String getDescription() {
		return description();
	}

	public String toString() {
		return "[description=" + description + ", partNumber=" + partNumber + "]";
	}

	public boolean equals(Object otherObject) {
		if(this == otherObject) return true;
		if(otherObject == null) return false;
		if(getClass() != otherObject.getClass()) return false;
		Item other = (Item) otherObject;
		return Object.equals(description, other.description) && partNumber == other.partNumber;
	}

	public int hashCode() {
		return Objects.hash(description, partNumber);
	}

	public int compareTo(Item other) {
		return Integer.compare(partNumber, other.partNumber);
	}
}
API java.lang.Comparable 1.2
	int compareTo(T other)

	java.util.Comparator 1.2
	int compare(T a, T b)

	java.util.SortedSet 1.2
	Comparator comparator()
	//返回用于对元素进行排序的比较器。如果元素用Comparable接口的compareTo方法进行比较则返回null
	E first()
	E last()
	//返回有序集中的最小或最大元素

	java.util.NavigableSet 6
	//返回大于value的最小元素或小于value的最大元素，如果没有这样的元素则返回null
	E ceiling(E value)
	E floor(E value)
	//返回大于等于value的最小元素或小于等于value的最大元素，如果没有这样的元素则返回null

	E pollFirst()
	E pollLast()
	//删除并返回这个集中的最大元素或最小元素，这个集为空时返回null。
	Iterator descendingIterator()
	//返回一个按照递减顺序遍历集中元素的迭代器。

	java.util.TreeSet 1.2
	TreeSet()
	//构造一个树集，并使用指定的比较器对其中的元素进行排序。
	TreeSet(Comparator c)
	//构造一个树集，并使用指定的比较器对其中的元素进行排序
	TreeSet(SortedSet elements)
	//构造一个树集，将有序集中的所有元素添加到这个树集中，并使用与给定集相同的元素比较器。

对列与双端对列 #

API java.util.Quene 5.0

	boolean add(E element)
	boolean offer(E element)
	//如果对列没有满，将给定的元素添加到这个双端对列的尾部并返回true。如果对列满了，第一个方法将抛出一个IllegalStateException，而第二个方法返回false。

	E remove()
	E poll()
	//假如对列不空，删除并返回这个对列头部的元素。如果对列是空的，第一个方法抛出NoSuchElementException，而第二个方法返回null。

	E element()
	E peek()
	//如果对列不空，返回这个对列头部的元素，但不删除。如果对列空，第一个方法将抛出一个NoSuchElementException，而第二个方法返回null

	java.util.Deque 6
	void addFirst(E element)
	void addLast(E element)
	boolean offerFirst(E element)
	boolean offerLast(E element)
	//将给定的对象添加到双端对列的头部或尾部。如果对列满了，前面两个方法将抛出一个IllegalStageException，而后面两个方法返回false

	E removeFirst()
	E removeLast()
	E pollFirst()
	E pollLast()
	//如果对列不空，删除并返回对列头部的元素。

	E getFirst()
	E getLast()
	E peekFirst()
	E peekLast()
	//如果对列非空，返回对列头部的元素，但不删除。

优先级对列 #

//显示一个正在运行的优先级对列。与TreeSet中的迭代不同，这里的迭代并不是按照元素的排列顺序访问的。而删除却总是删除剩余元素中优先级数最小的那个元素。
//priorityQueue/PriorityQueueTest.java

package priorityQueue;

public static void main(String[] args) {
	PriorityQueue pq = new PriorityQueue<>();
	pq.add(new GregorianCalendar(1906, Calendar.DECEMBER, 9));
	pq.add(new GregorianCalendar(1815, Calendar.DECEMBER, 10));
	pq.add(new GregorianCalendar(1903, Calendar.DECEMBER, 3));
	pq.add(new GregorianCalendar(1910, Calendar.DECEMBER, 22));

	System.out.println("Iterating over elements...");
	for(GregorianCalendar date : pq)
		System.out.println(date.get(Calendar.YEAR));
	System.out.println("Removing elements...");
	while(!pq.isEmpty())
		System.out.println(pq.remove().get(Calendar.YEAR));
}
API java.util.PriorityQueue 5.0

	PriorityQueue()
	PriorityQueue(int initialCapacity)
	//构造一个用于存放Comparable对象的优先级对列。

	PriorityQueue(int initialCapacity, Comparator c)
	//构造一个优先级对列，并用指定的比较器对元素进行排序

映射表 #

//map/MapTest.java

package map;

import java.util.*;

public class MapTest {
	public static void main(String[] args) {
		Map staff = new HashMap<>();
		staff.put("144-25-5464", new Employee("Amy Lee"));
		staff.put("567-24-2546", new Employee("Harry Hacker"));
		staff.put("157-62-7935", new Employee("Gary Cooper"));
		staff.put("456-62-5527", new Employee("Francesca Cruz"));

		// print all entries
		System.out.println(staff);

		// print all entries
		System.out.println(staff);

		// remove an entry
		staff.remove("567-24-2546");

		//replace an entry
		staff.put("456-62-5527", new Employee("Francesca Miller"));

		// look up a value
		System.out.println(staff.get("157-62-7935"));

		// iterate through all entries
		for (Map.Entry entry : staff.entrySet()) {
			String key = entry.getKey();
			String value = entry.getValue();
			System.out.println("key=" + key + ", value=" + value);
		}
	}
}
API java.util.Map 1.2

	V get(Object key)
	//获取与键对应的值；返回与键对应的对象，如果在映射表中没有这个对象则返回null。
	//键可以为null

	V put(K key, V value)
	//将键与对应的值关系插入到映射表中。
	//如果这个键已经存在，新的对象将取代与这个键对应的旧对象。
	//这个方法将返回键对应的旧值。如果这个键以前没有出现过则返回null。
	//键可以为null，但值不能为null

	void putAll(Map entries)
	boolean containsKey(Object key)
	boolean containsValue(Object value)
	Set> entrySet()
	//返回Map.Entry对象的集视图，即映射表中的键/值对。
	//可以从这个集中删除元素，同时也从映射表中删除了它们。
	//但是，不能添加任何元素

	Set keySet()
	//返回映射表中所有键的集视图。
	//可以从这个集中删除元素，同时也从映射表中删除了它们。
	//但是，不能添加任何元素

	Collection values()
	//返回映射表中所有值的集合视图。可以从这个集中删除元素，同时也从映射表中删除了它们。但是，不能添加任何元素

	java.util.Map.Entry 1.2

	K getKey()
	V getValue()

	V setValue(V newValue)
	// 设置在映射表中与新值对应的值，并返回旧值。

	java.util.HashMap 1.2
	HashMap()
	HashMap(int initialCapacity)
	HashMap(int initialCapacity, float loadFactor)
	//用给定的容量和装填因子构造一个空散列表映射表(装填因子是一个0.0~1.0之间的数值。这个数值决定散列表填充的百分比。一旦到了这个比例，就要将其再散列到更大的表中)。
	//默认装填因子是0.75

	java.util.TreeMap 1.2
	TreeMap(Comparator c)
	//构造一个树映射表，并使用一个指定的比较器对键进行排序

	TreeMap(Map entries)
	//构造一个树映射表，并将某个映射表中的所有条目添加到树映射表中

	TreeMap(SortedMap entries)
	//构造一个树映射表并将某个有序映射表中的所有条目添加到树映射表中，并使用与给定的有序映射表相同的比较器。

	java.util.SortedMap 1.2
	Comparator comparator()
	//返回对键进行排序的比较器。如果键是用Comparable接口的compareTo方法进行比较的，返回null

	K firstKey()
	K lastKey()
	//返回映射表中最小元素和最大元素

专用集与映射表类 #

API java.util.WeakHashMap 1.2

集合框架 #

    Co[Collection] --> It[Iterable]
    L[List] --> Co
    S[Set] --> Co
    Q[Queue] --> Co
    So[SortedSet] --> S
    Na[NavigableSet] --> So
    D[Deque] --> Q

    Sor[SortedMap] --> M[Map]
    Nav[NavigableMap] --> Sor

视图与包装器 #

API java.util.Collections 1.2

	static  Collection unmodifiableCollection(Collection c)
	static  List unmodifiableList(List c)
	static  Set unmodifiableSet(Set c)
	static  SortedSet unmodifiableSortedSet(SortedSet c)
	static  Map unmodifiableMap(Map c)
	static  SortedMap unmodifiableSortedMap(SortedMap c)
	// 构造一个集合视图，其更改器方法将抛出一个UnsupportedOperationException

	static  Collection synchronizedCollection(Collection c)
	static  List synchronizedList(List c)
	static  Set synchronizedSet(Set c)
	static  SortedSet synchronizedSortedSet(SortedSet c)
	static  Map synchronizedMap(Map c)
	static  SortedMap synchronizedSortedMap(SortedMap c)
	// 构造一个集合视图，其方法都是同步的

	static  Collection checkedCollection(Collection c, Class elementType)
	static  List checkedList(List c, Class elementType)
	static  Set checkedSet(Set c, Class elementType)
	static  SortedSet checkedSortedSet(SortedSet c, Class elementType)
	static  Map checkedMap(Map c, Class keyType, Class valueType)
	static  SortedMap checkedSortedMap(SortedMap c, Class keyType, Class valueType)
	// 构造一个集合视图。如果插入一个错误类型的元素，将抛出一个ClassCastException

	static  List nCopies(int n, E value)
	static  Set singleton(E value)
	//构造一个对象视图，它即可以作为一个拥有n个相同元素的不可修改列表，又可以作为一个拥有单个元素的集

	java.util.Arrays 1.2

	static  List asList(E... array)
	//返回一个数组元素的列表视图。这个数组时可修改的，但其大小不可变

	java.util.ListM 1.2

	List subList(int firstIncluded, int firstExcluded)
	//返回给定位置范围内的所有元素的列表视图

	java.util.SortedSet 1.2

	SortedSet subSet(E firstIncluded, E firstExcluded)
	SortedSet headSet(E firstExcluded)
	SortedSet tailSet(E firstIncluded)
	//返回给定范围内的元素视图

	java.util.NavigableSet 6
	NavigableSet subSet(E from, boolean fromIncluded, E to, boolean toIncluded)
	NavigableSet headSet(E to, boolean toIncluded)
	NavigableSet tailSet(E from, boolean fromIncluded)
	//返回给定范围内的元素视图。boolean标志决定视图是否包含边界

	java.util.SortedMap 1.2
	SortedMap subMap(K firstIncluded, K firstExcluded)
	SortedMap headMap(K firstExcluded)
	SortedMap tailMap(K firstIncluded)
	//返回在给定范围内的键条目的映射表视图。

	java.util.NavigableMap 6
	NavigableMap subMap(K from, boolean fromIncluded, K to, boolean toIncluded)
	NavigableMap headMap(K from, boolean fromIncluded)
	NavigableMap tailMap(K to, boolean toIncluded)
	//返回在给定 范围内的键条目的映射表视图。boolean标志决定视图是否包含边界。

批操作 #

集合与数组之间的转换 #

算法 #

排序与混排 #

//shuffle/ShuffleTest.java

package shuffle;

import java.util.*;

public class ShuffleTest {
	public static void main(String[] args) {
		List numbers = new ArrrayList<>();
		for(int i = 1; i <= 49; i++)
			numbers.add(i);
		Collections.shuffle(numbers);
		List winningCombination = numbers.subList(0, 6);
		Collections.sort(winningCombination);
		System.out.println(winningCombination);
	}
}
API java.util.Collections 1.2

	static > void sort(List elements)
	static  void sort(List elements, Comparator C)
	//使用稳定的排序算法，对列表中的元素进行排序。这个算法的时间复杂度是O(n logn)，其中n为列表的长度

	static void shuffle(List elements)
	static void shuffle(List elements, Random r)
	//随机地打乱列表中的元素。这个算法的时间复杂度是O(n a(n))，n是列表的长度，a(n)是访问元素的平均时间

	static  Comparator reverseOrder()
	//返回一个比较器，它用与Comparable接口的compareTo方法规定的顺序的逆序对元素进行排序。

	static  Comparator reverseOrder(Comparator comp)
	//返回一个比较器，它用与comp给定的顺序的逆序对元素进行排序

二分查找 #

API java.util.Collections 1.2

	static > int binarySearch(List elements, T key)
	static  int binarySearch(List elements, T key, Comparator c)
	//从有序列表中搜索一个键，如果元素扩展了AbstractSequentialList类，则采用线性查找，否则将采用二分查找。这个方法的时间复杂度为O(a(n) logn), n是列表的长度，a(n)是访问一个元素的平均时间。
	//这个方法将返回这个键在列表中的索引，如果在列表中不存在这个键将返回负值i。
	//在这种情况下，应该将这个键插入到列表索引-i-1的位置上，以保持列表的有序性。

简单算法 #

编写自己的算法 #

遗留的集合 #

Hashtable类 #

枚举 #

API java.util.Enumeration 1.0

	boolean hasMoreElements()
	E nextElement()

	java.util.Hashtable 1.0

	Enumeration keys()
	//返回一个遍历散列表中键的枚举对象
	Enumeration elements()
	// 返回一个遍历散列表中元素的枚举对象

	java.util.Vector 1.0
	Enumeration elements()
	//返回遍历向量中元素的枚举对象

属性映射表 #

API java.util.Propertier 1.0

	Propertier()
	//创建一个空的属性映射表
	Propertier(Propertier defaults)
	// 创建一个带有一组默认值的空的属性映射表
	String getProperty(String key)
	// 获得属性的对于关系；返回与键对应的字符串。如果映射表不存在，返回默认表中与这个键对应的字符串

	String getProperty(String key, String defaultValue)
	//获得在键没有找到时具有的默认值属性；它将返回与键对应的字符串，如果在映射表中不存在，就返回默认的字符串
	void load(InputStream in)
	//从InputStream加载属性映射表
	void store(OutputStream out, String commentString)
	//把属性映射表存储到OutputStream

栈 #

API java.util.Stacl 1.0

	E push(E item)
	//将item压入栈并返回item
	E pop()
	//弹出并返回栈顶的item。如果栈为空，请不要使用这个方法。
	E peek()
	//返回栈顶元素，但不弹出。如果栈为空，请不要使用这个方法。

位集 #

API java.util.BitSet 1.0

	BitSet(int initialCapacity)
	//创建一个位集
	int length()
	//返回位集的“逻辑长度”，即1加上位集的最高设置位的索引
	boolean get(int bit)
	//获得一个位
	void set(int bit)
	//设置一个位
	void clear(int bit)
	//清除一个位
	void and(BitSet set)
	//这个位集与另一个位集进行逻辑“AND”
	void or(BitSet set)
	void xor(BitSet set)

	void andNot(BitSet set)
	//清除这个位集中对应另一个位集设置的所有位
package sieve;

import java.util.*;

public class Sieve {
	public static void main(String[] s) {
		int n = 2000000;
		long start = System.currentTimeMillis();
		BitSet b = new BitSet(n + 1);
		int count = 0;
		int i;
		for(i = 2; i <= n; i++)
			b.set(i);
		i = 2;
		while(i * i <= n) {
			if(b.get(i)) {
				count++;
				int k = 2*i;
				while(k <= n) {
					b.clear(k);
					k += i;
				}
			}
			i++;
		}
		while(i <= n) {
			if(b.get(i)) count++;
			i++;
		}
		long end = System.currentTimeMillis();
		System.out.println(count + " primes");
		System.out.println((end - start) + " milliseconds");
	}
}