Java.util.Hashtable類簡介

1.概述

哈希表是最古老的實現Java中的哈希表的數據結構。 HashMap是第二個實現，它是JDK 1.2中引入的。

兩種類都提供相似的功能，但也有一些細微差別，我們將在本教程中進行探討。

2.何時使用Hashtable

假設我們有一個字典，其中每個單詞都有其定義。另外，我們需要快速從字典中獲取，插入和刪除單詞。

因此， Hashtable （或HashMap ）是有意義的。單詞將成為哈希表中的鍵，因為它們應該是唯一的。另一方面，定義將是值。

3.使用示例

讓我們繼續字典示例。我們將把Word建模為關鍵：

public class Word {

 private String name;



 public Word(String name) {

 this.name = name;

 }



 // ...

 }

假設值是Strings 。現在我們可以創建一個Hashtable ：

Hashtable<Word, String> table = new Hashtable<>();

首先，讓我們添加一個條目：

Word word = new Word("cat");

 table.put(word, "an animal");

另外，要獲得一個條目：

String definition = table.get(word);

最後，讓我們刪除一個條目：

definition = table.remove(word);

該類中還有許多其他方法，我們將在後面介紹其中一些方法。

但是首先，讓我們談談對關鍵對象的一些要求。

4. hashCode（）的重要性

要用作Hashtable中的鍵，該對像一定不能違反hashCode（）協定。簡而言之，相等的對象必須返回相同的代碼。為了理解為什麼讓我們看一下哈希表的組織方式。

哈希表使用數組。數組中的每個位置都是一個“存儲桶”，可以為空，也可以包含一個或多個鍵值對。計算每對的索引。

但是為什麼不按順序存儲元素，在數組末尾添加新元素呢？

關鍵是，按索引查找元素比按順序進行比較遍曆元素要快得多。因此，我們需要一個將鍵映射到索引的函數。

4.1。直接地址表

這種映射的最簡單示例是直接地址表。此處，鍵用作索引：

index(k)=k,

 where k is a key

鍵是唯一的，即每個存儲桶都包含一個鍵值對。當整數鍵的可能範圍相當小時，此技術適用於整數鍵。

但是我們這裡有兩個問題：

• 首先，我們的鍵不是整數，而是Word對象
• 其次，如果它們是整數，則沒人會保證它們很小。想像一下，鍵是1、2和1000000。我們將有一個大數組，大小為1000000，只有三個元素，其餘的將是浪費的空間

hashCode（）方法解決了第一個問題。

哈希表中的數據操作邏輯解決了第二個問題。

讓我們深入討論。

4.2。 hashCode（）方法

任何Java對像都繼承hashCode（）方法，該方法返回一個int值。該值是根據對象的內部存儲器地址計算得出的。默認情況下， hashCode（）為不同的對象返回不同的整數。

因此，可以使用hashCode（）將任何鍵對象轉換為整數。但是這個整數可能很大。

4.3。縮小範圍

get（） ， put（）和remove（）方法包含解決第二個問題的代碼-減小可能整數的範圍。

該公式計算密鑰的索引：

int index = (hash & 0x7FFFFFFF) % tab.length;

其中tab.length是數組大小， hash是鍵的hashCode（）方法返回的數字。

正如我們所看到的， index提醒我們用數組大小表示除法哈希。請注意，相等的哈希碼會產生相同的索引。

4.4。碰撞

此外，即使不同的哈希碼也可以產生相同的索引。我們將此稱為衝突。為了解決衝突，哈希表存儲鍵值對的LinkedList 。

這種數據結構稱為帶有鍊錶的哈希表。

4.5。負載係數

不難猜測，碰撞會減慢元素的操作速度。要獲得條目，僅知道其索引是不夠的，但是我們需要遍歷列表並與每個項目進行比較。

因此，減少衝突數量很重要。數組越大，發生碰撞的機會就越小。負載係數決定了陣列大小和性能之間的平衡。默認情況下為0.75，這意味著當75％的存儲桶不為空時，數組大小將增加一倍。此操作由rehash（）方法執行。

但是，讓我們回到關鍵。

4.6。覆蓋equals（）和hashCode（）

當我們將一個條目放入哈希表並從中取出時，我們期望不僅可以使用相同的鍵實例，而且可以使用相等的鍵來獲取值：

Word word = new Word("cat");

 table.put(word, "an animal");

 String extracted = table.get(new Word("cat"));

要設置相等規則，我們重寫鍵的equals（）方法：

