2つの数字をマップキーとして使用する方法

Question

私は2つの数字を持っており、それらを一緒にキーとしてMapに使用したいと思います。現在、私は文字列表現を連結しています。例えば、キー番号は4と12は私が使用していると仮定します

String key = 4 + "," + 12; 

マップはMap<String, Object>として宣言されています。

これはとても悪いと思います！私は鍵としてString以外の何かを使用したい！私はこれらのキーを作成する最速の方法をしたい。

誰が良いアイデアを持っていますか？

Answer 1

2つの数値を保持するオブジェクトを作成し、キーとして使用します。たとえば、

class Coordinates { 

    private int x; 
    private int y; 

    public Coordinates(int x, int y) { 
    ... 
    } 

    // getters 

    // equals and hashcode using x and y 
} 

Map<Coordinates, Location> locations = new HashMap<Coordinates, Location>(); 

this StackOverflow answerを参照してください。

Answer 2

正しいeqaulsおよびhashcodeメソッドを記述するか、いくつかのバグを生成する必要があります。

Answer 3

public class Pair<L, R> { 

    private L l; 
    private R r; 

    public Pair() { 
    } 

    public Pair(L l, R r) { 
     this.l = l; 
     this.r = r; 
    } 

    public L getLeft() { 
     return l; 
    } 

    public R getRight() { 
     return r; 
    } 

    @Override 
    public boolean equals(Object o) { 
     if (!(o instanceof Pair)) { 
      return false; 
     } 
     Pair obj = (Pair) o; 
     return l.equals(obj.l) && r.equals(obj.r); 
    } 

    @Override 
    public int hashCode() { 
     return l.hashCode()^r.hashCode(); 
    } 
} 

Answer 4

オブジェクト溶液で行く場合は、があなたの鍵を確認してください、あなたは

long n = (l << 32) | (r & 0XFFFFFFFFL); 

、長い間このように2つの整数を格納することができますまたはあなたはPair<Integer, Integer>クラス次使用することができますオブジェクトは不変ですです。

誰かが値を変更すると、他の明らかに同一の値に等しくなるだけでなく、マップに格納されたハッシュコードがhashCode()メソッドによって返されたものと一致しなくなります。その時点であなたは基本的にSOLです。

public static void main(String[] args) { 
    Map<Point, Object> map = new HashMap<Point, Object>(); 

    Point key = new Point(1, 3); 
    Object val = new Object(); 

    map.put(key, val); 

    System.out.println(map.containsKey(key)); 
    System.out.println(map.containsKey(new Point(1, 3))); 

    // equivalent to setLeft()/setRight() in ZZCoder's solution, 
    // or setX()/setY() in SingleShot's 
    key.setLocation(2, 4); 

    System.out.println(map.containsKey(key)); 
    System.out.println(map.containsKey(new Point(2, 4))); 
    System.out.println(map.containsKey(new Point(1, 3))); 
    } 

プリント：

true 
true 
false 
false 
false 

Answer 5

別のアプローチは、になります - ルックス、紙の上、正確に何をしたいのように - 次java.awt.Pointを使用して例えば

、ネストマップを使用します。

Map<Integer,Map<Integer,Object>> 

ここでは、キーを作成するオーバーヘッドはありません。しかし、エントリを正しく作成して取得するためのオーバーヘッドが増え、探しているオブジェクトを見つけるために常にマップアクセスする必要があります。

Answer 6

シンプルな文字列を使用するよりも、何か他のもののために必要ではない完全なクラスを作成するために余分なコードをすべて書く必要があるのはなぜですか？そのクラスのインスタンスのハッシュコードの計算は、Stringよりもはるかに高速ですか？私はそうは思わない。

非常に限られたコンピューティングパワー環境で実行している場合を除き、文字列の作成とハッシュのオーバーヘッドは、カスタムクラスのインスタンス化のオーバーヘッドよりもはるかに大きくすべきではありません。

私は、ZZコーダが示唆しているように、単純にintを単一のLongにパックするのが最速の方法だと思っていますが、いずれの場合でもスピードの向上は期待できません。この質問へ

Answer 7

実用的な答えは：A、BとhashCodeはすべてint型です

hashCode = a + b * 17; 

...。 17はちょうど任意の素数です。あなたのハッシュはユニークではありませんが、それは問題ありません。そのようなことはJava標準ライブラリ全体で使用されています。

