在 Java 中限制 HashMap 的最大大小

1. 概述

HashMap是 Java Collections 函式庫中的一個著名類別。它實現了Map介面並允許存儲鍵值對。 HashMap實例對其條目數沒有限制。在某些特定場景中，我們可能想要改變這種行為。在本教程中，我們將研究對HashMap實作大小限制的幾種可能方法。

2. Java HashMap的概念

HashMap的核心本質上就是一個哈希表。哈希表是一種基於另外兩種基本結構的基本資料結構：數組和鍊錶。

2.1.內部結構

數組是HashMap的基本儲存實體。數組的每個位置都包含對鍊錶的參考。鍊錶可以包含一組由鍵和值組成的條目。鍵和值都是Java對象，而不是原始型別，鍵是唯一的。 HashMap的介面有一個put方法，定義如下：

V put(K key, V value)

它使用所謂的“雜湊函數”，根據輸入鍵計算出一個稱為“雜湊”的數字。然後，從雜湊開始，根據數組的當前大小，計算要插入條目的索引。

不同的鍵值可以具有相同的雜湊值，因此具有相同的索引。這會導致衝突，當發生這種情況時，該條目將插入到該索引的鍊錶的下一個位置。

如果鍊錶中的條目數大於由TREEIFY_THRESHOLD常數定義的特定閾值， HashMap會用樹替換鍊錶，從而將運行時效能從O(n)提高到O(log(n)) 。

2.2.調整大小、重新散列和負載因子

從效能的角度來看，理想的情況是條目分佈在整個陣列中，每個位置最多有一個條目。然而，隨著條目數量的增加，衝突的數量也會增加，每個位置的鍊錶大小也會增加。

為了保持盡可能接近理想的情況， HashMap在條目數量達到一定限制時會自行調整大小，然後重新計算雜湊值和索引。

HashMap根據「負載因子」調整自身大小。我們可以將負載因子定義為在需要調整大小和重新散列之前條目數除以可用位置之間的分數的最大值。 HashMap的預設負載因子是0.75f。

3. 可能需要HashMap最大大小的場景

HashMap的大小僅受可用 Java 虛擬機器記憶體的限制。這就是類別的設計方式，並且它與哈希表資料結構的常規用例一致。

儘管如此，在某些特定情況下，我們可能需要施加自訂限制。例如：

• 實現緩存
• 在明確定義的條件下收集HashMap指標，避免其自動調整大小階段

正如我們將在以下部分中看到的，對於第一種情況，我們可以使用LinkedHashMap擴充及其removeEldestEntry方法。對於第二種情況，我們必須實作HashMap的自訂擴充。

這些場景與HashMap設計的初衷相去甚遠。快取是一個比簡單映射更廣泛的概念，並且需要擴展原始類別使得無法像純黑盒一樣對其進行測試。

4. 使用LinkedHashMap限制最大大小

限制最大大小的一種可能方法是使用LinkedHashMap ，它是HashMap. LinkedHashMap是HashMap和LinkedList的組合：它儲存指向上一個和下一個條目的指標。因此，它可以維護其條目的插入順序，而HashMap不支援這一點。

4.1. LinkedHashMap的範例

我們可以透過重寫removeEldestEntry()方法來限制最大大小。此方法傳回boolean ，並在內部呼叫以決定是否應在新插入後刪除最舊的條目。

最舊的條目將是最近最少插入的鍵或最近最少訪問的條目，取決於我們是否使用accessOrder參數建立LinkedHashMap實例（預設值為false ）或true 。

透過重寫removeEldestEntry()方法，我們定義了自己的規則：

@Test
 void givenLinkedHashMapObject_whenAddingNewEntry_thenEldestEntryIsRemoved() {
 final int MAX_SIZE = 4;
 LinkedHashMap<Integer, String> linkedHashMap;
 linkedHashMap = new LinkedHashMap<Integer, String>() {
 @Override
 protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
 return size() > MAX_SIZE;
 }
 };
 linkedHashMap.put(1, "One");
 linkedHashMap.put(2, "Two");
 linkedHashMap.put(3, "Three");
 linkedHashMap.put(4, "Four");
 linkedHashMap.put(5, "Five");
 String[] expectedArrayAfterFive = { "Two", "Three", "Four", "Five" };
 assertArrayEquals(expectedArrayAfterFive, linkedHashMap.values()
 .toArray());
 linkedHashMap.put(6, "Six");
 String[] expectedArrayAfterSix = { "Three", "Four", "Five", "Six" };
 assertArrayEquals(expectedArrayAfterSix, linkedHashMap.values()
 .toArray());
 }

在上面的範例中，我們建立了LinkedHashMap的實例，並重寫了其removeEldestEntry方法。然後，當您新增條目時條目集的大小變得大於給定限制時，實例本身將在插入新條目之前刪除其最舊的鍵。

在測試案例中，我們在setUp方法中初步設定最大大小為4，並用四個條目填入LinkedHashMap物件。我們可以看到，對於每次進一步插入，條目數始終為 4，且LinkedHashMap實例每次都會刪除其最舊的條目。

我們必須注意，這並不是對限制最大大小的要求的嚴格解釋，因為仍然允許插入操作：透過刪除最舊的鍵來保留最大大小。

我們可以透過使用適當的建構函式來建立accessOrder參數為true LinkedHashMap來實現所謂的 LRU（最近最少使用）快取。

4.2.性能考慮因素

