Java 之路/表
array Vector table
陣列是一種通用的資料結構，但它們存在兩個重要的限制
專案符號
陣列的大小不取決於它包含的專案數量。如果陣列太大，就會浪費空間。如果太小，可能會導致錯誤，或者我們可能需要編寫程式碼來調整它的大小。
雖然陣列可以包含任何型別的專案，但陣列的索引必須是整數。例如，我們不能使用字串來指定陣列中的元素。
專案符號
在向量部分，我們看到了內建的 Vector 類是如何解決第一個問題的。隨著使用者新增專案，它會自動擴充套件。還可以縮小 Vector，使其容量與當前大小相同。
但是 Vectors 無法幫助解決第二個問題。索引仍然是整數。
這就是表 ADT 出現的地方。表是 Vector 的泛化，可以使用任何型別作為索引。這些泛化索引稱為鍵。
就像使用索引訪問陣列中的值一樣，使用鍵訪問表中的值。因此，每個鍵都與一個值相關聯，這就是為什麼表有時被稱為關聯陣列的原因。
dictionary associative array key entry index
表的常見示例是字典，它是將單詞（鍵）與其定義（值）相關聯的表。由於這個例子，表有時也被稱為字典。此外，將特定鍵與特定值相關聯稱為條目。
Table ADT ADT!Table
與我們看過的其他 ADT 一樣，表是由它們支援的操作集定義的
描述
[建構函式：] 建立一個新的空表。
[put：] 建立一個將值與鍵關聯的條目。
[get：] 對於給定的鍵，查詢相應的 value。
[containsKey：] 如果表中存在使用給定鍵的條目，則返回 true。
[keys：] 返回包含表中所有鍵的集合。
描述
Hashtable class!Hashtable
Java 提供了表 ADT 的實現，稱為 Hashtable。它位於 java.util 包中。在本章後面，我們將看到為什麼它被稱為 Hashtable。
為了演示 Hashtable 的使用，我們將編寫一個簡短的程式，該程式遍歷一個字串並統計每個單詞出現的次數。
我們將建立一個名為 WordCount 的新類，該類將構建表並列印其內容。自然地，每個 WordCount 物件都包含一個 Hashtable
逐字 public class WordCount
Hashtable ht;
public WordCount ()
ht = new Hashtable ();
逐字
WordCount 的唯一公共方法是 processLine，它接受一個字串並將它的單詞新增到表中，以及 print，它在最後列印結果。
processLine 使用 StringTokenizer 將字串分解為單詞，並將每個單詞傳遞給 processWord。
逐字
public void processLine (String s)
StringTokenizer st = new StringTokenizer (s, " ,.");
while (st.hasMoreTokens())
String word = st.nextToken();
processWord (word.toLowerCase ());
逐字
有趣的工作在 processWord 中。
逐字
public void processWord (String word)
if (ht.containsKey (word))
Integer i = (Integer) ht.get (word);
Integer j = new Integer (i.intValue() + 1);
ht.put (word, j);
else
ht.put (word, new Integer (1));
逐字
如果單詞已存在於表中，我們將獲取其計數器，遞增它，然後放入新值。否則，我們只將一個新條目放入表中，並將計數器設定為 1。
Enumeration class class!Enumeration traverse
要打印表中的條目，我們需要能夠遍歷表中的鍵。幸運的是，Hashtable 實現提供了一個名為 keys 的方法，該方法返回一個我們可以使用的 Enumeration 物件。列舉與我們在迭代器部分看到的迭代器非常相似。兩者都是 java.util 包中的抽象類；您應該檢視兩者的文件。以下是使用 keys 列印 Hashtable 內容的方法
逐字
public void print ()
Enumeration enum = ht.keys ();
while (enum.hasMoreElements ())
String key = (String) enum.nextElement ();
Integer value = (Integer) ht.get (key);
System.out.println (" " + key + ", " + value + " ");
逐字
列舉的每個元素都是一個物件，但由於我們知道它們是鍵，因此我們將它們型別轉換為字串。當我們從表中獲取值時，它們也是物件，但我們知道它們是計數器，因此我們將它們型別轉換為整數。
最後，要統計字串中的單詞
逐字
WordCount wc = new WordCount ();
wc.processLine ("da doo ron ron ron, da doo ron ron");
wc.print ();
逐字
輸出是
逐字
ron, 5 doo, 2 da, 2
逐字
列舉的元素沒有任何特定的順序。唯一保證的是表中的所有鍵都會出現。
implementation!Table table!vector implementation KeyValuePair
實現表 ADT 的一種簡單方法是使用條目向量，其中每個條目都是包含鍵和值的 object。這些物件被稱為鍵值對。
KeyValuePair 的類定義可能如下所示
逐字 class KeyValuePair
Object key, value;
public KeyValuePair (Object key, Object value)
this.key = key;
this.value = value;
public String toString ()
return " " + key + ", " + value + " ";
逐字
然後表的實現如下所示
逐字 public class Table
Vector v;
public Table ()
v = new Vector ();
逐字
要將新條目放入表中，我們只需將新的 KeyValuePair 新增到 Vector 中
逐字
public void put (Object key, Object value)
KeyValuePair pair = new KeyValuePair (key, value);
v.add (pair);
逐字
然後，要查詢表中的鍵，我們必須遍歷 Vector 並找到具有匹配鍵的 KeyValuePair
逐字
public Object get (Object key)
Iterator iterator = v.iterator ();
while (iterator.hasNext ())
KeyValuePair pair = (KeyValuePair) iterator.next ();
if (key.equals (pair.key))
return pair.value;
return null;
逐字
遍歷 Vector 的習慣用法是我們之前在迭代器部分看到的。當我們比較鍵時，我們使用深度相等（equals 方法）而不是淺層相等（== 運算子）。這允許鍵類指定相等的定義。在我們的示例中，鍵是字串，因此它將使用 String 類中的內建 equals 方法。
traverse
對於大多數內建類，equals 方法實現深度相等。然而，對於某些類，很難定義這意味著什麼。例如，請參閱 Doubles 的 equals 文件。
equals equality
由於 equals 是一個物件方法，因此 get 的這個實現如果 key 為 null 則無法正常工作。我們可以將 null 作為特殊情況進行處理，或者我們可以像內建的 Hashtable 一樣---簡單地宣告 null 不是合法鍵。
說到內建的 Hashtable，它的 put 實現與我們的實現略有不同。如果表中已經存在使用給定鍵的條目，put 會更新它（賦予它一個新值），並返回舊值（如果沒有舊值，則返回 null。以下是它們的版本的實現
逐字
public Object put (Object key, Object value)
Object result = get (key);
if (result == null)
KeyValuePair pair = new KeyValuePair (key, value);
v.add (pair);
else
update (key, value);
return result;
逐字
update 方法不是表 ADT 的一部分，因此它被宣告為私有。它遍歷向量，直到找到正確的 KeyValuePair，然後更新 value 欄位。請注意，我們不必修改 Vector 本身，只需修改它包含的其中一個物件即可。
逐字
private void update (Object key, Object value)
Iterator iterator = v.iterator ();
while (iterator.hasNext ())
KeyValuePair pair = (KeyValuePair) iterator.next ();
if (key.equals (pair.key))
pair.value = value;
break;
逐字
我們還沒有實現的唯一方法是 containsKey 和 keys。containsKey 方法幾乎與 get 相同，除了它返回 true 或 false 而不是物件引用或 null。
作為練習，透過構建鍵向量並返回向量中的元素來實現 keys。有關更多資訊，請參閱 Vector 類中的元素文件。
abstract class!List List abstract class
java.util 包定義了一個名為 List 的抽象類，它指定了類為了被認為（非常抽象地）是一個列表而必須實現的操作集。當然，這並不意味著每個實現 List 的類都必須是連結串列。
不出所料，內建的 LinkedList 類是 List 抽象類的一個成員。令人驚訝的是，Vector 也是如此。
List 定義中的方法包括 add、get 和 iterator。事實上，我們用來實現 Table 的 Vector 類中的所有方法都在 List 抽象類中定義。
這意味著我們可以使用任何 List 類來代替 Vector。在 Table.java 中，我們可以用 LinkedList 替換 Vector，程式仍然可以正常工作！
這種型別通用性對於調整程式效能很有用。你可以用 List 這樣的抽象類來編寫程式，然後用幾個不同的實現來測試程式，看看哪個實現可以獲得最佳效能。
implementation!Table implementation!hash table hash table!implementation table!hash table implementation
Table ADT 的內建實現被稱為 Hashtable，因為它使用了一種稱為雜湊表的 Table 的特別高效的實現。
當然，定義 ADT 的全部意義在於它允許我們在不知道細節的情況下使用實現。因此，Java 庫的編寫者根據其實現而不是其 ADT 來命名這個類可能不是一件好事，但我認為在他們所做的一切壞事中，這件事算是很小了。
無論如何，你可能想知道雜湊表是什麼，以及為什麼我說它特別高效。我們將從分析我們剛剛完成的 List 實現的效能開始。
檢視 put 的實現，我們看到有兩種情況。如果鍵不在表中，那麼我們只需要建立一個新的鍵值對並將其新增到 List 中。這兩種操作都是常數時間操作。
在另一種情況下，我們必須遍歷 List 以找到現有的鍵值對。這是一個線性時間操作。出於同樣的原因，get 和 containsKey 也是線性的。
雖然線性操作通常足夠好，但我們可以做得更好。事實證明，有一種方法可以實現 Table ADT，使 put 和 get 都是常數時間操作！
關鍵是認識到遍歷列表所需的時間與列表的長度成正比。如果我們可以對列表的長度設定上限，那麼我們就可以對遍歷時間設定上限，而任何具有固定上限的東西都被認為是常數時間。
analysis!hashtable
但是，如何在不限制表中專案數量的情況下限制列表的長度？透過增加列表的數量。我們不會使用一個長列表，而是保留許多短列表。
只要我們知道要搜尋哪個列表，我們就可以對搜尋量設定上限。
hash function mapping
這就是雜湊函式的作用。我們需要某種方法來檢視一個鍵，並在不搜尋的情況下知道它位於哪個列表中。我們將假設列表位於陣列（或 Vector）中，因此我們可以透過索引引用它們。
解決方案是找到鍵值與列表索引之間的一種對映關係——幾乎任何對映都可以。對於每個可能的鍵，必須有一個索引，但可能有多個鍵對映到同一個索引。
例如，想象一個包含 8 個列表的陣列和一個由鍵（為整數）和值（為字串）組成的表。由於它們是正確的型別，因此使用整數的 intValue 作為索引可能很誘人，但有很多整數不在 0 到 7 之間，而 0 到 7 是唯一合法的索引。
modulus operator!modulus
模運算子提供了一種簡單（就程式碼而言）且高效（就執行時間而言）的方法，將所有整數對映到範圍。表示式
逐字
key.intValue()
逐字
保證產生 -7 到 7（包含兩者）之間的值。如果取其絕對值（使用 Math.abs），你將獲得一個合法的索引。
對於其他型別，我們可以玩類似的遊戲。例如，要將 Character 轉換為整數，我們可以使用內建方法 Character.getNumericValue，對於 Doubles，可以使用 intValue。
shifted sum
對於字串，我們可以獲取每個字元的數值並將其加起來，或者使用移位求和。要計算移位求和，請在將新值新增到累加器和將累加器左移之間交替。透過“左移”我的意思是“乘以一個常數”。
為了瞭解它是如何工作的，請檢視以下數字列表。
and compute their shifted sum as
首先，將累加器初始化為 0。然後，
列舉
將累加器乘以 10。
將列表的下一個元素新增到累加器。
重複此操作，直到列表結束。
列舉
作為練習，編寫一個方法，使用 32 的乘數計算字串中字元的數值的移位求和。
對於每種型別，我們可以找到一個函式，它接收該型別的值並生成相應的整數值。這些函式稱為雜湊函式，因為它們通常涉及對物件元件進行雜湊。每個物件的整數值稱為其雜湊碼。
還有一種方法可以為 Java 物件生成雜湊碼。每個 Java 物件都提供一個名為 hashCode 的方法，該方法返回對應於該物件的整數。對於內建型別，hashCode 方法的實現方式是，如果兩個物件包含相同的資料，它們將具有相同的雜湊碼（如深度相等）。這些方法的文件解釋了雜湊函式是什麼。你應該檢視它們。
deep equality hash function hash code
對於使用者定義的型別，由實現者提供適當的雜湊函式。在 Object 類中提供的預設雜湊函式通常使用物件的地址來生成雜湊碼，因此它對“相同性”的理解是淺層相等。通常，當我們在雜湊表中搜索一個鍵時，淺層相等不是我們想要的。
無論雜湊碼是如何生成的，最後一步都是使用模運算子和絕對值將雜湊碼對映到合法索引的範圍內。
resizing hash table!resizing
讓我們回顧一下。雜湊表由一個列表陣列（或 Vector）組成，每個列表包含少量鍵值對。要將新條目新增到表中，我們計算新鍵的雜湊碼，並將條目新增到相應的列表中。
要查詢一個鍵，我們再次對其進行雜湊，並搜尋相應的列表。如果列表的長度是有界的，那麼搜尋時間也是有界的。
那麼我們如何保持列表的長度很短呢？一個目標是儘可能地保持它們平衡，這樣就不會出現一些列表非常長而其他列表為空的情況。這並不容易做到完美——這取決於我們選擇雜湊函式的好壞——但我們通常可以做得很好。
即使完全平衡，平均列表長度也會隨著條目數量的增加而線性增長，我們必須阻止這種情況發生。
解決方案是跟蹤每個列表的平均條目數量，稱為負載因子；如果負載因子過高，我們必須調整表的大小。
load factor rehashing
要調整大小，我們建立一個新表，通常是原始表的兩倍大，將所有條目從舊錶中取出，再次對其進行雜湊，然後將它們放到新表中。通常我們可以使用相同的雜湊函式；我們只是對模運算子使用不同的值。
analysis!Hashtable
調整表大小需要多長時間？顯然，它與條目數量成正比。這意味著，在大多數情況下，put 需要常數時間，但有時——當我們調整大小——它需要線性時間。
一開始這聽起來很糟糕。這難道不會破壞我關於 put 可以用常數時間執行的說法嗎？坦率地說，是的。但只要稍微哄哄，我就可以解決它。
由於有些 put 操作比其他操作花費的時間更長，讓我們計算一下 put 操作的平均時間。平均值將是，一個簡單 put 的常數時間，再加上一個額外的項，即，我們必須調整大小的百分比，乘以，調整大小的成本。
方程 t(n) = c + p kn 方程
我不知道 和 是什麼，但我們可以弄清楚是什麼
is. Imagine that we have just resized the hash table by
將其大小加倍。如果有 個條目，那麼在必須再次調整大小之前，我們可以新增 個額外的條目。因此，我們必須調整大小的百分比是 。
代入方程，我們得到
方程 t(n) = c + 1/n kn = c + k 方程
換句話說，是常數時間！
table entry key value dictionary associative array hash table hash function hash code shifted sum load factor
描述
[表:] 定義對條目集合的操作的 ADT。
[條目:] 表中包含鍵值對的元素。
[鍵:] 用於在表中查詢值的任何型別的索引。
[值:] 儲存在表中的任何型別的元素。
[字典:] 另一個表名。
[關聯陣列:] 另一個字典名。
[雜湊表:] 一種特別高效的表實現。
[雜湊函式:] 一個將某種型別的對映到整數的函式。
[雜湊碼:] 對應於給定值的整數值。
[移位求和:] 一種簡單的雜湊函式，通常用於像字串這樣的複合物件。
[負載因子:] 雜湊表中條目的數量除以雜湊表中列表的數量；即每個列表的平均條目數。
描述