Answer 8

キーとしてjava.awt.Dimensionを使用する必要があります。

寸法キー=新しい寸法（4,12）;

Dimensionには、（4,12）と（12,4）のハッシュコードが異なるように、正の整数のペアごとに異なるhashCodeを生成する非常に優れたhashCode（）メソッドがあります。だから、これらのインスタンス化と非常に良いhashCodesを作るのは速いです。

私は彼らがクラスを不変にしてもらいたいと思いますが、Dimensionでモデル化した独自の不変クラスを作ることができます。あなたは0から14まで順にハッシュコードをたどる場合は、パターンを参照してくださいよ、

 0 1 2 3 4 <-- width 
    +-------------------- 
0 | 0 2 5 9 14 
1 | 1 4 8 13 
2 | 3 7 12 
3 | 6 11 
4 | 10 

^ 
| 
height 

：

はここで幅と高さの異なる値のハッシュコードを示す表です。ここで

は、このハッシュコードを生成したコードです：

public int hashCode() { 
    int sum = width + height; 
    return sum * (sum + 1)/2 + width; 
} 

あなたは最後の行の内側三角数の計算式を認識することができます。そのため、表の最初の列にはすべての三角形の数字が含まれています。

スピードを上げるには、コンストラクタでhashCodeを計算する必要があります。あなたはおそらくメソッドに等しい必要があります場合は、もちろん

public class PairHash { 
    private final int hash; 
    public PairHash(int a, int b) { 
    int sum = a+b; 
    hash = sum * (sum+1)/2 + a; 
    } 
    public int hashCode() { return hash; } 
} 

、しかし、あなたはありませんオーバーフロー、あなたは非常に高速なものを追加することができます正の整数に自分自身を制限します。だから、あなたの全クラスは次のようになります。

public class PairHash { 
    // PAIR_LIMIT is 23170 
    // Keeping the inputs below this level prevents overflow, and guarantees 
    // the hash will be unique for each pair of positive integers. This 
    // lets you use the hashCode in the equals method. 
    public static final int PAIR_LIMIT = (int) (Math.sqrt(Integer.MAX_VALUE))/2; 
    private final int hash; 

    public PairHash(int a, int b) { 
    assert a >= 0; 
    assert b >= 0; 
    assert a < PAIR_LIMIT; 
    assert b < PAIR_LIMIT; 
    int sum = a + b; 
    hash = sum * (sum + 1)/2 + a; 
    } 

    public int hashCode() { return hash; } 

    public boolean equals(Object other) { 
    if (other instanceof PairHash){ 
     return hash == ((PairHash) other).hash; 
    } 
    return false; 
    } 
} 

負の値はいくつかの重複したハッシュコードを生成するので、これを正の値に制限します。しかし、この制限があると、これらは最速のhashCode（）メソッドとequals（）メソッドで記述することができます。 （もちろん、コンストラクタでhashCodeを計算することで、不変クラスでhashCodeをできるだけ速く書くことができます）。

これらの制約を満たすことができない場合は、パラメータを保存するだけです。

public class PairHash { 
    private final int a, b, hash; 
    public PairHash(int a, int b) { 
    this.a = a; 
    this.b = b; 
    int sum = a+b; 
    hash = sum * (sum+1)/2 + a; 
    } 
    public int hashCode() { return hash; } 
    public boolean equals(Object other) { 
    if (other instanceof PairHash) { 
     PairHash otherPair = (PairHash)other; 
     return a == otherPair.a && b == otherPair.b; 
    } 
    return false; 
} 

しかし、ここではキッカーです。このクラスはまったく必要ありません。数式は数値の各ペアに固有の整数を与えるので、その整数をマップキーとして使用できます。 Integerクラスには、高速のequals（）メソッドとhashCodeメソッドがあり、正常に動作します。このメソッドは、2つの短い値からハッシュキーを生成します。制限は、入力が正の短い値である必要があることです。オーバーフローしないように保証されています。中間合計をlongにキャストすると、以前の方法よりも広い範囲が得られます。すべての正のshort値で機能します。

static int hashKeyFromPair(short a, short b) { 
    assert a >= 0; 
    assert b >= 0; 
    long sum = (long) a + (long) b; 
    return (int) (sum * (sum + 1)/2) + a; 
}