在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
()之間的契約
equals
和hashCode
方法都具有應遵守的約定。在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();
}
}
我們還需要實現自己的equals
和hashCode
方法。幸運的是,我們可以將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
數組作為鍵的不同問題和解決方案。首先,我們研究了為什麼不能使用數組作為鍵。然後,我們使用了一些內置容器來緩解該問題,最後實現了自己的包裝器。