Обновление
Скажем, например, в случае, когда у нас будет массив, который мы хотим рассматривать как мультимножество.
Таким образом, вы должны обработать все записи по мере их поступления, вы не можете использовать count и не можете предполагать, что записи приходят в известном порядке.
Общая функция, которую я бы рассмотрел:
int hashCode() {
int x = INITIAL_VALUE;
for (Object o : this) {
x = f(x, o==null ? NULL_HASH : g(o.hashCode()));
}
return h(x);
}
Некоторые наблюдения:
- Как уже говорилось в других ответах, INITIAL_VALUE не имеет большого значения.
- Я бы не стал использовать
NULL_HASH=0, поскольку это игнорировало бы нулевые значения.
- Функция
g может использоваться, если вы ожидаете, что хэши элементов находятся в небольшом диапазоне (что может произойти, если они, например, одиночные символы).
- Функция
h может быть использована для улучшения результата, что не очень важно, поскольку это уже происходит, например, в HashMap.hash(int).
- Функция
f является наиболее важной, к сожалению, она весьма ограничена, поскольку она, очевидно, должна быть как ассоциативной, так и коммутативной.
- Функция
f должна быть биективной в обоих аргументах, в противном случае вы получите ненужные коллизии.
Ни в коем случае я бы не порекомендовал f(x, y) = x^y, так как он сделал бы два вхождения элемента для отмены. Использование сложения лучше. Что-то вроде
f(x, y) = x + (2*A*x + 1) * y
, где A - константа, удовлетворяющая всем вышеуказанным условиям. Это может стоить того.
Для A=0 оно вырождается в сложение, использование четного A не годится, поскольку оно сдвигает биты x*y.
Использование A=1 хорошо, и выражение 2*x+1 может быть вычислено с использованием одной инструкции в архитектуре x86.
Использование большего нечетного A может работать лучше, если хэши членов распределены неправильно.
Если вы выберете нетривиальный hashCode(), вам следует проверить, работает ли он правильно. Вы должны измерить производительность вашей программы, может быть, вы найдете достаточно простого дополнения. Иначе я бы за NULL_HASH=1, g=h=identity и A=1.
Мой старый ответ
Это может быть из соображений эффективности. Вызов count может быть дорогостоящим для некоторых реализаций, но вместо него можно использовать entrySet. Тем не менее, это может быть дороже, я не могу сказать.
Я сделал простой тест на столкновение для хэш-кода Гуавы, Ринке и моих собственных предложений:
enum HashCodeMethod {
GUAVA {
@Override
public int hashCode(Multiset<?> multiset) {
return multiset.hashCode();
}
},
RINKE {
@Override
public int hashCode(Multiset<?> multiset) {
int result = 0;
for (final Object o : multiset.elementSet()) {
result += (o==null ? 0 : o.hashCode()) * multiset.count(o);
}
return result;
}
},
MAAARTIN {
@Override
public int hashCode(Multiset<?> multiset) {
int result = 0;
for (final Multiset.Entry<?> e : multiset.entrySet()) {
result += (e.getElement()==null ? 0 : e.getElement().hashCode()) * (2*e.getCount()+123);
}
return result;
}
}
;
public abstract int hashCode(Multiset<?> multiset);
}
Код подсчета столкновений выглядит следующим образом:
private void countCollisions() throws Exception {
final String letters1 = "abcdefgh";
final String letters2 = "ABCDEFGH";
final int total = letters1.length() * letters2.length();
for (final HashCodeMethod hcm : HashCodeMethod.values()) {
final Multiset<Integer> histogram = HashMultiset.create();
for (final String s1 : Splitter.fixedLength(1).split(letters1)) {
for (final String s2 : Splitter.fixedLength(1).split(letters2)) {
histogram.add(hcm.hashCode(ImmutableMultiset.of(s1, s2, s2)));
}
}
System.out.println("Collisions " + hcm + ": " + (total-histogram.elementSet().size()));
}
}
и напечатано
Collisions GUAVA: 45
Collisions RINKE: 42
Collisions MAAARTIN: 0
Так что в этом простом примере hashCode Guava работал очень плохо (45 коллизий из 63 возможных). Однако я не утверждаю, что мой пример имеет большое значение для реальной жизни.