Javaでのマップキーとしてのバイト配列の使用

投稿日: 2022-10-26 2022-10-26
タグ: Java Collections, Java Map

1. 序章

このチュートリアルでは、HashMapでバイト配列をキーとして使用する方法を学習します。 HashMap がどのように機能するかにより、残念ながら、それを直接行うことはできません。その理由を調査し、その問題を解決するためのいくつかの方法を検討します。

2. HashMapの適切なキーの設計

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 のコンテキストでは、1つの側面が特に重要です。互いに等しいオブジェクトは、同じhashCodeを返す必要があります。ただし、同じ hashCode を返すオブジェクトは、互いに等しい必要はありません。そのため、1つのバケットに複数の値を格納できます。

2.3. 不変性

HashMapのキーのhashCodeは変更しないでください。必須ではありませんが、キーを不変にすることを強くお勧めします。オブジェクトが不変である場合、 hashCode メソッドの実装に関係なく、そのhashCodeは変更される機会がありません。

デフォルトでは、ハッシュはオブジェクトのすべてのフィールドに基づいて計算されます。可変キーが必要な場合は、 hashCode メソッドをオーバーライドして、可変フィールドがその計算で使用されないようにする必要があります。契約を維持するには、equalsメソッドも変更する必要があります。

2.4. 意味のある平等

マップから値を正常に取得できるようにするには、等式に意味がある必要があります。ほとんどの場合、マップ内の既存のキーと同じになる新しいキーオブジェクトを作成できる必要があります。そのため、このコンテキストではオブジェクトIDはあまり役に立ちません。

これは、プリミティブバイト配列を使用することが実際にはオプションではない主な理由でもあります。 Javaの配列は、オブジェクトIDを使用して同等性を判断します。バイト配列をキーとして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");

実質的に同じキーを持つ2つのエントリがあるだけでなく、同じ値で新しく作成された配列を使用して何も取得できません。

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. 既存のコンテナの使用

バイト配列の代わりに、同等性の実装がオブジェクトIDではなくコンテンツに基づいている既存のクラスを使用できます。

3.1. 文字列

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");

次に、マップから値を取得できます。両方のキーについて、同じ2番目の値を取得します。キーが本当に互いに等しいことを確認することもできます。

String retrievedValue1 = map.get(key1);
String retrievedValue2 = map.get(key2);

assertThat(key1).isEqualTo(key2);
assertThat(retrievedValue1).isEqualTo("value2");
assertThat(retrievedValue2).isEqualTo("value2");

3.2. リスト

String と同様に、 List＃equalsメソッドは各要素が等しいかどうかをチェックします。これらの要素に適切なequals（）メソッドがあり、不変である場合、ListはHashMapキーとして正しく機能します。 不変のリスト実装を使用していることを確認する必要があるだけです：

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. カスタムコンテナの実装

独自のラッパーを実装して、ハッシュコードの計算と同等性を完全に制御することもできます。 こうすることで、ソリューションが高速で、メモリフットプリントが大きくないことを確認できます。

最後の1つのプライベートbyte配列フィールドを持つクラスを作成しましょう。セッターはなく、ゲッターは完全な不変性を確保するために防御コピーを作成します。

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");

次に、宣言されたキーのいずれかを使用して2番目の値を取得するか、オンザフライで作成したキーを使用できます。

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. 結論

このチュートリアルでは、byte配列をHashMapのキーとして使用するためのさまざまな問題と解決策について説明しました。まず、配列をキーとして使用できない理由を調査しました。次に、いくつかの組み込みコンテナを使用してその問題を軽減し、最後に独自のラッパーを実装しました。

いつものように、このチュートリアルのソースコードはGitHubのにあります。

getdocs

13036