Como usar dois números como uma chave Mapa
https://stackoverflow.com/questions/1430822
-
07-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu tenho dois números e quero usá-los juntos, como uma chave em um Map. Atualmente, estou concatenando as suas representações de seqüência. Por exemplo, suponha que os números principais são 4 e 12. uso I:
String key = 4 + "," + 12;
O mapa é declarado como Map<String, Object>.
Eu acho que isso é tão ruim! Eu gosto de usar algo diferente de um String como a chave! Eu quero o caminho mais rápido para criar essas chaves.
Quem tem uma boa idéia?
Solução
Criar um objeto que contém os dois números e usá-lo como a chave. Por exemplo:
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>();
Se você prefere uma abordagem matemática, consulte esta resposta StackOverflow .
Outras dicas
Você deve usar java.awt.Dimension como sua chave.
= Dimensão chave nova dimensão (4, 12);
Dimensão tem um método muito bom hashCode () que produz um hashCode diferente para cada par de números inteiros positivos, pelo que os hashcodes para (4, 12) e (12, 4) serem diferentes. Então, essas são rápidos para instanciar e fazer muito bons hashcodes.
Gostaria que tinha feito a imutável classe, mas você pode fazer sua própria classe imutável modelado em Dimension.
Aqui está uma tabela mostrando a hashCode para diferentes valores de largura e altura:
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
Se você seguir as hashcodes a fim de 0 a 14, você vai ver o padrão.
Aqui está o código que produz essa hashCode:
public int hashCode() {
int sum = width + height;
return sum * (sum + 1)/2 + width;
}
Você pode reconhecer a fórmula para o número triangular dentro da última linha. É por isso que a primeira coluna da tabela contém todos os números triangulares.
Para a velocidade, você deve calcular o hashCode no construtor. Assim, toda a sua classe poderia ser assim:
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; }
}
Claro que, se você provavelmente vai precisar de um método é igual, mas você se limitar a números inteiros positivos que não excesso, você pode adicionar um muito rápido um:
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;
}
}
Nós restringimos isso para valores positivos porque os valores negativos irão produzir alguns códigos de hash duplicados. Mas com esta restrição no lugar, estes são os hashCode mais rápido () e equals () métodos que podem ser escritas. (Claro, você pode escrever hashcodes tão rápido em qualquer classe imutável através do cálculo da hashCode no construtor.)
Se você não pode viver com essas restrições, você só precisa salvar os parâmetros.
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;
}
Mas aqui está o kicker. Você não precisa esta classe em tudo. Desde que a fórmula dá-lhe um número inteiro único para cada par de números, você pode apenas usar esse inteiro como seu chave do mapa. A classe Integer tem seus próprios iguais rápido () e métodos hashCode que irá funcionar bem. Este método irá gerar a chave da mistura a partir de dois valores curtos. A restrição é que as entradas precisam ser curtos valores positivos. Esta é a garantia de não excesso, e lançando a soma intermediária para um longo, ele tem um alcance mais amplo do que o método anterior:. Ele funciona com todos os valores curtos positivos
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;
}
Se você vai com a solução objeto, verifique se o objeto-chave é imutável .
Caso contrário, se transforma alguém o valor, não só já não ser igual a outros valores aparentemente idênticos, mas o hashcode armazenado no mapa não irá corresponder a um retornado pelo método hashCode(). Nesse ponto você está basicamente SOL.
Por exemplo, usando java.awt.Point - que aparência, em papel, como exatamente o que você quer - se o seguinte:
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)));
}
impressões:
true
true
false
false
false
Você pode armazenar dois números inteiros em uma longa como esta,
long n = (l << 32) | (r & 0XFFFFFFFFL);
Ou você pode usar seguinte classe Pair<Integer, Integer>,
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();
}
}
A resposta prática a esta pergunta é:
hashCode = a + b * 17;
... onde a, b e hashCode são todos inteiros. 17 é apenas um número primo arbitrária. Seu hash não será exclusivo, mas isso é OK. Esse tipo de coisa é utilizado em todo a biblioteca padrão Java.
Outra abordagem seria a utilização de mapas aninhados:
Map<Integer,Map<Integer,Object>>
Aqui você tem nenhuma sobrecarga para criar chaves. No entanto, você tem mais sobrecarga para criar e recuperar entradas corretamente e você precisa sempre para mapear-acessos para encontrar o objeto que você está procurando.
Por que escrever todo esse código extra para fazer uma classe soprado completo que você não precisa de qualquer outra coisa seria melhor do que usar uma seqüência simples? Irá calcular o código hash para instâncias dessa classe ser muito mais rápido do que para a cadeia? Acho que não.
A menos que você estiver executando em um ambiente de poder de computação extremamente limitada, a sobrecarga de fazer e hashing Cordas não deve ser visivelmente maior do que a de instanciar a classe personalizada.
Eu acho que a maneira mais rápida seria a de simplesmente embalar os ints em um único longa como ZZ Coder sugerido, mas em qualquer caso, eu não espero que os ganhos de velocidade a ser substancial.
Você precisa escrever os iguais certas e métodos hashCode, ou produzir alguns erros.
