Как правильно определить хеш-функцию для списка объектов?
У меня есть структура данных, содержащая список объектов, как это:
class A {
private List<Object> list;
}
Как правильно определить хеш-функцию для списка, предположив, что каждый элемент списка имеет корректное hashCode()?
4 ответа
Если фактическая реализация List полностью соответствует интерфейсу, предоставленной реализации hashCode должно быть достаточно:
Возвращает значение хэш-кода для этого списка. Хэш-код списка определяется как результат следующих вычислений:
hashCode = 1;
Iterator i = list.iterator();
while (i.hasNext()) {
Object obj = i.next();
hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
}
Интерфейс Список требует предоставления соответствующих реализаций равно на основе элементов списка. Таким образом, им пришлось явно указать алгоритм hashCode
Почему вы хотите определить hashCode для вашего списка, когда он уже реализовал (вместе с равно )?
(При условии, что это java.util.List , но если нет, то ссылка выше показывает вам точную реализацию, которую вы можете использовать для своего типа списка.)
Хэш-код списка определяется интерфейсом List List. Это можно использовать как часть хэш-кода вашего объекта, хотя есть несколько случаев, когда вы можете не захотеть его использовать - если элементы вашего списка имеют дорогостоящую функцию хеш-кода или если список может содержать ссылку на объект, и вы получите переполнение стека, если бы использовался алгоритм списка. В этом случае просто используйте длину списка или другое значение хеш-функции.
В библиотеке Java реализации List ( LinkedList , ArrayList ) используют реализацию по умолчанию hashCode , предоставленную AbstractList . который определяется как:
int hashCode = 1;
Iterator<E> i = iterator();
while (i.hasNext()) {
E obj = i.next();
hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
}
return hashCode;