Jak używać dwóch liczb jako klucza mapy

Question

Mam dwa numery i chcę je używać razem jako klucza w Map. Obecnie łączę ich reprezentacje ciągów. Na przykład, załóżmy, że kluczowe są numery 4 i 12. Używam:

String key = 4 + "," + 12; 

Mapa jest zadeklarowany jako Map<String, Object>.

Myślę, że to jest takie złe! Lubię używać czegoś innego niż String jako klucza! Chcę najszybszego sposobu na utworzenie tych kluczy.

Kto ma dobry pomysł?

Answer 1

Utwórz obiekt, który zawiera dwie liczby i użyj go jako klucza. Na przykład:

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

Jeśli wolisz matematyczne podejście, zobacz this StackOverflow answer.

Answer 2

Musisz napisać odpowiednie metody eqauls i hashcode lub wygenerować kilka błędów.

Answer 3

można zapisać dwie liczby całkowite w długi tak,

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

Albo można użyć następujących Pair<Integer, Integer> klasie

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

Jeśli pójdziesz z roztworem obiektu, upewnić się, że klucz obiekt jest niezmienny.

W przeciwnym razie, jeśli ktoś zmutuje wartość, nie tylko nie będzie już równy innym pozornie identycznym wartościom, ale kod skrótu zapisany na mapie nie będzie już odpowiadać metodzie zwróconej przez metodę hashCode(). W tym momencie jesteś w zasadzie SOL.

Na przykład, używając java.awt.Point - co wygląd, na papierze, jak dokładnie to, co chcesz - następujący:

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

drukuje:

true 
true 
false 
false 
false 

Answer 5

Innym rozwiązaniem byłoby użyj zagnieżdżonych map:

Map<Integer,Map<Integer,Object>> 

Tutaj nie ma narzutu na tworzenie kluczy. Jednak masz więcej narzutów, aby poprawnie tworzyć i pobierać wpisy, i zawsze potrzebujesz dostępu do map, aby znaleźć poszukiwany obiekt.

Answer 6

Dlaczego napisanie całego tego dodatkowego kodu, aby uczynić pełną klasę, której nie potrzebujesz do niczego innego, byłoby lepsze niż użycie prostego ciągu? Czy obliczenie kodu skrótu dla wystąpień tej klasy będzie dużo szybsze niż w przypadku String? Nie sądzę.

O ile nie używasz bardzo ograniczonego środowiska obliczeniowego, obciążenie związane z tworzeniem i mieszaniem łańcuchów nie powinno być zauważalnie większe niż tworzenie instancji klasy użytkownika.

Myślę, że najszybszym sposobem byłoby po prostu spakować ints do pojedynczego tak długiego, jak sugerował ZZ Coder, ale w każdym razie nie oczekuję, że wzrost prędkości będzie znaczny.

Answer 7

Praktyczna odpowiedź na to pytanie brzmi:

hashCode = a + b * 17; 

... gdzie a, b i hashCode są ints. 17 to tylko arbitralna liczba pierwsza. Twój hasz nie będzie unikalny, ale to jest w porządku. Tego rodzaju rzeczy są używane w całej standardowej bibliotece Java.

Answer 8

Powinieneś użyć java.awt.Dimension jako klucza.

Klucz wymiarowy = nowy wymiar (4, 12);

Wymiar ma bardzo ładną metodę hashCode(), która generuje inny kod skrótu dla każdej pary liczb całkowitych dodatnich, tak aby kody mieszające dla (4, 12) i (12, 4) były różne. Tak więc są one szybkie do tworzenia instancji i tworzenia bardzo dobrych kodów hash.

Żałuję, że nie uczyniły klasy niezmienną, ale możesz stworzyć własną niezmienną klasę wzorowaną na Wymiarach.

Oto tabelę hashCode dla różnych wartości szerokości i wysokości:

 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 

Jeśli zastosujemy hashCodes w kolejności od 0 do 14, zobaczysz wzór.

Oto kod, który wywołuje tę hashCode:

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

Można rozpoznać wzór na liczbę trójkątną wewnątrz ostatniej linii. Dlatego pierwsza kolumna tabeli zawiera wszystkie liczby trójkątne.

Aby uzyskać prędkość, należy obliczyć kod haszowania w konstruktorze. Więc cała klasa może wyglądać następująco:

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; } 
} 

Oczywiście, jeśli będzie potrzebne równości metodę, ale ograniczyć się do liczb całkowitych dodatnich, które nie przepełnienia, można dodać bardzo szybko jeden:

Ograniczamy to do wartości dodatnich, ponieważ wartości ujemne spowodują pojawienie się zduplikowanych kodów skrótu. Ale z tym ograniczeniem, są to najszybsze metody hashCode() i equals(), które można zapisać. (Oczywiście, możesz napisać hashCodes równie szybko w każdej niezmiennej klasie, obliczając kod haszujący w konstruktorze.)

Jeśli nie możesz żyć z tymi ograniczeniami, po prostu zapisz parametry.

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; 
} 

Ale tutaj jest kopacz. W ogóle nie potrzebujesz tej klasy. Ponieważ formuła daje unikalną liczbę całkowitą dla każdej pary liczb, możesz po prostu użyć tej liczby całkowitej jako klucza mapy. Klasa Integer ma własne metody szybkiego equals() i hashCode, które będą działały poprawnie. Ta metoda wygeneruje skrót z dwóch krótkich wartości. Ograniczeniem jest to, że twoje dane wejściowe muszą być dodatnimi krótkimi wartościami. Gwarantuje to, że nie będzie przepełnienia, a odlewanie sumy pośredniej na długą, ma szerszy zakres niż poprzednia metoda: Działa ze wszystkimi dodatnimi krótkimi wartościami.

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; 
}