@anya_hacker

Как сравнить два списка с помощью хеш-кода?

Есть два списка с одинаковым содержимым:
List<Integer> ar1 = new ArrayList<>();
ar1.add(1);
ar1.add(2);
ar1.add(3);
ar1.add(4);
ar1.add(4);

List<Integer> ar2 = new ArrayList<>();
ar2.add(1);
ar2.add(2);
ar2.add(3);
ar2.add(4);
ar2.add(4);

Их хеш-коды одинаковые:
System.out.println(ar1.hashCode()); // 29615265
System.out.println(ar2.hashCode()); // 29615265
System.out.println(ar1.equals(ar2)); // true

Значит, если будет стоять задача сравнить два списка (одинаковы ли они), то достаточно вычислить хеш двух списков? Или просто так совпало, что их хеши одинаковые?
Списки лежат в разной области памяти, (два объекта ar1 и ar2) но содержимое и размер у них одинаковый.
При этом equals будет в цикле проходить по элементам списков, в то время как хеш возьмётся быстрее.
  • Вопрос задан
  • 281 просмотр
Решения вопроса 1
@Mercury13
Программист на «си с крестами» и не только
1. Реализация из Java8:
public int hashCode() {
    int hashCode = 1;
    for (E e : this)
        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
    return hashCode;
}

Из неё видно, что не совпало — у одинаковых списков хэши одинаковые. Но вспомни комбинаторику: если хэши одинаковы, объекты, СКОРЕЕ ВСЕГО, одинаковые, и один хрен нужно глубокое сравнение. Если разные — точно разные.

2. Если просто сравнить два списка — сравнивай обычным equals, ничего ты не выиграешь от хэшей. Один хрен для вычисления хэша придётся пройти по всем данным. Хэши используй, если нужно сравнить, например, 100 объектов попарно — я так сжимал WAD’ы для Doom без потерь и рассинхронизаций демо-роликов. Сначала находил множества потенциально равных блоков, потом вёл глубокое сравнение.
Ответ написан
Пригласить эксперта
Ответы на вопрос 3
jcmvbkbc
@jcmvbkbc
"I'm here to consult you" © Dogbert
Значит, если будет стоять задача сравнить два списка (одинаковы ли они), то достаточно вычислить хеш двух списков? Или просто так совпало, что их хеши одинаковые?

Если хеши получились разными то со 100% уверенностью можно сказать, что списки разные. Если хеши получились одинаковыми, то с высокой (в зависимости от качества хеширующей функции, но однозначно не 100%) степенью уверенности можно сказать, что списки одинаковые. 100% уверенность в равенстве списков с одинаковыми хешами даёт только поэлементное сравнение списков.
Ответ написан
mayton2019
@mayton2019 Куратор тега Java
Bigdata Engineer
Насколько я вижу хешкод нигде не хранится для ArrayList а расчитывается каждый раз. Поэтому твоя попытка срезать на повороте - скорее всего неудачна.

int hashCodeRange(int from, int to) {
        final Object[] es = elementData;
        if (to > es.length) {
            throw new ConcurrentModificationException();
        }
        int hashCode = 1;
        for (int i = from; i < to; i++) {
            Object e = es[i];
            hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
        }
        return hashCode;
    }


Используй метод equals. Это будет правильный ответ на собеседовании.
Ответ написан
Комментировать
Значит, если будет стоять задача сравнить два списка (одинаковы ли они), то достаточно вычислить хеш двух списков?

Нет. Хэши могут быть одинаковыми просто из-за коллизий. Так что если у тебя совпал hashcode - тебе следует ещё и содержимое на равенство проверить.
Если хэшкод не совпал - тогда они точно разные.
в то время как хеш возьмётся быстрее.

Разве для вычисления хэша не нужно точно также пройтись по всем элементам?
Или хэш кэшируется при добавлении новых элементов в список?
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы