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的某些優點。

另外,請注意,我們並不關心StringIntegerLong或其他包裝器類型的鍵。 wrapper類中的equal()hashCode()方法都已被覆蓋。

5.迭代哈希表

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

5.1。快速失敗:迭代

快速失敗迭代意味著,如果在創建HashtableIterator之後修改了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. HashtableHashMap

HashtableHashMap提供了非常相似的功能。

他們兩個都提供:

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

但是也有一些區別:

  • 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上找到