public boolean equals(Object o) {

 if (o == this)

 return true;

 if (!(o instanceof Word))

 return false;



 Word word = (Word) o;

 return word.getName().equals(this.name);

 }

但是，如果我們沒有重載hashCode（）忽略equals（）時，則兩個相等的鍵可以在不同的桶最終因為Hashtable的計算使用其散列碼的關鍵指數。

讓我們仔細看一下上面的例子。如果不重寫hashCode（）會發生什麼？

• 這裡涉及兩個Word實例–第一個實例用於放置條目，第二個實例用於獲取條目。儘管這些實例相等，但是它們的hashCode（）方法返回不同的數字
• 每個密鑰的索引由第4.3節中的公式計算得出。根據此公式，不同的哈希碼可能會產生不同的索引
• 這意味著我們將條目放入一個存儲桶中，然後嘗試從另一個存儲桶中取出它。這樣的邏輯打破了哈希表

相等的鍵必須返回相等的哈希碼，這就是為什麼我們重寫hashCode（）方法的原因：

public int hashCode() {

 return name.hashCode();

 }

請注意，還建議使不相等的鍵返回不同的哈希碼，否則它們將最終出現在同一存儲桶中。這會影響性能，因此會失去Hashtable的某些優點。

另外，請注意，我們並不關心String ， Integer ， Long或其他包裝器類型的鍵。 wrapper類中的equal（）和hashCode（）方法都已被覆蓋。

5.迭代哈希表

有幾種迭代Hashtables的方法。在本節中，將對它們進行很好的討論並解釋其中的一些含義。

5.1。快速失敗：迭代

快速失敗迭代意味著，如果在創建Hashtable的Iterator之後修改了Hashtable ，則將引發ConcurrentModificationException 。讓我們演示一下。

首先，我們將創建一個哈希表並向其添加條目：

Hashtable<Word, String> table = new Hashtable<Word, String>();

 table.put(new Word("cat"), "an animal");

 table.put(new Word("dog"), "another animal");

其次，我們將創建一個Iterator ：

Iterator<Word> it = table.keySet().iterator();

第三，我們將修改表：

table.remove(new Word("dog"));

現在，如果我們嘗試遍歷表，我們將獲得ConcurrentModificationException ：

while (it.hasNext()) {

 Word key = it.next();

 }

java.util.ConcurrentModificationException


 at java.util.Hashtable$Enumerator.next(Hashtable.java:1378)

ConcurrentModificationException有助於發現錯誤，從而避免不可預測的行為，例如，當一個線程正在遍歷該表，而另一個正在嘗試同時對其進行修改時。

5.2。不快速失敗：枚舉

哈希表中的**枚舉不是快速失敗的。讓我們來看一個例子。

首先，讓我們創建一個哈希表並向其中添加條目：

Hashtable<Word, String> table = new Hashtable<Word, String>();

 table.put(new Word("1"), "one");

 table.put(new Word("2"), "two");

其次，讓我們創建一個Enumeration ：

Enumeration<Word> enumKey = table.keys();

第三，讓我們修改表：

table.remove(new Word("1"));

現在，如果我們遍歷表，它將不會引發異常：

while (enumKey.hasMoreElements()) {

 Word key = enumKey.nextElement();

 }

5.3。不可預測的迭代順序

另外，請注意，哈希表中的迭代順序是不可預測的，並且與條目添加的順序不匹配。

這是可以理解的，因為它使用密鑰的哈希碼計算每個索引。此外，不時進行哈希處理，重新排列數據結構的順序。

因此，讓我們添加一些條目並檢查輸出：

Hashtable<Word, String> table = new Hashtable<Word, String>();

 table.put(new Word("1"), "one");

 table.put(new Word("2"), "two");

 // ...

 table.put(new Word("8"), "eight");



 Iterator<Map.Entry<Word, String>> it = table.entrySet().iterator();

 while (it.hasNext()) {

 Map.Entry<Word, String> entry = it.next();

 // ...

 }

 }

five

 four

 three

 two

 one

 eight

 seven

6. Hashtable與HashMap

Hashtable和HashMap提供了非常相似的功能。

他們兩個都提供：

• 快速失敗的迭代
• 不可預測的迭代順序

但是也有一些區別：

• HashMap不提供任何枚舉，而**Hashtable不提供快速失敗的枚舉
• Hashtable不允許空鍵和空值，而HashMap允許一個空鍵和任意數量的空值
• Hashtable的方法不同步，而HashMaps的方法不同步

7. Java 8中的哈希表API

Java 8引入了有助於使我們的代碼更整潔的新方法。特別是，我們可以擺脫一些if塊。讓我們演示一下。