常規HashMap具有我們期望的哈希表資料結構的性能。另一方面， LinkedHashMap必須保持其條目的順序，使其插入和刪除操作變慢。除非我們將accessOrder標誌設為true ，否則存取操作的效能不會改變。

5. 使用自訂HashMap限制最大大小

另一個可能的策略是使用put方法的自訂實作來擴展HashMap 。當HashMap實例達到強加的限制時，我們可以使此實作引發異常。

5.1.實作自訂HashMap

對於這種方法，我們必須重寫put方法，這會進行初步檢查：

public class HashMapWithMaxSizeLimit<K, V> extends HashMap<K, V> {
 private int maxSize = -1;

 public HashMapWithMaxSizeLimit(int maxSize) {
 super();
 this.maxSize = maxSize;
 }

 @Override
 public V put(K key, V value) {
 if (this.maxSize == -1 || this.containsKey(key) || this.size() < this.maxSize) {
 return super.put(key, value);
 }
 throw new RuntimeException("Max size exceeded!");
 }
 }

在上面的例子中，我們有一個HashMap.它有一個maxSize屬性，預設值為-1 ，這隱式意味著「無限制」 。我們可以透過特定的建構子來修改這個屬性。在put實作中，如果maxSize等於預設值，鍵已經存在，或者條目數低於指定的maxSize ，則擴充呼叫超類別的相應方法。

如果擴充不符合上述條件，則會引發未經檢查的異常。我們不能使用受檢查的異常，因為put方法不會明確拋出任何異常，我們無法重新定義其簽章。在我們的範例中，可以使用putAll來規避此限制。為了避免這種情況，我們可能還想透過使用相同的邏輯來重寫putAll來改進範例。

為了使範例簡單，我們沒有重新定義超類別的所有建構子。不過，我們應該在實際用例中這樣做，以保持HashMap的原始設計。在這種情況下，我們也應該在HashMap(Map<? extends K, ? extends V> m)建構函式中使用最大大小邏輯，因為它加入了 map 參數的所有條目，而不使用putAll 。

該解決方案比上一節中描述的解決方案更嚴格地遵循要求。在這種情況下， HashMap會禁止任何超出限制的插入操作，而不會刪除任何現有元素。

5.2.測試自訂HashMap

作為例子，我們可以測試上面的自訂類別：

private final int MAX_SIZE = 4;
 private HashMapWithMaxSizeLimit<Integer, String> hashMapWithMaxSizeLimit;

 @Test
 void givenCustomHashMapObject_whenThereIsNoLimit_thenDoesNotThrowException() {
 hashMapWithMaxSizeLimit = new HashMapWithMaxSizeLimit<Integer, String>();
 assertDoesNotThrow(() -> {
 for (int i = 0; i < 10000; i++) {
 hashMapWithMaxSizeLimit.put(i, i + "");
 }
 });
 }

 @Test
 void givenCustomHashMapObject_whenLimitNotReached_thenDoesNotThrowException() {
 hashMapWithMaxSizeLimit = new HashMapWithMaxSizeLimit<Integer, String>(MAX_SIZE);
 assertDoesNotThrow(() -> {
 for (int i = 0; i < 4; i++) {
 hashMapWithMaxSizeLimit.put(i, i + "");
 }
 });
 }

 @Test
 void givenCustomHashMapObject_whenReplacingValueWhenLimitIsReached_thenDoesNotThrowException() {
 hashMapWithMaxSizeLimit = new HashMapWithMaxSizeLimit<Integer, String>(MAX_SIZE);
 assertDoesNotThrow(() -> {
 hashMapWithMaxSizeLimit.put(1, "One");
 hashMapWithMaxSizeLimit.put(2, "Two");
 hashMapWithMaxSizeLimit.put(3, "Three");
 hashMapWithMaxSizeLimit.put(4, "Four");
 hashMapWithMaxSizeLimit.put(4, "4");
 });
 }

 @Test
 void givenCustomHashMapObject_whenLimitExceeded_thenThrowsException() {
 hashMapWithMaxSizeLimit = new HashMapWithMaxSizeLimit<Integer, String>(MAX_SIZE);
 Exception exception = assertThrows(RuntimeException.class, () -> {
 for (int i = 0; i < 5; i++) {
 hashMapWithMaxSizeLimit.put(i, i + "");
 }
 });

 String messageThrownWhenSizeExceedsLimit = "Max size exceeded!";
 String actualMessage = exception.getMessage();
 assertTrue(actualMessage.equals(messageThrownWhenSizeExceedsLimit));
 }

在上面的程式碼中，我們有四個測試案例：

• 我們用預設的無限制行為實例化該類別。即使我們添加大量條目，我們也不希望出現任何異常。
• 我們用maxSize 4來實例化該類別。如果沒有達到限制，我們預計不會有任何例外。
• 我們用maxSize 4來實例化該類別。如果我們達到了限制並替換了一個值，我們預計不會出現任何異常。
• 我們用maxSize 4來實例化該類別。如果超出限制，我們預期會出現帶有特定訊息的RuntimeException 。

六，結論

在某些特定場景中，可能需要對HashMap的最大大小進行限制。在本文中，我們看到了一些滿足此要求的範例。

如果我們想快速實作 LRU 快取或類似的東西，擴展LinkedHashMap並重寫其removeEldestEntry()方法可能會很有用。如果我們想要強制執行更嚴格的限制，我們可以擴展HashMap並重寫其插入方法來滿足我們的需求。

與往常一樣，範例程式碼可在 GitHub 上取得。