在Java中使用字節數組作為hashmap鍵

    1.簡介

    在本教程中,我們將學習如何在HashMap使用字節數組作為鍵。由於HashMap工作方式,不幸的是,我們無法直接做到這一點。我們將調查為什麼會這樣,並探討解決該問題的幾種方法。

    2.為HashMap設計一個好的Key

    2.1。 HashMap如何工作

    HashMap使用散列機制從自身存儲和檢索值。當我們調用put(key, value)方法時, HashMap根據鍵的hashCode()方法計算哈希碼。此哈希用於標識最終將值存儲在其中的存儲桶:

    public V put(K key, V value) {
    
     if (key == null)
    
     return putForNullKey(value);
    
     int hash = hash(key.hashCode());
    
     int i = indexFor(hash, table.length);
    
     for (Entry e = table[i]; e != null; e = e.next) {
    
     Object k;
    
     if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    
     V oldValue = e.value;
    
     e.value = value;
    
     e.recordAccess(this);
    
     return oldValue;
    
     }
    
     }
    
    
    
     modCount++;
    
     addEntry(hash, key, value, i);
    
     return null;
    
     }

    當我們使用get(key)方法檢索值時,將涉及類似的過程。該密鑰用於計算哈希碼,然後找到存儲桶。然後,使用equals()方法檢查存儲桶中的每個條目是否相等。最後,返回匹配條目的值:

    public V get(Object key) {
    
     if (key == null)
    
     return getForNullKey();
    
     int hash = hash(key.hashCode());
    
     for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
    
     Object k;
    
     if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
    
     return e.value;
    
     }
    
     return null;
    
     }

    2.2。 equals ()和hashCode ()之間的契約

    equalshashCode方法都具有應遵守的約定。在HashMaps的上下文中,一方面特別重要:彼此相等的對象必須返回相同的hashCode 。但是,返回相同hashCode對像不必彼此相等。這就是為什麼我們可以將多個值存儲在一個存儲桶中的原因。

    2.3。不變性

    HashMap中的鍵的hashCode不應更改。儘管它不是強制性的,但強烈建議鍵是不可變的。如果對像是不可變的,則無論hashCode方法的實現如何,其hashCode都沒有機會進行更改。

    默認情況下,哈希是根據對象的所有字段計算的。如果我們想要一個可變鍵,則需要重寫hashCode方法,以確保在其計算中不使用可變字段。為了維持合同,我們還需要更改equals方法。

    2.4。有意義的equal

    為了能夠從地圖成功檢索值,相等性必須有意義。在大多數情況下,我們需要能夠創建一個新的鍵對象,該對象將等於地圖中的某些現有鍵。因此,對象標識在這種情況下不是很有用。

    這也是使用原始字節數組並不是真正的選擇的主要原因。 Java中的數組使用對象標識來確定相等性。如果我們使用字節數組作為鍵來創建HashMap ,我們將只能使用完全相同的數組對象來檢索值。

    讓我們創建一個簡單的實現,將字節數組作為鍵:

    byte[] key1 = {1, 2, 3};
    
     byte[] key2 = {1, 2, 3};
    
     Map<byte[], String> map = new HashMap<>();
    
     map.put(key1, "value1");
    
     map.put(key2, "value2");

    我們不僅有兩個條目具有幾乎相同的鍵,而且我們不能使用新創建的具有相同值的數組來檢索任何內容:

    String retrievedValue1 = map.get(key1);
    
     String retrievedValue2 = map.get(key2);
    
     String retrievedValue3 = map.get(new byte[]{1, 2, 3});
    
    
    
     assertThat(retrievedValue1).isEqualTo("value1");
    
     assertThat(retrievedValue2).isEqualTo("value2");
    
     assertThat(retrievedValue3).isNull();

    3.使用現有容器

    代替字節數組,我們可以使用現有的類,其相等性實現是基於內容而不是對象標識的。

    3.1。 String

    String相等性基於字符數組的內容:

    public boolean equals(Object anObject) {
    
     if (this == anObject) {
    
     return true;
    
     }
    
     if (anObject instanceof String) {
    
     String anotherString = (String)anObject;
    
     int n = count;
    
     if (n == anotherString.count) {
    
     char v1[] = value;
    
     char v2[] = anotherString.value;
    
     int i = offset;
    
     int j = anotherString.offset;
    
     while (n-- != 0) {
    
     if (v1[i++] != v2[j++])
    
     return false;
    
     }
    
     return true;
    
     }
    
     }
    
     return false;
    
     }

    String也是不可變的,並且基於字節數組創建String非常簡單。我們可以使用Base64方案輕鬆地對String進行編碼和解碼:

    String key1 = Base64.getEncoder().encodeToString(new byte[]{1, 2, 3});
    
     String key2 = Base64.getEncoder().encodeToString(new byte[]{1, 2, 3});

    現在,我們可以創建一個以String為鍵而不是字節數組的HashMap 。我們將以類似於上一個示例的方式將值放入Map中:

    Map<String, String> map = new HashMap<>();
    
     map.put(key1, "value1");
    
     map.put(key2, "value2");

    然後,我們可以從地圖中檢索一個值。對於這兩個鍵,我們將獲得相同的第二個值。我們還可以檢查兩個鍵是否真正相等:

    String retrievedValue1 = map.get(key1);
    
     String retrievedValue2 = map.get(key2);
    
    
    
     assertThat(key1).isEqualTo(key2);
    
     assertThat(retrievedValue1).isEqualTo("value2");
    
     assertThat(retrievedValue2).isEqualTo("value2");

    3.2。Lists

    String相似, List#equals方法將檢查其每個元素的相等性。如果這些元素具有明智的equals()方法並且是不可變的,則List將作為HashMap鍵正確工作。我們只需要確保我們使用的是不可變的List實現

    List<Byte> key1 = ImmutableList.of((byte)1, (byte)2, (byte)3);
    
     List<Byte> key2 = ImmutableList.of((byte)1, (byte)2, (byte)3);
    
     Map<List<Byte>, String> map = new HashMap<>();
    
     map.put(key1, "value1");
    
     map.put(key2, "value2");
    
    
    
     assertThat(map.get(key1)).isEqualTo(map.get(key2));

    請注意, Byte對象List將比byte基元數組佔用更多的內存。因此,該解決方案雖然方便,但在大多數情況下並不可行。

    4.實施自定義容器

    我們還可以實現自己的包裝器,以完全控制哈希碼的計算和相等性。這樣,我們可以確保解決方案是快速的,並且不會佔用大量內存。

    讓我們創建一個帶有最後一個私有byte數組字段的類。它沒有二傳手,它的getter會進行防禦性複制以確保完全不變:

    public final class BytesKey {
    
     private final byte[] array;
    
    
    
     public BytesKey(byte[] array) {
    
     this.array = array;
    
     }
    
    
    
     public byte[] getArray() {
    
     return array.clone();
    
     }
    
     }

    我們還需要實現自己的equalshashCode方法。幸運的是,我們可以將Arrays實用程序類用於以下兩個任務:

    @Override
    
     public boolean equals(Object o) {
    
     if (this == o) return true;
    
     if (o == null || getClass() != o.getClass()) return false;
    
     BytesKey bytesKey = (BytesKey) o;
    
     return Arrays.equals(array, bytesKey.array);
    
     }
    
    
    
     @Override
    
     public int hashCode() {
    
     return Arrays.hashCode(array);
    
     }

    最後,我們可以將包裝器用作HashMap的鍵:

    BytesKey key1 = new BytesKey(new byte[]{1, 2, 3});
    
     BytesKey key2 = new BytesKey(new byte[]{1, 2, 3});
    
     Map<BytesKey, String> map = new HashMap<>();
    
     map.put(key1, "value1");
    
     map.put(key2, "value2");

    然後,我們可以使用已聲明的鍵之一檢索第二個值,也可以使用動態創建的鍵:

    String retrievedValue1 = map.get(key1);
    
     String retrievedValue2 = map.get(key2);
    
     String retrievedValue3 = map.get(new BytesKey(new byte[]{1, 2, 3}));
    
    
    
     assertThat(retrievedValue1).isEqualTo("value2");
    
     assertThat(retrievedValue2).isEqualTo("value2");
    
     assertThat(retrievedValue3).isEqualTo("value2");

    5.結論

    在本教程中,我們研究了在HashMap使用byte數組作為鍵的不同問題和解決方案。首先,我們研究了為什麼不能使用數組作為鍵。然後,我們使用了一些內置容器來緩解該問題,最後實現了自己的包裝器。