7.1。 getOrDefault（）

假設我們需要獲取單詞“ dog ”的定義，並將其分配給表中的變量。否則，將“找不到”分配給變量。

在Java 8之前：

Word key = new Word("dog");

 String definition;



 if (table.containsKey(key)) {

 definition = table.get(key);

 } else {

 definition = "not found";

 }

在Java 8之後：

definition = table.getOrDefault(key, "not found");

7.2。 putIfAbsent（）

假設只有在字典中還沒有的時候，才需要添加“ cat ”一詞。

在Java 8之前：

if (!table.containsKey(new Word("cat"))) {

 table.put(new Word("cat"), definition);

 }

在Java 8之後：

table.putIfAbsent(new Word("cat"), definition);

7.3。布爾值remove（）

假設我們需要刪除“貓”一詞，但前提是它的定義是“動物”。

在Java 8之前：

if (table.get(new Word("cat")).equals("an animal")) {

 table.remove(new Word("cat"));

 }

在Java 8之後：

boolean result = table.remove(new Word("cat"), "an animal");

最後，當舊的remove（）方法返回值時，新方法返回boolean 。

7.4。更換（）

假設我們需要替換“貓”的定義，但前提是它的舊定義是“小型馴養的食肉哺乳動物”。

在Java 8之前：

if (table.containsKey(new Word("cat"))

 && table.get(new Word("cat")).equals("a small domesticated carnivorous mammal")) {

 table.put(new Word("cat"), definition);

 }

在Java 8之後：

table.replace(new Word("cat"), "a small domesticated carnivorous mammal", definition);

7.5。 computeIfAbsent（）

此方法類似於putIfabsent（） 。但是putIfabsent（）直接採用該值， computeIfAbsent（）採用映射函數。它僅在檢查密鑰後才計算值，這會更有效，尤其是在難以獲得值的情況下。

table.computeIfAbsent(new Word("cat"), key -> "an animal");

因此，以上行等效於：

if (!table.containsKey(cat)) {

 String definition = "an animal"; // note that calculations take place inside if block

 table.put(new Word("cat"), definition);

 }

7.6。 computeIfPresent（）

此方法類似於replace（）方法。但是，再次， replace（）直接採用該值， computeIfPresent（）採用映射函數。它計算if塊內部的值，這就是為什麼它效率更高的原因。

假設我們需要更改定義：

table.computeIfPresent(cat, (key, value) -> key.getName() + " - " + value);

因此，以上行等效於：

if (table.containsKey(cat)) {

 String concatination=cat.getName() + " - " + table.get(cat);

 table.put(cat, concatination);

 }

7.7。compute()

現在，我們將解決另一個任務。假設我們有一個String數組，其中的元素不是唯一的。另外，讓我們計算在數組中可以得到多少次出現的String。這是數組：

String[] animals = { "cat", "dog", "dog", "cat", "bird", "mouse", "mouse" };

另外，我們想創建一個Hashtable ，其中包含一個動物作為鍵，其出現次數作為一個值。

這是一個解決方案：

Hashtable<String, Integer> table = new Hashtable<String, Integer>();



 for (String animal : animals) {

 table.compute(animal,

 (key, value) -> (value == null ? 1 : value + 1));

 }

最後，讓我們確保該表包含兩隻貓，兩隻狗，一隻鳥和兩隻鼠標：

assertThat(table.values(), hasItems(2, 2, 2, 1));

7.8。merge()

還有另一種方法可以解決上述任務：

for (String animal : animals) {

 table.merge(animal, 1, (oldValue, value) -> (oldValue + value));

 }

第二個參數1是如果鍵尚未在表上，則映射到鍵的值。如果鍵已經在表中，則我們將其計算為oldValue + 1 。

7.9。 foreach（）

這是一種遍歷條目的新方法。讓我們打印所有條目：

table.forEach((k, v) -> System.out.println(k.getName() + " - " + v)

7.10。replaceAll()

此外，我們無需迭代即可替換所有值：

table.replaceAll((k, v) -> k.getName() + " - " + v);

8.結論

在本文中，我們描述了哈希表結構的目的，並展示瞭如何使直接地址表結構複雜化以獲取哈希表結構。

此外，我們還介紹了哈希表中的衝突和負載因數。此外，我們還了解了為什麼要為關鍵對象覆蓋equals（）和hashCode（） 。

最後，我們討論了Hashtable的屬性和特定於Java 8的API。

與往常一樣，完整的源代碼可 在Github上找到。