[TOC]
<!-- Appendix: Understanding equals() and hashCode() -->
# 附錄:理解equals和hashCode方法
假設有一個容器使用hash函數,當你創建一個放到這個容器時,你必須定義 **hashCode()** 函數和 **equals()** 函數。這兩個函數一起被用于hash容器中的查詢操作。
<!-- A Canonical equals() -->
## equals規范
當你創建一個類的時候,它自動繼承自 **Objcet** 類。如果你不覆寫 **equals()** ,你將會獲得 **Objcet** 對象的 **equals()** 函數。默認情況下,這個函數會比較對象的地址。所以只有你在比較同一個對象的時候,你才會獲得**true**。默認的情況是"區分度最高的"。
```java
// equalshashcode/DefaultComparison.java
class DefaultComparison {
private int i, j, k;
DefaultComparison(int i, int j, int k) {
this.i = i;
this.j = j;
this.k = k;
}
public static void main(String[] args) {
DefaultComparison
a = new DefaultComparison(1, 2, 3),
b = new DefaultComparison(1, 2, 3);
System.out.println(a == a);
System.out.println(a == b);
}
}
/*
Output:
true
false
*/
```
通常你會希望放寬這個限制。一般來說如果兩個對象有相同的類型和相同的字段,你會認為這兩個對象相等,但也會有一些你不想加入 **equals()** 函數中來比較的字段。這是類型設計的一部分。
一個合適的 **equals()**函數必須滿足以下五點條件:
1. 反身性:對于任何 **x**, **x.equals(x)** 應該返回 **true**。
2. 對稱性:對于任何 **x** 和 **y**, **x.equals(y)** 應該返回 **true**當且僅當 **y.equals(x)** 返回 **true** 。
3. 傳遞性:對于任何**x**,**y**,還有**z**,如果 **x.equals(y)** 返回 **true** 并且 **y.equals(z)** 返回 **true**,那么 **x.equals(z)** 應該返回 **true**。
4. 一致性:對于任何 **x**和**y**,在對象沒有被改變的情況下,多次調用 **x.equals(y)** 應該總是返回 **true** 或者**false**。
5. 對于任何非**null**的**x**,**x.equals(null)**應該返回**false**。
下面是滿足這些條件的測試,并且判斷對象是否和自己相等(我們這里稱呼其為**右值**):
1. 如果**右值**是**null**,那么不相等。
2. 如果**右值**是**this**,那么兩個對象相等。
3. 如果**右值**不是同一個類型或者子類,那么兩個對象不相等。
4. 如果所有上面的檢查通過了,那么你必須決定 **右值** 中的哪些字段是重要的,然后比較這些字段。
Java 7 引入了 **Objects** 類型來幫助這個流程,這樣我們能夠寫出更好的 **equals()** 函數。
下面的例子比較了不同類型的 **Equality**類。為了避免重復的代碼,我們使用*工廠函數設計模*式來實現樣例。 **EqualityFactory**接口提供**make()**函數來生成一個**Equaity**對象,這樣不同的**EqualityFactory**能夠生成**Equality**不同的子類。
```java
// equalshashcode/EqualityFactory.java
import java.util.*;
interface EqualityFactory {
Equality make(int i, String s, double d);
}
```
現在我們來定義 **Equality**,它包含三個字段(所有的字段我們認為在比較中都很重要)和一個 **equals()** 函數用來滿足上述的四種檢查。構造函數展示了它的類名來保證我們在執行我們想要的測試:
```java
// equalshashcode/Equality.java
import java.util.*;
public class Equality {
protected int i;
protected String s;
protected double d;public Equality(int i, String s, double d) {
this.i = i;
this.s = s;
this.d = d;
System.out.println("made 'Equality'");
}
@Override
public boolean equals(Object rval) {
if(rval == null)
return false;
if(rval == this)
return true;
if(!(rval instanceof Equality))
return false;
Equality other = (Equality)rval;
if(!Objects.equals(i, other.i))
return false;
if(!Objects.equals(s, other.s))
return false;
if(!Objects.equals(d, other.d))return false;
return true;
}
public void test(String descr, String expected, Object rval) {
System.out.format("-- Testing %s --%n" + "%s instanceof Equality: %s%n" +
"Expected %s, got %s%n",
descr, descr, rval instanceof Equality,
expected, equals(rval));
}
public static void testAll(EqualityFactory eqf) {
Equality
e = eqf.make(1, "Monty", 3.14),
eq = eqf.make(1, "Monty", 3.14),
neq = eqf.make(99, "Bob", 1.618);
e.test("null", "false", null);
e.test("same object", "true", e);
e.test("different type",
"false", Integer.valueOf(99));e.test("same values", "true", eq);
e.test("different values", "false", neq);
}
public static void main(String[] args) {
testAll( (i, s, d) -> new Equality(i, s, d));
}
}
/*
Output:
made 'Equality'
made 'Equality'
made 'Equality'
-- Testing null --
null instanceof Equality: false
Expected false, got false
-- Testing same object --
same object instanceof Equality: true
Expected true, got true
-- Testing different type --
different type instanceof Equality: false
Expected false, got false-- Testing same values --
same values instanceof Equality: true
Expected true, got true
-- Testing different values --
different values instanceof Equality: true
Expected false, got false
*/
```
**testAll()** 執行了我們期望的所有不同類型對象的比較。它使用工廠創建了**Equality**對象。
在 **main()** 里,請注意對 **testAll()** 的調用很簡單。因為**EqualityFactory**有著單一的函數,它能夠和lambda表達式一起使用來表示**make()**函數。
上述的 **equals()** 函數非常繁瑣,并且我們能夠將其簡化成規范的形式,請注意:
1. **instanceof**檢查減少了**null**檢查的需要。
2. 和**this**的比較是多余的。一個正確書寫的 **equals()** 函數能正確地和自己比較。
因為 **&&** 是一個短路比較,它會在第一次遇到失敗的時候退出并返回**false**。所以,通過使用 **&&** 將檢查鏈接起來,我們可以寫出更精簡的 **equals()** 函數:
```java
// equalshashcode/SuccinctEquality.java
import java.util.*;
public class SuccinctEquality extends Equality {
public SuccinctEquality(int i, String s, double d) {
super(i, s, d);
System.out.println("made 'SuccinctEquality'");
}
@Override
public boolean equals(Object rval) {
return rval instanceof SuccinctEquality &&
Objects.equals(i, ((SuccinctEquality)rval).i) &&
Objects.equals(s, ((SuccinctEquality)rval).s) &&
Objects.equals(d, ((SuccinctEquality)rval).d);
}
public static void main(String[] args) {
Equality.testAll( (i, s, d) ->
new SuccinctEquality(i, s, d));
}
}
/* Output:
made 'Equality'
made 'SuccinctEquality'
made 'Equality'
made 'SuccinctEquality'
made 'Equality'
made 'SuccinctEquality'
-- Testing null --
null instanceof Equality: false
Expected false, got false
-- Testing same object --
same object instanceof Equality: true
Expected true, got true
-- Testing different type --
different type instanceof Equality: false
Expected false, got false
-- Testing same values --
same values instanceof Equality: true
Expected true, got true
-- Testing different values --different values instanceof Equality: true
Expected false, got false
*/
```
對于每個 **SuccinctEquality**,基類構造函數在派生類構造函數前被調用,輸出顯示我們依然獲得了正確的結果,你可以發現短路返回已經發生了,不然的話,**null**測試和“不同類型”的測試會在 **equals()** 函數下面的比較中強制轉化的時候拋出異常。
**Objects.equals()** 會在你組合其他類型的時候發揮很大的作用。
```java
// equalshashcode/ComposedEquality.java
import java.util.*;
class Part {
String ss;
double dd;
Part(String ss, double dd) {
this.ss = ss;
this.dd = dd;
}
@Override
public boolean equals(Object rval) {
return rval instanceof Part &&
Objects.equals(ss, ((Part)rval).ss) &&
Objects.equals(dd, ((Part)rval).dd);
}
}
public class ComposedEquality extends SuccinctEquality {
Part part;
public ComposedEquality(int i, String s, double d) {
super(i, s, d);
part = new Part(s, d);
System.out.println("made 'ComposedEquality'");
}
@Override
public boolean equals(Object rval) {
return rval instanceof ComposedEquality &&
super.equals(rval) &&
Objects.equals(part,
((ComposedEquality)rval).part);
}
public static void main(String[] args) {
Equality.testAll( (i, s, d) ->
new ComposedEquality(i, s, d));
}
}
/*
Output:
made 'Equality'
made 'SuccinctEquality'
made 'ComposedEquality'
made 'Equality'
made 'SuccinctEquality'
made 'ComposedEquality'
made 'Equality'
made 'SuccinctEquality'
made 'ComposedEquality'
-- Testing null --null instanceof Equality: false
Expected false, got false
-- Testing same object --
same object instanceof Equality: true
Expected true, got true
-- Testing different type --
different type instanceof Equality: false
Expected false, got false
-- Testing same values --
same values instanceof Equality: true
Expected true, got true
-- Testing different values --
different values instanceof Equality: true
Expected false, got false
*/
```
注意super.equals()這個調用,沒有必要重新發明它(因為你不總是有權限訪問基類所有的必要字段)
<!--Equality Across Subtypes -->
### 不同子類的相等性
繼承意味著兩個不同子類的對象當其向上轉型的時候可以是相等的。假設你有一個Animal對象的集合。這個集合天然接受**Animal**的子類。在這個例子中是**Dog**和**Pig**。每個**Animal**有一個**name**和**size**,還有唯一的內部**id**數字。
我們通過**Objects**類,以規范的形式定義 **equals()**函數和**hashCode()**。但是我們只能在基類**Animal**中定義他們。并且我們在這兩個函數中沒有包含**id**字段。從**equals()**函數的角度看待,這意味著我們只關心它是否是**Animal**,而不關心是否是**Animal**的某個子類。
```java
// equalshashcode/SubtypeEquality.java
import java.util.*;
enum Size { SMALL, MEDIUM, LARGE }
class Animal {
private static int counter = 0;
private final int id = counter++;
private final String name;
private final Size size;
Animal(String name, Size size) {
this.name = name;
this.size = size;
}
@Override
public boolean equals(Object rval) {
return rval instanceof Animal &&
// Objects.equals(id, ((Animal)rval).id) && // [1]
Objects.equals(name, ((Animal)rval).name) &&
Objects.equals(size, ((Animal)rval).size);
}
@Override
public int hashCode() {
return Objects.hash(name, size);
// return Objects.hash(name, size, id); // [2]
}
@Override
public String toString() {
return String.format("%s[%d]: %s %s %x",
getClass().getSimpleName(), id,
name, size, hashCode());
}
}
class Dog extends Animal {
Dog(String name, Size size) {
super(name, size);
}
}
class Pig extends Animal {
Pig(String name, Size size) {
super(name, size);
}
}
public class SubtypeEquality {
public static void main(String[] args) {
Set<Animal> pets = new HashSet<>();
pets.add(new Dog("Ralph", Size.MEDIUM));
pets.add(new Pig("Ralph", Size.MEDIUM));
pets.forEach(System.out::println);
}
}
/*
Output:
Dog[0]: Ralph MEDIUM a752aeee
*/
```
如果我們只考慮類型的話,某些情況下它的確說得通——只從基類的角度看待問題,這是李氏替換原則的基石。這個代碼完美符合替換理論因為派生類沒有添加任何額外不再基類中的額外函數。派生類只是在表現上不同,而不是在接口上。(當然這不是常態)
但是當我們提供了兩個有著相同數據的不同的對象類型,然后將他們放置在 **HashSet<Animal>** 中。只有他們中的一個能存活。這強調了 **equals()** 不是完美的數學理論,而只是機械般的理論。
**hashCode()** 和 **equals()** 必須能夠允許類型在hash數據結構中正常工作。例子中 **Dog** 和 **Pig** 會被映射到同 **HashSet** 的同一個桶中。這個時候,**HashSet** 回退到 **equals()** 來區分對象,但是 **equals()** 也認為兩個對象是相同的。**HashSet**因為已經有一個相同的對象了,所以沒有添加 **Pig**。
我們依然能夠通過使得其他字段對象不同來讓例子能夠正常工作。在這里每個 **Animal** 已經有了一個獨一無二的 **id** ,所以你能夠取消 **equals()** 函數中的 **[1]** 行注釋,或者取消 **hashCode()** 函數中的 **[2]** 行注釋。按照規范,你應該同時完成這兩個操作,如此能夠將所有“不變的”字段包含在兩個操作中(“不變”所以 **equals()** 和 **hashCode()** 在哈希數據結構中的排序和取值時,不會生成不同的值。我將“不變的”放在引號中因為你必須計算出是否已經發生變化)。
> **旁注**: 在**hashCode()**中,如果你只能夠使用一個字段,使用**Objcets.hashCode()**。如果你使用多個字段,那么使用 **Objects.hash()**。
我們也可以通過標準方式,將 **equals()** 定義在子類中(不包含 **id** )解決這個問題:
```java
// equalshashcode/SubtypeEquality2.java
import java.util.*;
class Dog2 extends Animal {
Dog2(String name, Size size) {
super(name, size);
}
@Override
public boolean equals(Object rval) {
return rval instanceof Dog2 &&super.equals(rval);
}
}
class Pig2 extends Animal {
Pig2(String name, Size size) {
super(name, size);
}
@Override
public boolean equals(Object rval) {
return rval instanceof Pig2 &&
super.equals(rval);
}
}
public class SubtypeEquality2 {
public static void main(String[] args) {
Set<Animal> pets = new HashSet<>();
pets.add(new Dog2("Ralph", Size.MEDIUM));
pets.add(new Pig2("Ralph", Size.MEDIUM));
pets.forEach(System.out::println);
}
}
/*
Output:
Dog2[0]: Ralph MEDIUM a752aeee
Pig2[1]: Ralph MEDIUM a752aeee
*/
```
注意 **hashCode()** 是獨一無二的,但是因為對象不再 **equals()** ,所以兩個函數都出現在**HashSet**中。另外,**super.equals()** 意味著我們不需要訪問基類的**private**字段。
一種說法是Java從**equals()** 和**hashCode()** 的定義中分離了可替代性。我們仍然能夠將**Dog**和**Pig**放置在 **Set\<Animal\>** 中,無論 **equals()** 和 **hashCode()** 是如何定義的,但是對象不會在哈希數據結構中正常工作,除非這些函數能夠被合理定義。不幸的是,**equals()** 不總是和 **hashCode()** 一起使用,這在你嘗試為了某個特殊類型避免定義它的時候會讓問題復雜化。并且這也是為什么遵循規范是有價值的。然而這會變得更加復雜,因為你不總是需要定義其中一個函數。
<!-- Hashing and Hash Codes -->
## 哈希和哈希碼
在 [集合]() 章節中,我們使用預先定義的類作為 HashMap 的鍵。這些示例之所以有用,是因為預定義的類具有所有必需的連線,以使它們正確地充當鍵。
當創建自己的類作為HashMap的鍵時,會發生一個常見的陷阱,從而忘記進行必要的接線。例如,考慮一個將Earthhog 對象與 Prediction 對象匹配的天氣預報系統。這似乎很簡單:使用Groundhog作為鍵,使用Prediction作為值:
```java
// equalshashcode/Groundhog.java
// Looks plausible, but doesn't work as a HashMap key
public class Groundhog {
protected int number;
public Groundhog(int n) { number = n; }
@Override
public String toString() {
return "Groundhog #" + number;
}
}
```
```java
// equalshashcode/Prediction.java
// Predicting the weather
import java.util.*;
public class Prediction {
private static Random rand = new Random(47);
@Override
public String toString() {
return rand.nextBoolean() ?
"Six more weeks of Winter!" : "Early Spring!";
}
}
```
```java
// equalshashcode/SpringDetector.java
// What will the weather be?
import java.util.*;
import java.util.stream.*;
import java.util.function.*;
import java.lang.reflect.*;
public class SpringDetector {
public static <T extends Groundhog>
void detectSpring(Class<T> type) {
try {
Constructor<T> ghog =
type.getConstructor(int.class);
Map<Groundhog, Prediction> map =
IntStream.range(0, 10)
.mapToObj(i -> {
try {
return ghog.newInstance(i);
} catch(Exception e) {
throw new RuntimeException(e);
}
})
.collect(Collectors.toMap(
Function.identity(),
gh -> new Prediction()));
map.forEach((k, v) ->
System.out.println(k + ": " + v));
Groundhog gh = ghog.newInstance(3);
System.out.println(
"Looking up prediction for " + gh);
if(map.containsKey(gh))
System.out.println(map.get(gh));
else
System.out.println("Key not found: " + gh);
} catch(NoSuchMethodException |
IllegalAccessException |
InvocationTargetException |
InstantiationException e) {
throw new RuntimeException(e);
}
}
public static void main(String[] args) {
detectSpring(Groundhog.class);
}
}
/* Output:
Groundhog #3: Six more weeks of Winter!
Groundhog #0: Early Spring!
Groundhog #8: Six more weeks of Winter!
Groundhog #6: Early Spring!
Groundhog #4: Early Spring!
Groundhog #2: Six more weeks of Winter!
Groundhog #1: Early Spring!
Groundhog #9: Early Spring!
Groundhog #5: Six more weeks of Winter!
Groundhog #7: Six more weeks of Winter!
Looking up prediction for Groundhog #3
Key not found: Groundhog #3
*/
```
每個 Groundhog 都被賦予了一個常數,因此你可以通過如下的方式在 HashMap 中尋找對應的 Prediction。“給我一個和 Groundhog#3 相關聯的 Prediction”。而 Prediction 通過一個隨機生成的 boolean 來選擇天氣。`detectSpring()` 方法通過反射來實例化 Groundhog 類,或者它的子類。稍后,當我們繼承一種新型的“Groundhog ”以解決此處演示的問題時,這將派上用場。
這里的 HashMap 被 Groundhog 和其相關聯的 Prediction 充滿。并且上面展示了 HashMap 里面填充的內容。接下來我們使用填充了常數 3 的 Groundhog 作為 key 用于尋找對應的 Prediction 。(這個鍵值對肯定在 Map 中)。
這看起來十分簡單,但是這樣做并沒有奏效 —— 它無法找到數字3這個鍵。問題出在Groundhog自動地繼承自基類Object,所以這里使用Object的hashCode0方法生成散列碼,而它默認是使用對象的地址計算散列碼。因此,由Groundhog(3)生成的第一個實例的散列碼與由Groundhog(3)生成的第二個實例的散列碼是不同的,而我們正是使用后者進行查找的。
我們需要恰當的重寫hashCode()方法。但是它仍然無法正常運行,除非你同時重寫 equals()方法,它也是Object的一部分。HashMap使用equals()判斷當前的鍵是否與表中存在的鍵相同。
這是因為默認的Object.equals()只是比較對象的地址,所以一個Groundhog(3)并不等于另一個Groundhog(3),因此,如果要使用自己的類作為HashMap的鍵,必須同時重載hashCode()和equals(),如下所示:
```java
// equalshashcode/Groundhog2.java
// A class that's used as a key in a HashMap
// must override hashCode() and equals()
import java.util.*;
public class Groundhog2 extends Groundhog {
public Groundhog2(int n) { super(n); }
@Override
public int hashCode() { return number; }
@Override
public boolean equals(Object o) {
return o instanceof Groundhog2 &&
Objects.equals(
number, ((Groundhog2)o).number);
}
}
```
```java
// equalshashcode/SpringDetector2.java
// A working key
public class SpringDetector2 {
public static void main(String[] args) {
SpringDetector.detectSpring(Groundhog2.class);
}
}
/* Output:
Groundhog #0: Six more weeks of Winter!
Groundhog #1: Early Spring!
Groundhog #2: Six more weeks of Winter!
Groundhog #3: Early Spring!
Groundhog #4: Early Spring!
Groundhog #5: Six more weeks of Winter!
Groundhog #6: Early Spring!
Groundhog #7: Early Spring!
Groundhog #8: Six more weeks of Winter!
Groundhog #9: Six more weeks of Winter!
Looking up prediction for Groundhog #3
Early Spring!
*/
```
Groundhog2.hashCode0返回Groundhog的標識數字(編號)作為散列碼。在此例中,程序員負責確保不同的Groundhog具有不同的編號。hashCode()并不需要總是能夠返回唯一的標識碼(稍后你會理解其原因),但是equals() 方法必須嚴格地判斷兩個對象是否相同。此處的equals()是判斷Groundhog的號碼,所以作為HashMap中的鍵,如果兩個Groundhog2對象具有相同的Groundhog編號,程序就出錯了。
如何定義 equals() 方法在上一節 [equals 規范]()中提到了。輸出表明我們現在的輸出是正確的。
### 理解 hashCode
前面的例子只是正確解決問題的第一步。它只說明,如果不為你的鍵覆蓋hashCode() 和equals() ,那么使用散列的數據結構(HashSet,HashMap,LinkedHashst或LinkedHashMap)就無法正確處理你的鍵。然而,要很好地解決此問題,你必須了解這些數據結構的內部構造。
首先,使用散列的目的在于:想要使用一個對象來查找另一個對象。不過使用TreeMap或者你自己實現的Map也可以達到此目的。與散列實現相反,下面的示例用一對ArrayLists實現了一個Map,與AssociativeArray.java不同,這其中包含了Map接口的完整實現,因此提供了entrySet()方法:
```java
// equalshashcode/SlowMap.java
// A Map implemented with ArrayLists
import java.util.*;
import onjava.*;
public class SlowMap<K, V> extends AbstractMap<K, V> {
private List<K> keys = new ArrayList<>();
private List<V> values = new ArrayList<>();
@Override
public V put(K key, V value) {
V oldValue = get(key); // The old value or null
if(!keys.contains(key)) {
keys.add(key);
values.add(value);
} else
values.set(keys.indexOf(key), value);
return oldValue;
}
@Override
public V get(Object key) { // key: type Object, not K
if(!keys.contains(key))
return null;
return values.get(keys.indexOf(key));
}
@Override
public Set<Map.Entry<K, V>> entrySet() {
Set<Map.Entry<K, V>> set= new HashSet<>();
Iterator<K> ki = keys.iterator();
Iterator<V> vi = values.iterator();
while(ki.hasNext())
set.add(new MapEntry<>(ki.next(), vi.next()));
return set;
}
public static void main(String[] args) {
SlowMap<String,String> m= new SlowMap<>();
m.putAll(Countries.capitals(8));
m.forEach((k, v) ->
System.out.println(k + "=" + v));
System.out.println(m.get("BENIN"));
m.entrySet().forEach(System.out::println);
}
}
/* Output:
CAMEROON=Yaounde
ANGOLA=Luanda
BURKINA FASO=Ouagadougou
BURUNDI=Bujumbura
ALGERIA=Algiers
BENIN=Porto-Novo
CAPE VERDE=Praia
BOTSWANA=Gaberone
Porto-Novo
CAMEROON=Yaounde
ANGOLA=Luanda
BURKINA FASO=Ouagadougou
BURUNDI=Bujumbura
ALGERIA=Algiers
BENIN=Porto-Novo
CAPE VERDE=Praia
BOTSWANA=Gaberone
*/
```
put()方法只是將鍵與值放入相應的ArrayList。為了與Map接口保持一致,它必須返回舊的鍵,或者在沒有任何舊鍵的情況下返回null。
同樣遵循了Map規范,get()會在鍵不在SlowMap中的時候產生null。如果鍵存在,它將被用來查找表示它在keys列表中的位置的數值型索引,并且這個數字被用作索引來產生與values列表相關聯的值。注意,在get()中key的類型是Object,而不是你所期望的參數化類型K(并且是在AssociativeArrayjava中真正使用的類型),這是將泛型注入到Java語言中的時刻如此之晚所導致的結果-如果泛型是Java語言最初就具備的屬性,那么get()就可以執行其參數的類型。
Map.entrySet() 方法必須產生一個Map.Entry對象集。但是,Map.Entry是一個接口,用來描述依賴于實現的結構,因此如果你想要創建自己的Map類型,就必須同時定義Map.Entry的實現:
```java
// equalshashcode/MapEntry.java
// A simple Map.Entry for sample Map implementations
import java.util.*;
public class MapEntry<K, V> implements Map.Entry<K, V> {
private K key;
private V value;
public MapEntry(K key, V value) {
this.key = key;
this.value = value;
}
@Override
public K getKey() { return key; }
@Override
public V getValue() { return value; }
@Override
public V setValue(V v) {
V result = value;
value = v;
return result;
}
@Override
public int hashCode() {
return Objects.hash(key, value);
}
@SuppressWarnings("unchecked")
@Override
public boolean equals(Object rval) {
return rval instanceof MapEntry &&
Objects.equals(key,
((MapEntry<K, V>)rval).getKey()) &&
Objects.equals(value,
((MapEntry<K, V>)rval).getValue());
}
@Override
public String toString() {
return key + "=" + value;
}
}
```
這里 equals 方法的實現遵循了[equals 規范]()。在 Objects 類中有一個非常熟悉的方法可以幫助創建 hashCode() 方法: Objects.hash()。當你定義含有超過一個屬性的對象的 `hashCode()` 時,你可以使用這個方法。如果你的對象只有一個屬性,可以直接使用 ` Objects.hashCode()`。
盡管這個解決方案非常簡單,并且看起來在SlowMap.main() 的瑣碎測試中可以正常工作,但是這并不是一個恰當的實現,因為它創建了鍵和值的副本。entrySet() 的恰當實現應該在Map中提供視圖,而不是副本,并且這個視圖允許對原始映射表進行修改(副本就不行)。
### 為了速度而散列
SlowMap.java 說明了創建一種新的Map并不困難。但是正如它的名稱SlowMap所示,它不會很快,所以如果有更好的選擇,就應該放棄它。它的問題在于對鍵的查詢,鍵沒有按照任何特定順序保存,所以只能使用簡單的線性查詢,而線性查詢是最慢的查詢方式。
散列的價值在于速度:散列使得查詢得以快速進行。由于瓶頸位于鍵的查詢速度,因此解決方案之一就是保持鍵的排序狀態,然后使用Collections.binarySearch()進行查詢。
散列則更進一步,它將鍵保存在某處,以便能夠很快找到。存儲一組元素最快的數據結構是數組,所以使用它來表示鍵的信息(請小心留意,我是說鍵的信息,而不是鍵本身)。但是因為數組不能調整容量,因此就有一個問題:我們希望在Map中保存數量不確定的值,但是如果鍵的數量被數組的容量限制了,該怎么辦呢?
答案就是:數組并不保存鍵本身。而是通過鍵對象生成一個數字,將其作為數組的下標。這個數字就是散列碼,由定義在Object中的、且可能由你的類覆蓋的hashCode()方法(在計算機科學的術語中稱為散列函數)生成。
于是查詢一個值的過程首先就是計算散列碼,然后使用散列碼查詢數組。如果能夠保證沒有沖突(如果值的數量是固定的,那么就有可能),那可就有了一個完美的散列函數,但是這種情況只是特例。。通常,沖突由外部鏈接處理:數組并不直接保存值,而是保存值的 list。然后對 list中的值使用equals()方法進行線性的查詢。這部分的查詢自然會比較慢,但是,如果散列函數好的話,數組的每個位置就只有較少的值。因此,不是查詢整個list,而是快速地跳到數組的某個位置,只對很少的元素進行比較。這便是HashMap會如此快的原因。
理解了散列的原理,我們就能夠實現一個簡單的散列Map了:
```java
// equalshashcode/SimpleHashMap.java
// A demonstration hashed Map
import java.util.*;
import onjava.*;
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];
@Override
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<>();
LinkedList<MapEntry<K, V>> bucket = buckets[index];
MapEntry<K, V> pair = new MapEntry<>(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;
}
@Override
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;
}
@Override
public Set<Map.Entry<K, V>> entrySet() {
Set<Map.Entry<K, V>> set= new HashSet<>();
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<>();
m.putAll(Countries.capitals(8));
m.forEach((k, v) ->
System.out.println(k + "=" + v));
System.out.println(m.get("BENIN"));
m.entrySet().forEach(System.out::println);
}
}
/* Output:
CAMEROON=Yaounde
ANGOLA=Luanda
BURKINA FASO=Ouagadougou
BURUNDI=Bujumbura
ALGERIA=Algiers
BENIN=Porto-Novo
CAPE VERDE=Praia
BOTSWANA=Gaberone
Porto-Novo
CAMEROON=Yaounde
ANGOLA=Luanda
BURKINA FASO=Ouagadougou
BURUNDI=Bujumbura
ALGERIA=Algiers
BENIN=Porto-Novo
CAPE VERDE=Praia
BOTSWANA=Gaberone
*/
```
由于散列表中的“槽位”(slot)通常稱為桶位(bucket),因此我們將表示實際散列表的數組命名為bucket,為使散列分布均勻,桶的數量通常使用質數[^2]。注意,為了能夠自動處理沖突,使用了一個LinkedList的數組;每一個新的元素只是直接添加到list尾的某個特定桶位中。即使Java不允許你創建泛型數組,那你也可以創建指向這種數組的引用。這里,向上轉型為這種數組是很方便的,這樣可以防止在后面的代碼中進行額外的轉型。
對于put() 方法,hashCode() 將針對鍵而被調用,并且其結果被強制轉換為正數。為了使產生的數字適合bucket數組的大小,取模操作符將按照該數組的尺寸取模。如果數組的某個位置是 null,這表示還沒有元素被散列至此,所以,為了保存剛散列到該定位的對象,需要創建一個新的LinkedList。一般的過程是,查看當前位置的ist中是否有相同的元素,如果有,則將舊的值賦給oldValue,然后用新的值取代舊的值。標記found用來跟蹤是否找到(相同的)舊的鍵值對,如果沒有,則將新的對添加到list的末尾。
get()方法按照與put()方法相同的方式計算在buckets數組中的索引(這很重要,因為這樣可以保證兩個方法可以計算出相同的位置)如果此位置有LinkedList存在,就對其進行查詢。
注意,這個實現并不意味著對性能進行了調優,它只是想要展示散列映射表執行的各種操作。如果你瀏覽一下java.util.HashMap的源代碼,你就會看到一個調過優的實現。同樣,為了簡單,SimpleHashMap使用了與SlowMap相同的方式來實現entrySet(),這個方法有些過于簡單,不能用于通用的Map。
### 重寫 hashCode()
在明白了如何散列之后,編寫自己的hashCode()就更有意義了。
首先,你無法控制bucket數組的下標值的產生。這個值依賴于具體的HashMap對象的容量,而容量的改變與容器的充滿程度和負載因子(本章稍后會介紹這個術語)有關。hashCode()生成的結果,經過處理后成為桶位的下標(在SimpleHashMap中,只是對其取模,模數為bucket數組的大小)。
設計hashCode()時最重要的因素就是:無論何時,對同一個對象調用hashCode()都應該生成同樣的值。如果在將一個對象用put()添加進HashMap時產生一個hashCode()值,而用get()取出時卻產生了另一個hashCode()值,那么就無法重新取得該對象了。所以,如果你的hashCode()方法依賴于對象中易變的數據,用戶就要當心了,因為此數據發生變化時,hashCode()就會生成一個不同的散列碼,相當于產生了一個不同的鍵。
此外,也不應該使hashCode()依賴于具有唯一性的對象信息,尤其是使用this值,這只能產生很糟糕的hashCode(),因為這樣做無法生成一個新的鍵,使之與put()中原始的鍵值對中的鍵相同。這正是SpringDetector.java的問題所在,因為它默認的hashCode0使用的是對象的地址。所以,應該使用對象內有意義的識別信息。
下面以String類為例。String有個特點:如果程序中有多個String對象,都包含相同的字符串序列,那么這些String對象都映射到同一塊內存區域。所以new String("hello")生成的兩個實例,雖然是相互獨立的,但是對它們使用hashCode()應該生成同樣的結果。通過下面的程序可以看到這種情況:
```java
// equalshashcode/StringHashCode.java
public class StringHashCode {
public static void main(String[] args) {
String[] hellos = "Hello Hello".split(" ");
System.out.println(hellos[0].hashCode());
System.out.println(hellos[1].hashCode());
}
}
/* Output:
69609650
69609650
*/
```
對于String而言,hashCode() 明顯是基于String的內容的。
因此,要想使hashCode() 實用,它必須速度快,并且必須有意義。也就是說,它必須基于對象的內容生成散列碼。記得嗎,散列碼不必是獨一無二的(應該更關注生成速度,而不是唯一性),但是通過 hashCode() 和 equals() ,必須能夠完全確定對象的身份。
因為在生成桶的下標前,hashCode()還需要做進一步的處理,所以散列碼的生成范圍并不重要,只要是int即可。
還有另一個影響因素:好的hashCode() 應該產生分布均勻的散列碼。如果散列碼都集中在一塊,那么HashMap或者HashSet在某些區域的負載會很重,這樣就不如分布均勻的散列函數快。
在Effective Java Programming Language Guide(Addison-Wesley 2001)這本書中,Joshua Bloch為怎樣寫出一份像樣的hashCode()給出了基本的指導:
1. 給int變量result賦予某個非零值常量,例如17。
2. 為對象內每個有意義的字段(即每個可以做equals)操作的字段計算出一個int散列碼c:
| 字段類型 | 計算公式 |
| ------------------------------------------------------ | ------------------------------------------------------------ |
| boolean | c = (f ? 0 : 1) |
| byte , char , short , or int | c = (int)f |
| long | c = (int)(f ^ (f>>>32)) |
| float | c = Float.floatToIntBits(f); |
| double | long l =Double.doubleToLongBits(f); <br>c = (int)(l ^ (l >>> 32)) |
| Object , where equals() calls equals() for this field | c = f.hashCode() |
| Array | 應用以上規則到每一個元素中 |
3. 合并計算得到的散列碼: **result = 37 * result + c;?**
4. 返回 result。
5. 檢查hashCode()最后生成的結果,確保相同的對象有相同的散列碼。
下面便是遵循這些指導的一個例子。提示,你沒有必要書寫像如下的代碼 —— 相反,使用 `Objects.hash()` 去用于散列多字段的對象(如同在本例中的那樣),然后使用 `Objects.hashCode()` 如散列單字段的對象。
```java
// equalshashcode/CountedString.java
// Creating a good hashCode()
import java.util.*;
public class CountedString {
private static List<String> created =
new ArrayList<>();
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 used by CountedString:
for(String s2 : created)
if(s2.equals(s))
id++;
}
@Override
public String toString() {
return "String: " + s + " id: " + id +
" hashCode(): " + hashCode();
}
@Override
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;
}
@Override
public boolean equals(Object o) {
return o instanceof CountedString &&
Objects.equals(s, ((CountedString)o).s) &&
Objects.equals(id, ((CountedString)o).id);
}
public static void main(String[] args) {
Map<CountedString,Integer> map = new HashMap<>();
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 to Integer
}
System.out.println(map);
for(CountedString cstring : cs) {
System.out.println("Looking up " + cstring);
System.out.println(map.get(cstring));
}
}
}
/* Output:
{String: hi id: 4 hashCode(): 146450=3, String: hi id:
5 hashCode(): 146451=4, String: hi id: 2 hashCode():
146448=1, String: hi id: 3 hashCode(): 146449=2,
String: hi id: 1 hashCode(): 146447=0}
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
*/
```
CountedString由一個String和一個id組成,此id代表包含相同String的CountedString對象的編號。所有的String都被存儲在static ArrayList中,在構造器中通過選代遍歷此ArrayList完成對id的計算。
hashCode()和equals() 都基于CountedString的這兩個字段來生成結果;如果它們只基于String或者只基于id,不同的對象就可能產生相同的值。
在main)中,使用相同的String創建了多個CountedString對象。這說明,雖然String相同,但是由于id不同,所以使得它們的散列碼并不相同。在程序中,HashMap被打印了出來,因此可以看到它內部是如何存儲元素的(以無法辨別的次序),然后單獨查詢每一個鍵,以此證明查詢機制工作正常。
作為第二個示例,請考慮Individual類,它被用作[類型信息]()中所定義的typeinfo.pet類庫的基類。Individual類在那一章中就用到了,而它的定義則放到了本章,因此你可以正確地理解其實現。
在這里替換了手工去計算 `hashCode()`,我們使用了更合適的方式 ` Objects.hash() `:
```java
// typeinfo/pets/Individual.java
package typeinfo.pets;
import java.util.*;
public class
Individual implements Comparable<Individual> {
private static long counter = 0;
private final long id = counter++;
private String name;
public Individual(String name) { this.name = name; }
// 'name' is optional:
public Individual() {}
@Override
public String toString() {
return getClass().getSimpleName() +
(name == null ? "" : " " + name);
}
public long id() { return id; }
@Override
public boolean equals(Object o) {
return o instanceof Individual &&
Objects.equals(id, ((Individual)o).id);
}
@Override
public int hashCode() {
return Objects.hash(name, id);
}
@Override
public int compareTo(Individual arg) {
// Compare by class name first:
String first = getClass().getSimpleName();
String argFirst = arg.getClass().getSimpleName();
int firstCompare = first.compareTo(argFirst);
if(firstCompare != 0)
return firstCompare;
if(name != null && arg.name != null) {
int secondCompare = name.compareTo(arg.name);
if(secondCompare != 0)
return secondCompare;
}
return (arg.id < id ? -1 : (arg.id == id ? 0 : 1));
}
}
```
compareTo() 方法有一個比較結構,因此它會產生一個排序序列,排序的規則首先按照實際類型排序,然后如果有名字的話,按照name排序,最后按照創建的順序排序。下面的示例說明了它是如何工作的:
```java
// equalshashcode/IndividualTest.java
import collections.MapOfList;
import typeinfo.pets.*;
import java.util.*;
public class IndividualTest {
public static void main(String[] args) {
Set<Individual> pets = new TreeSet<>();
for(List<? extends Pet> lp :
MapOfList.petPeople.values())
for(Pet p : lp)
pets.add(p);
pets.forEach(System.out::println);
}
}
/* Output:
Cat Elsie May
Cat Pinkola
Cat Shackleton
Cat Stanford
Cymric Molly
Dog Margrett
Mutt Spot
Pug Louie aka Louis Snorkelstein Dupree
Rat Fizzy
Rat Freckly
Rat Fuzzy
*/
```
由于所有的寵物都有名字,因此它們首先按照類型排序,然后在同類型中按照名字排序。
<!-- Tuning a HashMap -->
## 調優 HashMap
我們有可能手動調優HashMap以提高其在特定應用程序中的性能。為了理解調整HashMap時的性能問題,一些術語是必要的:
- 容量(Capacity):表中存儲的桶數量。
- 初始容量(Initial Capacity):當表被創建時,桶的初始個數。 HashMap 和 HashSet 有可以讓你指定初始容量的構造器。
- 個數(Size):目前存儲在表中的鍵值對的個數。
- 負載因子(Load factor):通常表現為 $\frac{size}{capacity}$。當負載因子大小為 0 的時候表示為一個空表。當負載因子大小為 0.5 表示為一個半滿表(half-full table),以此類推。輕負載的表幾乎沒有沖突,因此是插入和查找的最佳選擇(但會減慢使用迭代器進行遍歷的過程)。 HashMap 和 HashSet 有可以讓你指定負載因子的構造器。當表內容量達到了負載因子,集合就會自動擴充為原始容量(桶的數量)的兩倍,并且會將原始的對象存儲在新的桶集合中(也被稱為 rehashing)
HashMap 中負載因子的大小為 0.75(當表內容量大小不足四分之三的時候,不會發生 rehashing 現象)。這看起來是一個非常好的同時考慮到時間和空間消耗的平衡策略。更高的負載因子會減少空間的消耗,但是會增加查詢的耗時。重要的是,查詢操作是你使用的最頻繁的一個操作(包括 `get()` 和 `put()` 方法)。
如果你知道存儲在 HashMap 中確切的條目個數,直接創建一個足夠容量大小的 HashMap,以避免自動發生的 rehashing 操作。
[^1]:
[^2]: 事實證明,質數實際上并不是散列桶的理想容量。近來,(經過廣泛的測試)Java的散列函數都使用2的整數次方。對現代的處理器來說,除法與求余數是最慢的操作。使用2的整數次方長度的散列表,可用掩碼代替除法。
<!-- 分頁 -->
<div style="page-break-after: always;"></div>
- 譯者的話
- 前言
- 簡介
- 第一章 對象的概念
- 抽象
- 接口
- 服務提供
- 封裝
- 復用
- 繼承
- "是一個"與"像是一個"的關系
- 多態
- 單繼承結構
- 集合
- 對象創建與生命周期
- 異常處理
- 本章小結
- 第二章 安裝Java和本書用例
- 編輯器
- Shell
- Java安裝
- 校驗安裝
- 安裝和運行代碼示例
- 第三章 萬物皆對象
- 對象操縱
- 對象創建
- 數據存儲
- 基本類型的存儲
- 高精度數值
- 數組的存儲
- 代碼注釋
- 對象清理
- 作用域
- 對象作用域
- 類的創建
- 類型
- 字段
- 基本類型默認值
- 方法使用
- 返回類型
- 參數列表
- 程序編寫
- 命名可見性
- 使用其他組件
- static關鍵字
- 小試牛刀
- 編譯和運行
- 編碼風格
- 本章小結
- 第四章 運算符
- 開始使用
- 優先級
- 賦值
- 方法調用中的別名現象
- 算術運算符
- 一元加減運算符
- 遞增和遞減
- 關系運算符
- 測試對象等價
- 邏輯運算符
- 短路
- 字面值常量
- 下劃線
- 指數計數法
- 位運算符
- 移位運算符
- 三元運算符
- 字符串運算符
- 常見陷阱
- 類型轉換
- 截斷和舍入
- 類型提升
- Java沒有sizeof
- 運算符總結
- 本章小結
- 第五章 控制流
- true和false
- if-else
- 迭代語句
- while
- do-while
- for
- 逗號操作符
- for-in 語法
- return
- break 和 continue
- 臭名昭著的 goto
- switch
- switch 字符串
- 本章小結
- 第六章 初始化和清理
- 利用構造器保證初始化
- 方法重載
- 區分重載方法
- 重載與基本類型
- 返回值的重載
- 無參構造器
- this關鍵字
- 在構造器中調用構造器
- static 的含義
- 垃圾回收器
- finalize()的用途
- 你必須實施清理
- 終結條件
- 垃圾回收器如何工作
- 成員初始化
- 指定初始化
- 構造器初始化
- 初始化的順序
- 靜態數據的初始化
- 顯式的靜態初始化
- 非靜態實例初始化
- 數組初始化
- 動態數組創建
- 可變參數列表
- 枚舉類型
- 本章小結
- 第七章 封裝
- 包的概念
- 代碼組織
- 創建獨一無二的包名
- 沖突
- 定制工具庫
- 使用 import 改變行為
- 使用包的忠告
- 訪問權限修飾符
- 包訪問權限
- public: 接口訪問權限
- 默認包
- private: 你無法訪問
- protected: 繼承訪問權限
- 包訪問權限 Vs Public 構造器
- 接口和實現
- 類訪問權限
- 本章小結
- 第八章 復用
- 組合語法
- 繼承語法
- 初始化基類
- 帶參數的構造函數
- 委托
- 結合組合與繼承
- 保證適當的清理
- 名稱隱藏
- 組合與繼承的選擇
- protected
- 向上轉型
- 再論組合和繼承
- final關鍵字
- final 數據
- 空白 final
- final 參數
- final 方法
- final 和 private
- final 類
- final 忠告
- 類初始化和加載
- 繼承和初始化
- 本章小結
- 第九章 多態
- 向上轉型回顧
- 忘掉對象類型
- 轉機
- 方法調用綁定
- 產生正確的行為
- 可擴展性
- 陷阱:“重寫”私有方法
- 陷阱:屬性與靜態方法
- 構造器和多態
- 構造器調用順序
- 繼承和清理
- 構造器內部多態方法的行為
- 協變返回類型
- 使用繼承設計
- 替代 vs 擴展
- 向下轉型與運行時類型信息
- 本章小結
- 第十章 接口
- 抽象類和方法
- 接口創建
- 默認方法
- 多繼承
- 接口中的靜態方法
- Instrument 作為接口
- 抽象類和接口
- 完全解耦
- 多接口結合
- 使用繼承擴展接口
- 結合接口時的命名沖突
- 接口適配
- 接口字段
- 初始化接口中的字段
- 接口嵌套
- 接口和工廠方法模式
- 本章小結
- 第十一章 內部類
- 創建內部類
- 鏈接外部類
- 使用 .this 和 .new
- 內部類與向上轉型
- 內部類方法和作用域
- 匿名內部類
- 嵌套類
- 接口內部的類
- 從多層嵌套類中訪問外部類的成員
- 為什么需要內部類
- 閉包與回調
- 內部類與控制框架
- 繼承內部類
- 內部類可以被覆蓋么?
- 局部內部類
- 內部類標識符
- 本章小結
- 第十二章 集合
- 泛型和類型安全的集合
- 基本概念
- 添加元素組
- 集合的打印
- 迭代器Iterators
- ListIterator
- 鏈表LinkedList
- 堆棧Stack
- 集合Set
- 映射Map
- 隊列Queue
- 優先級隊列PriorityQueue
- 集合與迭代器
- for-in和迭代器
- 適配器方法慣用法
- 本章小結
- 簡單集合分類
- 第十三章 函數式編程
- 新舊對比
- Lambda表達式
- 遞歸
- 方法引用
- Runnable接口
- 未綁定的方法引用
- 構造函數引用
- 函數式接口
- 多參數函數式接口
- 缺少基本類型的函數
- 高階函數
- 閉包
- 作為閉包的內部類
- 函數組合
- 柯里化和部分求值
- 純函數式編程
- 本章小結
- 第十四章 流式編程
- 流支持
- 流創建
- 隨機數流
- int 類型的范圍
- generate()
- iterate()
- 流的建造者模式
- Arrays
- 正則表達式
- 中間操作
- 跟蹤和調試
- 流元素排序
- 移除元素
- 應用函數到元素
- 在map()中組合流
- Optional類
- 便利函數
- 創建 Optional
- Optional 對象操作
- Optional 流
- 終端操作
- 數組
- 集合
- 組合
- 匹配
- 查找
- 信息
- 數字流信息
- 本章小結
- 第十五章 異常
- 異常概念
- 基本異常
- 異常參數
- 異常捕獲
- try 語句塊
- 異常處理程序
- 終止與恢復
- 自定義異常
- 異常與記錄日志
- 異常聲明
- 捕獲所有異常
- 多重捕獲
- 棧軌跡
- 重新拋出異常
- 精準的重新拋出異常
- 異常鏈
- Java 標準異常
- 特例:RuntimeException
- 使用 finally 進行清理
- finally 用來做什么?
- 在 return 中使用 finally
- 缺憾:異常丟失
- 異常限制
- 構造器
- Try-With-Resources 用法
- 揭示細節
- 異常匹配
- 其他可選方式
- 歷史
- 觀點
- 把異常傳遞給控制臺
- 把“被檢查的異常”轉換為“不檢查的異常”
- 異常指南
- 本章小結
- 后記:Exception Bizarro World
- 第十六章 代碼校驗
- 測試
- 如果沒有測試過,它就是不能工作的
- 單元測試
- JUnit
- 測試覆蓋率的幻覺
- 前置條件
- 斷言(Assertions)
- Java 斷言語法
- Guava斷言
- 使用斷言進行契約式設計
- 檢查指令
- 前置條件
- 后置條件
- 不變性
- 放松 DbC 檢查或非嚴格的 DbC
- DbC + 單元測試
- 使用Guava前置條件
- 測試驅動開發
- 測試驅動 vs. 測試優先
- 日志
- 日志會給出正在運行的程序的各種信息
- 日志等級
- 調試
- 使用 JDB 調試
- 圖形化調試器
- 基準測試
- 微基準測試
- JMH 的引入
- 剖析和優化
- 優化準則
- 風格檢測
- 靜態錯誤分析
- 代碼重審
- 結對編程
- 重構
- 重構基石
- 持續集成
- 本章小結
- 第十七章 文件
- 文件和目錄路徑
- 選取路徑部分片段
- 路徑分析
- Paths的增減修改
- 目錄
- 文件系統
- 路徑監聽
- 文件查找
- 文件讀寫
- 本章小結
- 第十八章 字符串
- 字符串的不可變
- +的重載與StringBuilder
- 意外遞歸
- 字符串操作
- 格式化輸出
- printf()
- System.out.format()
- Formatter類
- 格式化修飾符
- Formatter轉換
- String.format()
- 一個十六進制轉儲(dump)工具
- 正則表達式
- 基礎
- 創建正則表達式
- 量詞
- CharSequence
- Pattern和Matcher
- find()
- 組(Groups)
- start()和end()
- Pattern標記
- split()
- 替換操作
- 正則表達式與 Java I/O
- 掃描輸入
- Scanner分隔符
- 用正則表達式掃描
- StringTokenizer類
- 本章小結
- 第十九章 類型信息
- 為什么需要 RTTI
- Class對象
- 類字面常量
- 泛化的Class引用
- cast()方法
- 類型轉換檢測
- 使用類字面量
- 遞歸計數
- 一個動態instanceof函數
- 注冊工廠
- 類的等價比較
- 反射:運行時類信息
- 類方法提取器
- 動態代理
- Optional類
- 標記接口
- Mock 對象和樁
- 接口和類型
- 本章小結
- 第二十章 泛型
- 簡單泛型
- 泛型接口
- 泛型方法
- 復雜模型構建
- 泛型擦除
- 補償擦除
- 邊界
- 通配符
- 問題
- 自限定的類型
- 動態類型安全
- 泛型異常
- 混型
- 潛在類型機制
- 對缺乏潛在類型機制的補償
- Java8 中的輔助潛在類型
- 總結:類型轉換真的如此之糟嗎?
- 進階閱讀
- 第二十一章 數組
- 數組特性
- 一等對象
- 返回數組
- 多維數組
- 泛型數組
- Arrays的fill方法
- Arrays的setAll方法
- 增量生成
- 隨機生成
- 泛型和基本數組
- 數組元素修改
- 數組并行
- Arrays工具類
- 數組比較
- 數組拷貝
- 流和數組
- 數組排序
- Arrays.sort()的使用
- 并行排序
- binarySearch二分查找
- parallelPrefix并行前綴
- 本章小結
- 第二十二章 枚舉
- 基本 enum 特性
- 將靜態類型導入用于 enum
- 方法添加
- 覆蓋 enum 的方法
- switch 語句中的 enum
- values 方法的神秘之處
- 實現而非繼承
- 隨機選擇
- 使用接口組織枚舉
- 使用 EnumSet 替代 Flags
- 使用 EnumMap
- 常量特定方法
- 使用 enum 的職責鏈
- 使用 enum 的狀態機
- 多路分發
- 使用 enum 分發
- 使用常量相關的方法
- 使用 EnumMap 進行分發
- 使用二維數組
- 本章小結
- 第二十三章 注解
- 基本語法
- 定義注解
- 元注解
- 編寫注解處理器
- 注解元素
- 默認值限制
- 替代方案
- 注解不支持繼承
- 實現處理器
- 使用javac處理注解
- 最簡單的處理器
- 更復雜的處理器
- 基于注解的單元測試
- 在 @Unit 中使用泛型
- 實現 @Unit
- 本章小結
- 第二十四章 并發編程
- 術語問題
- 并發的新定義
- 并發的超能力
- 并發為速度而生
- 四句格言
- 1.不要這樣做
- 2.沒有什么是真的,一切可能都有問題
- 3.它起作用,并不意味著它沒有問題
- 4.你必須仍然理解
- 殘酷的真相
- 本章其余部分
- 并行流
- 創建和運行任務
- 終止耗時任務
- CompletableFuture類
- 基本用法
- 結合 CompletableFuture
- 模擬
- 異常
- 流異常(Stream Exception)
- 檢查性異常
- 死鎖
- 構造方法非線程安全
- 復雜性和代價
- 本章小結
- 缺點
- 共享內存陷阱
- This Albatross is Big
- 其他類庫
- 考慮為并發設計的語言
- 拓展閱讀
- 第二十五章 設計模式
- 概念
- 單例模式
- 模式分類
- 構建應用程序框架
- 面向實現
- 工廠模式
- 動態工廠
- 多態工廠
- 抽象工廠
- 函數對象
- 命令模式
- 策略模式
- 責任鏈模式
- 改變接口
- 適配器模式(Adapter)
- 外觀模式(Fa?ade)
- 包(Package)作為外觀模式的變體
- 解釋器:運行時的彈性
- 回調
- 多次調度
- 模式重構
- 抽象用法
- 多次派遣
- 訪問者模式
- RTTI的優劣
- 本章小結
- 附錄:補充
- 附錄:編程指南
- 附錄:文檔注釋
- 附錄:對象傳遞和返回
- 附錄:流式IO
- 輸入流類型
- 輸出流類型
- 添加屬性和有用的接口
- 通過FilterInputStream 從 InputStream 讀取
- 通過 FilterOutputStream 向 OutputStream 寫入
- Reader和Writer
- 數據的來源和去處
- 更改流的行為
- 未發生改變的類
- RandomAccessFile類
- IO流典型用途
- 緩沖輸入文件
- 從內存輸入
- 格式化內存輸入
- 基本文件的輸出
- 文本文件輸出快捷方式
- 存儲和恢復數據
- 讀寫隨機訪問文件
- 本章小結
- 附錄:標準IO
- 附錄:新IO
- ByteBuffer
- 數據轉換
- 基本類型獲取
- 視圖緩沖區
- 字節存儲次序
- 緩沖區數據操作
- 緩沖區細節
- 內存映射文件
- 性能
- 文件鎖定
- 映射文件的部分鎖定
- 附錄:理解equals和hashCode方法
- 附錄:集合主題
- 附錄:并發底層原理
- 附錄:數據壓縮
- 附錄:對象序列化
- 附錄:靜態語言類型檢查
- 附錄:C++和Java的優良傳統
- 附錄:成為一名程序員