Вы должны использовать java.awt.Dimension в качестве ключа.
Ключ измерения = новое измерение (4, 12);
Dimension имеет очень хороший метод hashCode (), который создает разные hashCode для каждой пары натуральных чисел, так что hashCodes для (4, 12) и (12, 4) различны. Таким образом, они быстро создаются и создают очень хорошие хэш-коды.
Хотелось бы, чтобы они сделали класс неизменным, но вы можете сделать свой собственный неизменный класс по образцу Dimension.
Вот таблица, показывающая hashCode для различных значений ширины и высоты:
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
Если вы будете следовать хеш-кодам в порядке от 0 до 14, вы увидите шаблон.
Вот код, который создает этот хэш-код:
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; }
}
Конечно, если вам, вероятно, понадобится метод equals, но вы ограничиваете себя целыми положительными числами, которые не переполняются, вы можете добавить очень быстрый:
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 (), которые могут быть написаны. (Конечно, вы можете написать hashCodes так же быстро в любом неизменяемом классе, вычислив 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, которые будут работать нормально. Этот метод генерирует хеш-ключ из двух коротких значений. Ограничение состоит в том, что ваши входные данные должны быть положительными короткими значениями. Это гарантированно не переполняет, и, приведя промежуточную сумму к длинной, она имеет более широкий диапазон, чем предыдущий метод: она работает со всеми положительными короткими значениями.
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;
}