search
LoginSignup
7

More than 5 years have passed since last update.

posted at

updated at

HashMapのキーに配列を使う方法あれこれ

Mapのkeyを配列にするとうまいこといかないを見て、そりゃ動かないだろうなあと思いつつ、動くようにする方法あれこれ。
Java の Map で byte 配列をキーにするときの注意点をリンクしてあって、さらにUsing a byte array as Map keyにリンクがあり、最後のStack Overflowにいろいろ書いてあるんだが。

HashMapのキーの前提

ここではHashMapとする。TreeMapだと変わってくるはず。→TreeMapのキーに配列を使う方法あれこれ
キーとなる前提は、
- equalsを実装している
- hashCodeを実装している
- imuutableなインスタンスである

1番目と2番目は、HashMapのcontainsKey, get, putでバッチリ使っている。
3番目はimuutableでなくて後から変えられてもいいけど、putしたあとにキーの値を変えると見つからなくなる可能性がある。
これはABCでputしたあとにDEFに変えれば、ABCで見つからないのは当たり前だがDEFでも見つからなくなる可能性がある。
理由はhashCodeが変わってしまうけど、本来はDEFのhashCodeに相当する場所に入るものが、ABCのhashCodeに相当する場所に入ってしまっているため。

配列のequalsとhashCodeの結果

配列だとequalsとhashCodeは正しくない。

Main.java
    public static void main(String[] args) {
        byte[] b01 = { 1, 2, 3 };
        byte[] b02 = { 1, 2, 3 };
        int h01 = b01.hashCode();
        int h02 = b02.hashCode();
        System.out.println(b01 == b02);
        System.out.println(b01.equals(b02));
        System.out.println(h01 == h02);
        int h11 = Arrays.hashCode(b01);
        int h12 = Arrays.hashCode(b02);
        System.out.println(Arrays.equals(b01, b02));
        System.out.println(h11 == h12);
    }

結果は・・・

false
false
false
true
true

Arrays.equalsやArrays.hashCodeがわざわざある理由は、配列のequalsとhashCodeは正しくないため。

その1:ByteArrayWrapperを作る

byte[]をラップして、equalsとhashCodeを実装する方法。

ByteArrayWrapper.java
import java.util.Arrays;

public class ByteArrayWrapper {
    private byte[] data;

    public ByteArrayWrapper(byte[] data) {
        this.data = data;
    }

    public boolean equals(Object other) {
        if (other instanceof ByteArrayWrapper) {
            return Arrays.equals(data, ((ByteArrayWrapper) other).data);
        }
        return false;
    }

    public int hashCode() {
        return Arrays.hashCode(data);
    }
}

テストしてみる。

Main.java
    public static void main(String[] args) {
        byte[] b01 = { 1, 2, 3 };
        byte[] b02 = { 1, 2, 3 };
        ByteArrayWrapper w01 = new ByteArrayWrapper(b01);
        ByteArrayWrapper w02 = new ByteArrayWrapper(b02);
        Map<ByteArrayWrapper, String> map = new HashMap<>();
        map.put(w01, "OK");
        int h01 = w01.hashCode();
        int h02 = w02.hashCode();
        System.out.println(w01 == w02);
        System.out.println(w01.equals(w02));
        System.out.println(h01 == h02);
        System.out.println(map.get(w01));
        System.out.println(map.get(w02));
    }

結果は・・・

false
true
true
OK
OK

なかでArrays.equalsやArrays.hashCodeを呼んでいるんだから当たり前だよね。

修正版ByteArrayWrapper.java

(1/17追記)Stack Overflowから持ってきたら、ダメじゃんこれ。
配列をそのまま保持しているだけなので、コンストラクタに渡した配列を修正すると誤動作する。
せっかくなので試してみよう。

Main.java
    public static void main(String[] args) {
        byte[] b01 = { 1, 2, 3 };
        byte[] b02 = { 1, 2, 3 };
        byte[] b03 = { 9, 2, 3 };
        ByteArrayWrapper w01 = new ByteArrayWrapper(b01);
        ByteArrayWrapper w02 = new ByteArrayWrapper(b02);
        ByteArrayWrapper w03 = new ByteArrayWrapper(b03);
        Map<ByteArrayWrapper, String> map = new HashMap<>();
        map.put(w01, "OK");
        System.out.println(map.get(w01));
        b01[0] = 9;
        System.out.println(map.get(w01));
        System.out.println(map.get(w02));
        System.out.println(map.get(w03));
        System.out.println(map);
    }

実行すると・・・

OK
null
null
null
{ByteArrayWrapper@9669=OK}

データがマップに入っているけど、キーで取れなくなる。
防ぐにはコンストラクタで配列のコピーを取ればいい。

ByteArrayWrapper.java
import java.util.Arrays;

public class ByteArrayWrapper {
    private byte[] data;

    public ByteArrayWrapper(byte[] data) {
        this.data = data.clone();
    }

    public boolean equals(Object other) {
        if (other instanceof ByteArrayWrapper) {
            return Arrays.equals(data, ((ByteArrayWrapper) other).data);
        }
        return false;
    }

    public int hashCode() {
        return Arrays.hashCode(data);
    }
}

同じテストプログラムを動かすと・・・

