第十七章 容器深入研究
2020-10-12 12:00:49
文章目錄
1.完整的容器分類法
2.填充容器
- (1) Collections.nCopies()
- (2) Collections.fill()
- (1) 所有的Collection子型別都有一個接收另一個Collection物件的構造器，用所接收的Collection物件中的元素來填充新的容器
- (2) 泛型便利方法（例如addAll()）可以減少在使用類時所必需的型別檢查數量
- (1) 例
package Chapter17.Example;
import java.util.*;
import net.mindview.util.*;
import static net.mindview.util.Print.*;
class Letters implements Generator<Pair<Integer, String>>,
Iterable<Integer> {
private int size = 9;
private int number = 1;
private char letter = 'A';
public Pair<Integer, String> next() {
return new Pair<Integer, String>(
number++, "" + letter++);
}
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
public Integer next() {
return number++;
}
public boolean hasNext() {
return number < size;
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
}
package Chapter17.Example;
import net.mindview.util.Generator;
import java.util.Iterator;
import java.util.LinkedHashMap;
public class MapData<K, V> extends LinkedHashMap<K, V> {
public MapData(Generator<Pair<K, V>> gen, int quantity) {
for(int i = 0; i < quantity; ++i) {
Pair<K, V> p = (Pair)gen.next();
this.put(p.key, p.value);
}
}
public MapData(Generator<K> genK, Generator<V> genV, int quantity) {
for(int i = 0; i < quantity; ++i) {
this.put(genK.next(), genV.next());
}
}
public MapData(Generator<K> genK, V value, int quantity) {
for(int i = 0; i < quantity; ++i) {
this.put(genK.next(), value);
}
}
public MapData(Iterable<K> genK, Generator<V> genV) {
Iterator var4 = genK.iterator();
while(var4.hasNext()) {
K key = (K) var4.next();
this.put(key, genV.next());
}
}
public MapData(Iterable<K> genK, V value) {
Iterator var4 = genK.iterator();
while(var4.hasNext()) {
K key = (K) var4.next();
this.put(key, value);
}
}
public static <K, V> MapData<K, V> map(Generator<Pair<K, V>> gen, int quantity) {
return new MapData(gen, quantity);
}
public static <K, V> MapData<K, V> map(Generator<K> genK, Generator<V> genV, int quantity) {
return new MapData(genK, genV, quantity);
}
public static <K, V> MapData<K, V> map(Generator<K> genK, V value, int quantity) {
return new MapData(genK, value, quantity);
}
public static <K, V> MapData<K, V> map(Iterable<K> genK, Generator<V> genV) {
return new MapData(genK, genV);
}
public static <K, V> MapData<K, V> map(Iterable<K> genK, V value) {
return new MapData(genK, value);
}
}
package Chapter17.Example;
import net.mindview.util.CountingGenerator;
import net.mindview.util.RandomGenerator;
import static net.mindview.util.Print.print;
public class MapDataTest {
public static void main(String[] args) {
// Pair Generator:
print(MapData.map(new Letters(), 11));
// Two separate generators:
print(MapData.map(new CountingGenerator.Character(),
new RandomGenerator.String(3), 8));
// A key Generator and a single value:
print(MapData.map(new CountingGenerator.Character(),
"Value", 6));
// An Iterable and a value Generator:
print(MapData.map(new Letters(),
new RandomGenerator.String(3)));
// An Iterable and a single value:
print(MapData.map(new Letters(), "Pop"));
}
}
package Chapter17.Example;
public class Pair<K, V> {
public final K key;
public final V value;
public Pair(K k, V v) {
key = k;
value = v;
}
}
- (2) 建立一個Pair<V，K>類，再呼叫Generator.next()方法來組裝Map
- (3) Map介面卡可以使用各種不同的Generator、Iterator和常數值的組合來填充Map初始化物件
- (4) 通過產生一個Iterator還實現了Iterable。
- (1) 例：
package Chapter17.Test5;
import java.util.*;
public class CountingMapData extends AbstractMap<Integer, String> {
private int size;
private static String[] chars = "A B C D E F G H I J K L M N O P Q R S T U V W X Y Z".split(" ");
public CountingMapData(int size) {
if (size < 0) this.size = 0;
this.size = size;
}
private class Entry implements Map.Entry<Integer, String> {
int index;
Entry(int index) {
this.index = index;
}
public boolean equals(Object o) {
return o instanceof Entry && index == ((Entry) o).index;
}
public Integer getKey() {
return index;
}
public String getValue() {
return chars[index % chars.length] + Integer.toString(index / chars.length);
}
public String setValue(String value) {
throw new UnsupportedOperationException();
}
public int hashCode() {
return Integer.valueOf(index).hashCode();
}
}
class EntrySet extends AbstractSet<Map.Entry<Integer, String>> {
public int size() {
return size;
}
private class Iter implements Iterator<Map.Entry<Integer, String>> {
private Entry entry = new Entry(-1);
public boolean hasNext() {
return entry.index < size - 1;
}
public Map.Entry<Integer, String> next() {
entry.index++;
return entry;
}
public void remove() {
throw new UnsupportedOperationException();
}
}
public Iterator<Map.Entry<Integer, String>> iterator() {
return new Iter();
}
}
private Set<Map.Entry<Integer, String>> entries =
new EntrySet();
public Set<Map.Entry<Integer, String>> entrySet() {
return entries;
}
}
package Chapter17.Test5;
public class Test5 {
public static void main(String[] args) {
System.out.println(new CountingMapData(60));
}
}
- (1) 產生容器的測試資料：建立客製化的Collection和Map實現
- (2) 享元設計模式：在普通的解決方案需要過多的物件，或者產生普通物件太佔用空間時使用享元
- (3) 為了建立唯讀的Map，可以繼承AbstractMap並實現entrySet()。為了建立唯讀的Set，可以繼承AbstractSet並實現iterator()和size()
3.Collection的功能方法
- boolean add(T)：像容器新增內容新增失敗返回false
- boolean addAll(Collection<? extends E> c)：新增引數中所有元素，有任意元素新增成功則返回true
- void clear()：移除容器中所有元素
- boolean contains(T)：如果容器已經持有泛型型別T的引數，則返回true
- boolean containsAll(Collection<?>)：如果容器中持有引數中所有元素返回true
- boolean isEmpty()：容器中沒有元素，返回true
- Iterator iterator()：返回一個Iterator，可用來遍歷容器中的元素
- boolean remove(Object o)：如果元素再容器中，則移除一個元素範例。如果做了移除動作，則返回true
- boolean removeAll(Collection<?> c)：一處引數中所有元素。如果有移除動作，則返回true
- boolean retainAll(Collection<?> c)：只儲存引數中元素。Collection發生改變返回true
- int size()：返回容器中元素數目
- Object[] toArray()：返回一個陣列，該陣列包含容器中所有元素
- T[] toArray(T[] a)：返回一個包含所有容器內元素的陣列，但返回型別為T而不簡單是Object
4.可選操作
- 執行各種不同的新增和移除的方法在Collection介面中都是可選操作。這意味著實現類並不需要為這些方法提供功能定義
- 「可選操作」可以防止設計中出現介面爆炸的情況
- 容器應該易學易用，未獲得支援的操作時一種特例，可以延遲到需要時再實現
- 如果一個操作未獲得支援，那麼實現介面會導致UnsupportedOperationException異常
- 未獲支援的操作
- (1) 最常見的未獲支援的操作，都是源於背後由固定尺寸的資料結構支援的容器
- (2) 任何會引起對底層資料結構的尺寸進行修改的方法都會產生一個UnsupportedOperationException異常，以表示對未獲支援操作的呼叫（一個程式設計錯誤）
- (3) 未獲支援的操作只有在執行時才能檢測到，因此它們表示動態型別檢查
5.List的功能方法
- 基本的List很容易使用：大多數時候只是呼叫add()新增物件，使用get()一次取出一個元素，以及呼叫iterator()獲取用於該序列的Iterator
package Chapter17.Example2;
import java.util.*;
import net.mindview.util.*;
import static net.mindview.util.Print.*;
public class Lists {
private static boolean b;
private static String s;
private static int i;
private static Iterator<String> it;
private static ListIterator<String> lit;
public static void basicTest(List<String> a) {//包含每個List都可執行的操作
a.add(1, "x"); // Add at location 1
a.add("x"); // Add at end
// Add a collection:
a.addAll(Countries.names(25));
// Add a collection starting at location 3:
a.addAll(3, Countries.names(25));
b = a.contains("1"); // Is it in there?
// Is the entire collection in there?
b = a.containsAll(Countries.names(25));
// Lists allow random access, which is cheap
// for ArrayList, expensive for LinkedList:
s = a.get(1); // Get (typed) object at location 1
i = a.indexOf("1"); // Tell index of object
b = a.isEmpty(); // Any elements inside?
it = a.iterator(); // Ordinary Iterator
lit = a.listIterator(); // ListIterator
lit = a.listIterator(3); // Start at loc 3
i = a.lastIndexOf("1"); // Last match
a.remove(1); // Remove location 1
a.remove("3"); // Remove this object
a.set(1, "y"); // Set location 1 to "y"
// Keep everything that's in the argument
// (the intersection of the two sets):
a.retainAll(Countries.names(25));
// Remove everything that's in the argument:
a.removeAll(Countries.names(25));
i = a.size(); // How big is it?
a.clear(); // Remove all elements
}
public static void iterMotion(List<String> a) {//使用Iterator遍歷元素
ListIterator<String> it = a.listIterator();
b = it.hasNext();
b = it.hasPrevious();
s = it.next();
i = it.nextIndex();
s = it.previous();
i = it.previousIndex();
}
public static void iterManipulation(List<String> a) {//使用Iterator修改元素
ListIterator<String> it = a.listIterator();
it.add("47");
// Must move to an element after add():
it.next();
// Remove the element after the newly produced one:
it.remove();
// Must move to an element after remove():
it.next();
// Change the element after the deleted one:
it.set("47");
}
public static void testVisual(List<String> a) {//檢視List的操作效果
print(a);
List<String> b = Countries.names(25);
print("b = " + b);
a.addAll(b);
a.addAll(b);
print(a);
// Insert, remove, and replace elements
// using a ListIterator:
ListIterator<String> x = a.listIterator(a.size() / 2);
x.add("one");
print(a);
print(x.next());
x.remove();
print(x.next());
x.set("47");
print(a);
// Traverse the list backwards:
x = a.listIterator(a.size());
while (x.hasPrevious())
printnb(x.previous() + " ");
print();
print("testVisual finished");
}
// There are some things that only LinkedLists can do:
public static void testLinkedList() {//LinkedList專用的操作
LinkedList<String> ll = new LinkedList<String>();
ll.addAll(Countries.names(25));
print(ll);
// Treat it like a stack, pushing:
ll.addFirst("one");
ll.addFirst("two");
print(ll);
// Like "peeking" at the top of a stack:
print(ll.getFirst());
// Like popping a stack:
print(ll.removeFirst());
print(ll.removeFirst());
// Treat it like a queue, pulling elements
// off the tail end:
print(ll.removeLast());
print(ll);
}
public static void main(String[] args) {
// Make and fill a new list each time:
basicTest(
new LinkedList<String>(Countries.names(25)));
basicTest(
new ArrayList<String>(Countries.names(25)));
iterMotion(
new LinkedList<String>(Countries.names(25)));
iterMotion(
new ArrayList<String>(Countries.names(25)));
iterManipulation(
new LinkedList<String>(Countries.names(25)));
iterManipulation(
new ArrayList<String>(Countries.names(25)));
testVisual(
new LinkedList<String>(Countries.names(25)));
testLinkedList();
}
} /* (Execute to see output) *///:~
6.Set和儲存順序
- (1) Set(interface)：存入Set的每個元素都必須是唯一的，因為Set不儲存重複元素。加入Set的元素必須定義equals()方法以確保物件的唯一性。
- (2) HashSet：為快速查詢而設計的Set。存入HashSet的元素必須定義hashCode()
- (3) TreeSet：保持次序的Set，底層為樹結構。使用它可以從set中提取有序的序列。元素必須實現Comparable介面
- (4) LinkedHashSet：具有HashSet的查詢速度，且內部使用連結串列維護元素的順序。元素也必須實現hashCode()方法
- (1) HashSet以某種神祕的順序儲存所有的元素
- (2) LinkedHashSet按照元素插入的順序儲存元素
- (3) 而TreeSet按照排序順序維護元素（按照CompareTo()的實現方式）
- (1) SortedSet中的元素可以保證處於排序狀態
- (2) SortSet：按物件的比較函數對元素排列
- (3) Comparator comparator() 返回當前Set使用的Comparator；或者返回null，表示以自然方式排序
- (4) Object first() 返回容器中第一個元素
- (5) Object last()返回容器最後一個元素
- (6) SortedSet subSet(from,to)生成此Set子集，範圍從from(包含)到 to(不包含)
- (7) SortSet headSet(to) 生成此Set子集，由 小於 to的元素組成
- (8) SortSet tailSet(to) 生成此Set子集，由 大於或等於 from的元素組成
7.佇列
- (1)
package Chapter17.Example3;
import java.util.*;
/**
* @author:YiMing
* @version:1.0
*/
class ToDoList extends PriorityQueue<ToDoList.ToDoItem> {
static class ToDoItem implements Comparable<ToDoItem> {
private char primary;
private int secondary;
private String item;
public ToDoItem(String td, char pri, int sec) {
primary = pri;
secondary = sec;
item = td;
}
/**
* compareable介面裡面就是這麼申明的，比較兩個數，
* 1.大於0就是說明是大於的關係，
* 2.小於0就說明是小於的關係，
* 3.等於0就說明是相等的關係
* @param arg
* @return
*/
public int compareTo(ToDoItem arg) {
if (primary > arg.primary)
return +1;
if (primary == arg.primary)
if (secondary > arg.secondary)
return +1;
else if (secondary == arg.secondary)
return 0;
return -1;
}
public String toString() {
return Character.toString(primary) +
secondary + ": " + item;
}
}
public void add(String td, char pri, int sec) {
super.add(new ToDoItem(td, pri, sec));
}
public static void main(String[] args) {
ToDoList toDoList = new ToDoList();
toDoList.add("Empty trash", 'C', 4);
toDoList.add("Feed dog", 'A', 2);
toDoList.add("Feed bird", 'B', 7);
toDoList.add("Mow lawn", 'C', 3);
toDoList.add("Water lawn", 'A', 1);
toDoList.add("Feed cat", 'B', 1);
while (!toDoList.isEmpty()) System.out.println(toDoList.remove());
}
} /* Output:
A1: Water lawn
A2: Feed dog
B1: Feed cat
B7: Feed bird
C3: Mow lawn
C4: Empty trash
*///:~
- (2) 優先佇列通過實現Comparable進行控制
- (1)
package Chapter17.Example4;
import java.util.LinkedList;
public class Deque<T> {
private LinkedList<T> deque = new LinkedList();
public Deque() {
}
public void addFirst(T e) {
this.deque.addFirst(e);
}
public void addLast(T e) {
this.deque.addLast(e);
}
public T getFirst() {
return this.deque.getFirst();
}
public T getLast() {
return this.deque.getLast();
}
public T removeFirst() {
return this.deque.removeFirst();
}
public T removeLast() {
return this.deque.removeLast();
}
public int size() {
return this.deque.size();
}
public String toString() {
return this.deque.toString();
}
}
package Chapter17.Example4;
import static net.mindview.util.Print.*;
public class DequeTest {
static void fillTest(Deque<Integer> deque) {
for (int i = 20; i < 27; i++)
deque.addFirst(i);
for (int i = 50; i < 55; i++)
deque.addLast(i);
}
public static void main(String[] args) {
Deque<Integer> di = new Deque<Integer>();
fillTest(di);
print(di);
while (di.size() != 0)
printnb(di.removeFirst() + " ");
print();
fillTest(di);
while (di.size() != 0)
printnb(di.removeLast() + " ");
}
} /* Output:
[26, 25, 24, 23, 22, 21, 20, 50, 51, 52, 53, 54]
26 25 24 23 22 21 20 50 51 52 53 54
54 53 52 51 50 20 21 22 23 24 25 26
*///:~
- (2) 雙向佇列可以在任何一端新增或移除元素
- (3) 可以使用組合來建立一個Deque類，並直接從LinkedList中暴露相關的方法
8.理解Map
- (1) HashMap
- (2) TreeMap
- (3) LinkedHashMap
- (4) WeakHashMap
- (5) ConcurrentHashMap
- (6) IdentityHashMap
- (1) HashMap
- Map基於雜湊表的實現（取代了Hashtable）。插入和查詢鍵值對的開銷是固定的。可以i通過構造器設定容量和負載因子，以調整容器的效能
- (2) LinkedHashMap
- 類似於HashMap，但是迭代遍歷它時，取得「鍵值對」的順序是其插入次序，或者是最近最少使用(LRU)次序。只比HashMap慢一點。而在迭代存取時反而更快，因為它使用連結串列維護內部次序
- (3) TreeMap
- 基於紅黑樹實現。檢視「鍵」或「鍵值對」時，他們會被排序（次序由Comparable或Comparator決定）TreeMap的特點在於，所得到的結果是經過排序的。TreeMap是唯一帶有subMap()方法的Map，他返回一個子樹
- (4) WeakHashMap
- 弱鍵 對映，允許釋放對映所指向的物件；這是為解決某類特殊問題而設計的。如果對映之外沒有參照指向某個「鍵」，則此「鍵」可以被垃圾收集器回收
- (5) ConcurrentHashMap
- 一種執行緒安全的Map，它不涉及同步枷鎖。
- (6) IdentityHashMap
- 使用==代替equals()對「鍵」進行比較的雜湊對映
- (1) 使用SortedMap（TreeMap是其現階段的唯一實現），可以確保鍵處於排序狀態
- (2) Comparator comparator()：返回當前Map使用的Comparator;或者返回null，以表示自然排序
- (3) T firstKey()：返回Map中的第一個鍵
- (4) T lastKey()：返回Map中的最後一個鍵
- (5) SortMap subMap(fromKet,toKey)：生成此Map的子集，範圍從fromKey（包含）到toKey（不包含）的鍵確定
- (6) SortMap headMap(toKey)：生成此Map的子集，由鍵 小於toKey的所有鍵值對組成
- (7) SortMap tailMap(fromKey)：生成此Map的子集，由鍵 大於或等於 fromeKey的所有鍵值對組成
- (1) 為了提高速度，LinkedHashMap雜湊化所有的元素，但是在遍歷鍵值對時，卻又以元素的插入順序返回鍵值對
- (2) 可以在構造器中設定LinkedHashMap，使之採用基於存取最近最少使用演演算法，於是沒有被存取過的元素就會出現在佇列的前面
- (3)
package Chapter17.Example5;
import java.util.*;
import net.mindview.util.*;
import static net.mindview.util.Print.*;
public class LinkedHashMapDemo {
public static void main(String[] args) {
LinkedHashMap<Integer, String> linkedMap =
new LinkedHashMap<Integer, String>(
new CountingMapData(9));
print(linkedMap);
// Least-recently-used order:
linkedMap =
new LinkedHashMap<Integer, String>(16, 0.75f, true);
linkedMap.putAll(new CountingMapData(9));
print(linkedMap);
for (int i = 0; i < 6; i++) // Cause accesses:
linkedMap.get(i);//存取前五個後，就被放在最後面了，最後的6，7，8被提前了
print(linkedMap);
linkedMap.get(0);//存取過「0「後也被放到了最後
print(linkedMap);
}
} /* Output:
{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0}
{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0}
{6=G0, 7=H0, 8=I0, 0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0}
{6=G0, 7=H0, 8=I0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 0=A0}
*///:~
9.雜湊與雜湊碼
- hashMap使用equals()判斷當前的鍵是否與表中存在的鍵相同
2 ###### 正確的equals()方法必須滿足下面5個條件：
- (1) 自反性。對任意x，x.equals(x)一定返回true。
- (2) 對稱性。對任意x和y，如果y.equals(x)返回true，則x.equals(y)也返回true。
- (3) 傳遞性。對任意x，y，z,如果有x.equals(y)返回true，y.equals(z)返回true，則x.equals(z)一定返回true。
- (4) 一致性。對任意x和y，如果物件中用於等價比較資訊沒有改變，那麼無論呼叫x.equals(y)多少次，返回結果保持一致。
- (5) 對任何不是null的x，x.equals(null)一定返回false。
- 如果要使用自己的類作為HashMap的鍵，必須同時過載hashCode()和equals()
- 理解hashCode()
- 使用雜湊的目的在於：想要使用一個物件來查詢另一個物件
- (1)
package Chapter17.Example6;
import Chapter17.Test15.MapEntry;
import net.mindview.util.Countries;
import java.util.*;
public class SimpleHashMap<K,V> extends AbstractMap<K,V> {
// Choose a prime number for the hash table
// size, to achieve a uniform distribution:
static final int SIZE = 997;
// You can't have a physical array of generics,
// but you can upcast to one:
@SuppressWarnings("unchecked")
LinkedList<MapEntry<K,V>>[] buckets =
new LinkedList[SIZE];
public V put(K key, V value) {
V oldValue = null;
int index = Math.abs(key.hashCode()) % SIZE;
if(buckets[index] == null)
buckets[index] = new LinkedList<MapEntry<K,V>>();
LinkedList<MapEntry<K,V>> bucket = buckets[index];
MapEntry<K,V> pair = new MapEntry<K,V>(key, value);
boolean found = false;
ListIterator<MapEntry<K,V>> it = bucket.listIterator();
while(it.hasNext()) {
MapEntry<K,V> iPair = it.next();
if(iPair.getKey().equals(key)) {
oldValue = iPair.getValue();
it.set(pair); // Replace old with new
found = true;
break;
}
}
if(!found)
buckets[index].add(pair);
return oldValue;
}
public V get(Object key) {
int index = Math.abs(key.hashCode()) % SIZE;
if(buckets[index] == null) return null;
for(MapEntry<K,V> iPair : buckets[index])
if(iPair.getKey().equals(key))
return iPair.getValue();
return null;
}
public Set<Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> set= new HashSet<Map.Entry<K,V>>();
for(LinkedList<MapEntry<K,V>> bucket : buckets) {
if(bucket == null) continue;
for(MapEntry<K,V> mpair : bucket)
set.add(mpair);
}
return set;
}
public static void main(String[] args) {
SimpleHashMap<String,String> m =
new SimpleHashMap<String,String>();
m.putAll(Countries.capitals(25));
System.out.println(m);
System.out.println(m.get("ERITREA"));
System.out.println(m.entrySet());
}
}
- (2) 雜湊的價值在於速度：雜湊使得查詢得以快速進行
- (3) 陣列並不儲存鍵本身。而是通過鍵物件生成一個數位，將其作為陣列的下標。這個數位就是雜湊碼，由定義在Object中的、且可能由你的類覆蓋的hashCode()方法生成
- (4) HashMap快的原因：不是查詢整個list，而是快速地跳到陣列的某個位置，只對很少的元素進行比較
- (5) 由於雜湊表中的「槽位」（slot）通常稱為桶位（bucket），因此我們將表示實際雜湊表的陣列命名為bucket。為使雜湊分佈均勻，同的數量通常使用質數
- (6) 為了能夠自動處理衝突，使用一個LinkedList的陣列；每一個新的元素只是直接新增到list末尾的某個特定桶中
-
(1) 你無法控制bucket陣列的下標值的產生。這個值依賴於具體的HashMap物件的容量，而容量的改變與容器的充滿程度和負載因子有關
-
(2) 設計hashCode()是最重要的因素是：無論何時，對同一個物件呼叫hasCode()都應該生成個同樣的值
-
(3) 如果你的hashCode()方法依賴於物件中易變的資料，因此資料發生變化時，hashCode()就會生成一個不同的雜湊碼，相當於產生了一個不同的鍵
-
(4) 不應該使hashCode()依賴於具有唯一型的物件資訊，尤其是使用this值，這隻能產生很糟糕的hashCode()，應為這樣無法生成一個新的鍵，使之與put()中源氏鍵值相同
-
(5) String有個特點：如果程式中有多個String物件，都包含相同的字串序列，那麼這些String物件都對映到同一塊記憶體區域
-
(6) 怎樣寫出一份像樣的hashCode基本指導
-
i.
package Chapter17.Example7; import java.util.*; import static net.mindview.util.Print.*; public class CountedString { private static List<String> created = new ArrayList<String>(); private String s; private int id = 0; public CountedString(String str) { s = str; created.add(s); // id is the total number of instances // of this string in use by CountedString: for(String s2 : created) if(s2.equals(s)) id++; } public String toString() { return "String: " + s + " id: " + id + " hashCode(): " + hashCode(); } public int hashCode() { // The very simple approach: // return s.hashCode() * id; // Using Joshua Bloch's recipe: int result = 17; result = 37 * result + s.hashCode(); result = 37 * result + id; return result; } public boolean equals(Object o) { return o instanceof CountedString && s.equals(((CountedString)o).s) && id == ((CountedString)o).id; } public static void main(String[] args) { Map<CountedString,Integer> map = new HashMap<CountedString,Integer>(); CountedString[] cs = new CountedString[5]; for(int i = 0; i < cs.length; i++) { cs[i] = new CountedString("hi"); map.put(cs[i], i); // Autobox int -> Integer } print(map); for(CountedString cstring : cs) { print("Looking up " + cstring); print(map.get(cstring)); } } } /* Output: (Sample) {String: hi id: 4 hashCode(): 146450=3, String: hi id: 1 hashCode(): 146447=0, String: hi id: 3 hashCode(): 146449=2, String: hi id: 5 hashCode(): 146451=4, String: hi id: 2 hashCode(): 146448=1} Looking up String: hi id: 1 hashCode(): 146447 0 Looking up String: hi id: 2 hashCode(): 146448 1 Looking up String: hi id: 3 hashCode(): 146449 2 Looking up String: hi id: 4 hashCode(): 146450 3 Looking up String: hi id: 5 hashCode(): 146451 4 *///:~ -
ii.給int變數result賦予某個非零值常數。例如17
-
iii.為物件內每個有意義的域f計算一個int雜湊碼c：
- boolean
- c=(f?0:1)
- byte,char,short或int
- c=(int)f
- long
- c=(int)(f^(f>>>32))
- float
- c=Float.float.ToIntBits(f)
- double
- long l=Doule.doubleToLongBits(f);c=(int)(l^(l>>>32))
- object,其equals()呼叫這個域的equals()
- c=f.hashCode()
- 陣列
- 對每個元素應用上述規則
- boolean
-
iv.返回result
-
v.檢查hashCode()最後生成結果，確保相同的物件有相同的雜湊碼。
-
-
(7) compareTo()方法有一個比較結構，因此它會產生一個排序序列，排序規則首先按照實際型別排序，然後如果有名字按名字排序，最後按建立順序排序：
package Chapter17.Example7; import typeinfo.pets.Individual; import typeinfo.pets.Pet; import java.util.*; public class IndividualTest { public static void main(String[] args) { Set<Individual> pets = new TreeSet<Individual>(); for(List<? extends Pet> lp : MapOfList.petPeople.values()) for(Pet p : lp) pets.add(p); System.out.println(pets); } } /* Output: [Cat Elsie May, Cat Pinkola, Cat Shackleton, Cat Stanford aka Stinky el Negro, Cymric Molly, Dog Margrett, Mutt Spot, Pug Louie aka Louis Snorkelstein Dupree, Rat Fizzy, Rat Freckly, Rat Fuzzy] *///:~
10.選擇介面的不同實現
- (1) ArrayList（底層由陣列支援）
- (2) LinkedList（底層由雙向連結串列實現）
- (1) HashSet（查詢速度最快）
- (2) LinkedHashSet（保持元素插入順序）
- (3) TreeSet（基於TreeMap，生成一個總是處於排序狀態的Set）
- 效能測試框架
package Chapter17.Example8;
// Framework for performing timed tests of containers.
public abstract class Test<C> {
String name;
public Test(String name) { this.name = name; }
// Override this method for different tests.
// Returns actual number of repetitions of test.
abstract int test(C container, TestParam tp);
} ///:~
package Chapter17.Example8;
// Applies Test objects to lists of different containers.
import java.util.*;
public class Tester<C> {
public static int fieldWidth = 8;
public static TestParam[] defaultParams= TestParam.array(
10, 5000, 100, 5000, 1000, 5000, 10000, 500);
// Override this to modify pre-test initialization:
protected C initialize(int size) { return container; }
protected C container;
private String headline = "";
private List<Test<C>> tests;
private static String stringField() {
return "%" + fieldWidth + "s";
}
private static String numberField() {
return "%" + fieldWidth + "d";
}
private static int sizeWidth = 5;
private static String sizeField = "%" + sizeWidth + "s";
private TestParam[] paramList = defaultParams;
public Tester(C container, List<Test<C>> tests) {
this.container = container;
this.tests = tests;
if(container != null)
headline = container.getClass().getSimpleName();
}
public Tester(C container, List<Test<C>> tests,
TestParam[] paramList) {
this(container, tests);
this.paramList = paramList;
}
public void setHeadline(String newHeadline) {
headline = newHeadline;
}
// Generic methods for convenience :
public static <C> void run(C cntnr, List<Test<C>> tests){
new Tester<C>(cntnr, tests).timedTest();
}
public static <C> void run(C cntnr,
List<Test<C>> tests, TestParam[] paramList) {
new Tester<C>(cntnr, tests, paramList).timedTest();
}
private void displayHeader() {
// Calculate width and pad with '-':
int width = fieldWidth * tests.size() + sizeWidth;
int dashLength = width - headline.length() - 1;
StringBuilder head = new StringBuilder(width);
for(int i = 0; i < dashLength/2; i++)
head.append('-');
head.append(' ');
head.append(headline);
head.append(' ');
for(int i = 0; i < dashLength/2; i++)
head.append('-');
System.out.println(head);
// Print column headers:
System.out.format(sizeField, "size");
for(Test test : tests)
System.out.format(stringField(), test.name);
System.out.println();
}
// Run the tests for this container:
public void timedTest() {
displayHeader();
for(TestParam param : paramList) {
System.out.format(sizeField, param.size);
for(Test<C> test : tests) {
C kontainer = initialize(param.size);
long start = System.nanoTime();
// Call the overriden method:
int reps = test.test(kontainer, param);
long duration = System.nanoTime() - start;
long timePerRep = duration / reps; // Nanoseconds
System.out.format(numberField(), timePerRep);
}
System.out.println();
}
}
} ///:~
package Chapter17.Example8;
// A "data transfer object."
public class TestParam {
public final int size;
public final int loops;
public TestParam(int size, int loops) {
this.size = size;
this.loops = loops;
}
// Create an array of TestParam from a varargs sequence:
public static TestParam[] array(int... values) {
int size = values.length/2;
TestParam[] result = new TestParam[size];
int n = 0;
for(int i = 0; i < size; i++)
result[i] = new TestParam(values[n++], values[n++]);
return result;
}
// Convert a String array to a TestParam array:
public static TestParam[] array(String[] values) {
int[] vals = new int[values.length];
for(int i = 0; i < vals.length; i++)
vals[i] = Integer.decode(values[i]);
return array(vals);
}
} ///:~
package Chapter17.Example9;
// Demonstrates performance differences in Lists.
// {Args: 100 500} Small to keep build testing short
import java.util.*;
import net.mindview.util.*;
public class ListPerformance {
static Random rand = new Random();
static int reps = 1000;
static List<Test<List<Integer>>> tests =
new ArrayList<Test<List<Integer>>>();
static List<Test<LinkedList<Integer>>> qTests =
new ArrayList<Test<LinkedList<Integer>>>();
static {
tests.add(new Test<List<Integer>>("add") {
int test(List<Integer> list, TestParam tp) {
int loops = tp.loops;
int listSize = tp.size;
for(int i = 0; i < loops; i++) {
list.clear();
for(int j = 0; j < listSize; j++)
list.add(j);
}
return loops * listSize;
}
});
tests.add(new Test<List<Integer>>("get") {
int test(List<Integer> list, TestParam tp) {
int loops = tp.loops * reps;
int listSize = list.size();
for(int i = 0; i < loops; i++)
list.get(rand.nextInt(listSize));
return loops;
}
});
tests.add(new Test<List<Integer>>("set") {
int test(List<Integer> list, TestParam tp) {
int loops = tp.loops * reps;
int listSize = list.size();
for(int i = 0; i < loops; i++)
list.set(rand.nextInt(listSize), 47);
return loops;
}
});
tests.add(new Test<List<Integer>>("iteradd") {
int test(List<Integer> list, TestParam tp) {
final int LOOPS = 1000000;
int half = list.size() / 2;
ListIterator<Integer> it = list.listIterator(half);
for(int i = 0; i < LOOPS; i++)
it.add(47);
return LOOPS;
}
});
tests.add(new Test<List<Integer>>("insert") {
int test(List<Integer> list, TestParam tp) {
int loops = tp.loops;
for(int i = 0; i < loops; i++)
list.add(5, 47); // Minimize random-access cost
return loops;
}
});
tests.add(new Test<List<Integer>>("remove") {
int test(List<Integer> list, TestParam tp) {
int loops = tp.loops;
int size = tp.size;
for(int i = 0; i < loops; i++) {
list.clear();
list.addAll(new CountingIntegerList(size));
while(list.size() > 5)
list.remove(5); // Minimize random-access cost
}
return loops * size;
}
});
// Tests for queue behavior:
qTests.add(new Test<LinkedList<Integer>>("addFirst") {
int test(LinkedList<Integer> list, TestParam tp) {
int loops = tp.loops;
int size = tp.size;
for(int i = 0; i < loops; i++) {
list.clear();
for(int j = 0; j < size; j++)
list.addFirst(47);
}
return loops * size;
}
});
qTests.add(new Test<LinkedList<Integer>>("addLast") {
int test(LinkedList<Integer> list, TestParam tp) {
int loops = tp.loops;
int size = tp.size;
for(int i = 0; i < loops; i++) {
list.clear();
for(int j = 0; j < size; j++)
list.addLast(47);
}
return loops * size;
}
});
qTests.add(
new Test<LinkedList<Integer>>("rmFirst") {
int test(LinkedList<Integer> list, TestParam tp) {
int loops = tp.loops;
int size = tp.size;
for(int i = 0; i < loops; i++) {
list.clear();
list.addAll(new CountingIntegerList(size));
while(list.size() > 0)
list.removeFirst();
}
return loops * size;
}
});
qTests.add(new Test<LinkedList<Integer>>("rmLast") {
int test(LinkedList<Integer> list, TestParam tp) {
int loops = tp.loops;
int size = tp.size;
for(int i = 0; i < loops; i++) {
list.clear();
list.addAll(new CountingIntegerList(size));
while(list.size() > 0)
list.removeLast();
}
return loops * size;
}
});
}
static class ListTester extends Tester<List<Integer>> {
public ListTester(List<Integer> container,
List<Test<List<Integer>>> tests) {
super(container, tests);
}
// Fill to the appropriate size before each test:
@Override protected List<Integer> initialize(int size){
container.clear();
container.addAll(new CountingIntegerList(size));
return container;
}
// Convenience method:
public static void run(List<Integer> list,
List<Test<List<Integer>>> tests) {
new ListTester(list, tests).timedTest();
}
}
public static void main(String[] args) {
if(args.length > 0)
Tester.defaultParams = TestParam.array(args);
// Can only do these two tests on an array:
Tester<List<Integer>> arrayTest =
new Tester<List<Integer>>(null, tests.subList(1, 3)){
// This will be called before each test. It
// produces a non-resizeable array-backed list:
@Override protected
List<Integer> initialize(int size) {
Integer[] ia = Generated.array(Integer.class,
new CountingGenerator.Integer(), size);
return Arrays.asList(ia);
}
};
arrayTest.setHeadline("Array as List");
arrayTest.timedTest();
Tester.defaultParams= TestParam.array(
10, 5000, 100, 5000, 1000, 1000, 10000, 200);
if(args.length > 0)
Tester.defaultParams = TestParam.array(args);
ListTester.run(new ArrayList<Integer>(), tests);
ListTester.run(new LinkedList<Integer>(), tests);
ListTester.run(new Vector<Integer>(), tests);
Tester.fieldWidth = 12;
Tester<LinkedList<Integer>> qTest =
new Tester<LinkedList<Integer>>(
new LinkedList<Integer>(), qTests);
qTest.setHeadline("Queue tests");
qTest.timedTest();
}
} /* Output: (Sample)
--- Array as List ---
size get set
10 130 183
100 130 164
1000 129 165
10000 129 165
--------------------- ArrayList ---------------------
size add get set iteradd insert remove
10 121 139 191 435 3952 446
100 72 141 191 247 3934 296
1000 98 141 194 839 2202 923
10000 122 144 190 6880 14042 7333
--------------------- LinkedList ---------------------
size add get set iteradd insert remove
10 182 164 198 658 366 262
100 106 202 230 457 108 201
1000 133 1289 1353 430 136 239
10000 172 13648 13187 435 255 239
----------------------- Vector -----------------------
size add get set iteradd insert remove
10 129 145 187 290 3635 253
100 72 144 190 263 3691 292
1000 99 145 193 846 2162 927
10000 108 145 186 6871 14730 7135
-------------------- Queue tests --------------------
size addFirst addLast rmFirst rmLast
10 199 163 251 253
100 98 92 180 179
1000 99 93 216 212
10000 111 109 262 384
*///:~
注：由於篇幅問題，程式碼中的Test、Tester、TestParam類見：Chapter17\Example9
- (1) 對於背後是陣列支撐的List和ArrayList，無論列表大小如何，這些存取都快速一致。而對於LinkedList存取時間對於較大的列表明顯增加，如果需要執行大量隨機存取，連結連結串列不會是一種好的選擇
- (2) 使用迭代器在列表中間插入新的元素。對於ArrayList，當列表變大時，其開銷將變得高昂，但是對於LinkedList，相對來說比較低廉，並且不隨列表尺寸而發生變化。這是因為ArrayList在插入時，必須建立空間並將它的所有參照向前移動，這會隨ArrayList的尺寸增加而產生高昂的代價。LinkedList自需要連結新的元素，而不必修改列表中剩餘的元素，一次你可以認為列表尺寸如果變化，其代價大致相同
- (3) LinkedList對List端點會進行特殊處理——這使得在將LinkedList用作Queue時，速度可以得到提高
- (4) 在LinkedList中的插入和移除代價相當低廉，並且不隨列表尺寸發生變化，但是對於ArrayList，插入操作代價很高昂，並且不隨列表尺寸的增加而增加
- (5) 從Queue測試中，可以看到LinkedList可以多麼快速的從列表的端點插入和移除元素，這正是對Queue行為所做的優化
- (6) 將ArrayList作為預設首選，只有你需要使用額外的功能，或者當程式的效能因為經常從表中間進行插入和刪除而變差的時候，才去選擇LinkedList。如果使用的是固定數量的元素，那麼既可以使用背後有支撐的List，也可以選擇真正的陣列
- (7) CopyOnWriteArrayList是List的一個特殊實現，專門用於並行程式設計
- 微基準測試的危險
- Math.random()的輸出中的，其範圍是[0,1)
- (1) HashSet的效能基本上總是比TreeSet的好，特別是在新增和查詢元素時，而這兩個操作是最重要的操作。TreeSet存在的唯一原因是它可以維持元素的排序狀態
- (2) 對於插入操作，LinkedHashSet比HashSet的代價更高，這是由維護連結串列所帶來額外開銷造成的
- (1) 所有的Map實現的插入操作都會隨著Map尺寸的變大明顯變慢。但是查詢的代價比插入小很多。
- (2) Hashtable的效能大體和HashMap相當。因為HashMap是用來替代Hashtable的，因此它們使用了相同的底層儲存和查詢機制
- (3) TreeMap
- i.TreeMap是一種建立有序列表的方式。樹的行為是：總是保證有序，並且不必進行特殊的排序。一旦你填充了一個TreeMap，就可以呼叫keySet()方法來獲取鍵的Set檢視，然後呼叫toArray()來產生這些鍵構成的陣列。
- ii.可以使用靜態方法Arrays.binarySearch()在排序陣列中快速查詢物件
- iii.只有你要求Map始終保持有序時，才需要使用TreeMap
- (4) LingkedHashMap在插入時比HashMap慢一點，因為它維護雜湊資料結構的同時還要維護連結串列。就是因為這個列表，使得其迭代速度更快
- (5) IdentityHashMap則具有完全不同的效能，因為它使用==而不是equals()來比較元素
- (6) HashMap的效能因子，可以通過手工調整HashMap來提高效能，從而滿足我們特定應用的需求：
- i.容量：表中的桶位數
- ii.初始容量：表在建立時所擁有的桶位數
- iii.尺寸：表中當前儲存的項數
- iv.負載因子：尺寸/容量。負載輕的表產生的可能性小，因此對於插入和查詢都是最理想的
- (7) HashMap使用的預設負載因子時0.75，這個因子在時間和空間代價之間達到了平衡。更高的負載因子可以降低表所需空間，但是會增加查詢代價
11.實用方法
- (1) List排序和查詢所使用的方法與物件陣列所使用的相應方法有相同的名字與語法，只是用Collections的static方法代替Arrays的方法而已
- (2) 如果使用Comparator進行排序，那麼binarySearch()必須使用相同的Comparator
- (1) Collections.unmodifiableCollection()用於建立「不可修改」的容器（返回值是容器的唯讀版本），任何修改容器內的操作（例如add()、put()）都會引起UnsupportedOperationException異常
- (2) 在將容器設為唯讀之前，必須填入有意義的資料。裝在資料後就不可修改了
- (1) 直接將新生成的容器傳遞給適當的同步方法
- Collections.synchronizedCollection(
new ArrayList()); - Collections.synchronizedList(
new ArrayList()); - Collections.synchronizedSet(
new HashSet()); - Collections.synchronizedSortedSet(
new TreeSet()); - Collections.synchronizedMap(
new HashMap<String,String>()) - Collections.synchronizedSortedMap(
new TreeMap<String,String>())
- Collections.synchronizedCollection(
- (2) 快速報錯
- Java容器有一種保護機制，能夠防止多個程序同時修改同一個容器的內容
- Java容器類類庫採用快速報錯機制，它會探查容器上的任何除了你程序所進行的操作以外的所有變化，一旦發現其他程序修改了容器，就會丟擲ConcurrentModificationException異常
- ConcurrentHashMap、CopyOnWriteArrayList和CopyOnWriteArrayList都使用了可以避免ConcurrentModificationException異常
12.持有參照
- java.lang.ref類庫包含了一組類，這些類為垃圾回收提供了更大的靈活性
- 有三個繼承自抽象類Reference的類：SoftReference、WeakReference和PhantomReference。當垃圾回收器正在考察的物件只能通過某個Reference物件才「可獲得」時，上述這些不同的派生類為垃圾回收器提供了不同級別的間接性指示
- 使用Renference物件，可以繼續使用該物件，而在記憶體消耗殆盡的時候由允許釋放該物件
- Soft reference：用以實現記憶體敏感的快取記憶體
- Weak reference：是為實現「規範對映」而設計的，它不妨礙垃圾回收對映的「鍵」（或「值」）
- Phantom reference：用以呼叫回收前的清理工作，它比Java終止機制更靈活
- WeakHashMap：容器類中有一種特殊的Map，即WeakHashMap，它被用來儲存WeakReference
13.Java 1.0/1.1 的容器
- Vector是唯一可以自我擴充套件的序列
- Enumeration只是介面而不是實現
- boolean hasMoreElement():如果此列舉包含更多元素，該方法就返回true
- Object nextElement():該方法返回此列舉中的下一個元素（如果該有下一個元素），否則丟擲異常
- Collection.emumeration()：從Collection生成一個Enumeration
- Hashtable
- 在新程式中，應使用HashMap
- Stack
- Stack繼承了Vector。它擁有Vector所有的特點和行為，在加上一些額外的Stack行為
- BitSet
- 如果想要高效率地儲存大量「開/關」資訊，BitSet是很好的選擇。不過它的效率僅是對空間而言；如果需要高效的存取時間，BitSet比本地陣列稍微慢一點