OK
OK
OK
null
{ByteArrayWrapper@7861=OK}

中の配列が守られている。

その2:ByteBufferを使う

ラッパークラスを作らずに、java.nio.ByteBufferで行けるんじゃないとコメントがある。
テストしてみる。

Main.java
    public static void main(String[] args) {
        byte[] b01 = { 1, 2, 3 };
        byte[] b02 = { 1, 2, 3 };
        ByteBuffer w01 = ByteBuffer.wrap(b01);
        ByteBuffer w02 = ByteBuffer.wrap(b02);
        Map<ByteBuffer, String> map = new HashMap<>();
        map.put(w01, "OK");
        int h01 = w01.hashCode();
        int h02 = w02.hashCode();
        System.out.println(w01 == w02);
        System.out.println(w01.equals(w02));
        System.out.println(h01 == h02);
        System.out.println(map.get(w01));
        System.out.println(map.get(w02));
    }

結果は・・・

false
true
true
OK
OK

全然OK。これが一番よい感じ。JDK 1.4から追加された標準ライブラリというのがいいよね。

その3:BigIntegerを使う→ダメ

java.math.BigIntegerでもbyte[]をコンストラクタが受け取るから行けるんじゃないとコメントがある。
しかし、{ 0, 100 }のときに{ 100 }と一緒になっちゃうんじゃない?とコメント返しがある。
テストしてみる。

Main.java
    public static void main(String[] args) {
        byte[] b01 = { 0, 100 };
        byte[] b02 = { 0, 100 };
        byte[] b03 = { 100 };
        BigInteger w01 = new BigInteger(b01);
        BigInteger w02 = new BigInteger(b02);
        BigInteger w03 = new BigInteger(b03);
        Map<BigInteger, String> map = new HashMap<>();
        map.put(w01, "OK");
        int h01 = w01.hashCode();
        int h02 = w02.hashCode();
        int h03 = w03.hashCode();
        System.out.println(w01 == w02);
        System.out.println(w01 == w03);
        System.out.println(w01.equals(w02));
        System.out.println(w01.equals(w03));
        System.out.println(h01 == h02);
        System.out.println(h01 == h03);
        System.out.println(map.get(w01));
        System.out.println(map.get(w02));
        System.out.println(map.get(w03));
    }

結果は・・・

false
false
true
true
true
true
OK
OK
OK

残念でした。{ 0, 100 }と{ 100 }が一緒になっています。知らずに使ったらヤバイな。

その4:文字列にする→効率がよくない

String s01 = new String(b01, "UTF-8");なんてあったけど、文字化けしそう。
String s02 = Arrays.toString(b01);が正統だろうけど、出力される文字列は"[1, 2, 3]"となる。括弧とかブランクとか要らないんだけど。
そこで数値,数値,...と出力するユーティリティメソッドを作る。
数値を16進数にする。
数値を36進数にする。(Character.MAX_RADIX == 36)
base64エンコードする。

といろいろ考えられるけど、byte[]より確実にサイズが大きくなるので効率が悪いです。

最後に

ByteBufferでいいと思うけど、byte[]でなくてint[]で使いたい場合、IntBufferがあります。
というか、プリミティブ型のすべて用意されています。各種なんとかBuffer。知らんかった。

厳密にはimuutableではないけど、キーに指定してからputで追加したりしないでしょう。
(1/17追記)ByteBufferのjavadocとソースを見ると、get()でもダメです。カレントポジションが移動して、equalsやhashCodeがカレントポジション以降を対象とするためです。equalsやhashCodeはget(int)でアクセスしています。
ByteBuffer/hashCodeには、以下の注意書きが書いてあります。

バッファのハッシュ・コードは内容依存型です。今後バッファの内容が変更されないことが明らかでないかぎり、バッファをハッシュ・マップその他のデータ構造のキーとして使用することは避けてください。

でも外部に出してどう使われるか分からない場合は、ByteArrayWrapperを作った方が通常の方法では変更できないので安心です。
(1/17追記)すんません、最初に出したByteArrayWrapperはimuutableではなかったです。修正しました。

HashMapとTreeMapの両方で使えるByteArrayWrapper

(1/18追記)TreeMapの方の最後に載せたのですが、両方で使えるラッパーです。
HashMapにあるソースから修正した内容:コンストラクタの引数をbyte[]からbyte...に変更、equals(byte[] other)の追加、compareTo()の追加

ByteArrayWrapper.java
import java.util.Arrays;

public class ByteArrayWrapper implements Comparable<ByteArrayWrapper> {
    private byte[] data;

    public ByteArrayWrapper(byte... data) {
        this.data = data.clone();
    }

    public boolean equals(Object other) {
        if (other instanceof ByteArrayWrapper) {
            return equals(((ByteArrayWrapper) other).data);
        }
        return false;
    }

    public boolean equals(byte[] other) {
        return Arrays.equals(data, other);
    }

    public int hashCode() {
        return Arrays.hashCode(data);
    }

    public int compareTo(ByteArrayWrapper that) {
        int n = Math.min(this.data.length, that.data.length);
        for (int i = 0; i < n; i++) {
            int cmp = Byte.compare(this.data[i], that.data[i]);
            if (cmp != 0)
                return cmp;
        }
        return this.data.length - that.data.length;
    }
}

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
7