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

Question

[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 будет в цикле проходить по элементам списков, в то время как хеш возьмётся быстрее.

Answer 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 без потерь и рассинхронизаций демо-роликов. Сначала находил множества потенциально равных блоков, потом вёл глубокое сравнение.

Comments

[mayton2019]

я так сжимал WAD’ы для Doom без потерь

Старичок... :)

[Mercury13]

mayton2019, Мне 41.

[mayton2019]

Кстати обрати внимание на hashCode. Возможно у нас разные версии JDK

public int hashCode() {
        int expectedModCount = modCount;
        int hash = hashCodeRange(0, size);
        checkForComodification(expectedModCount);
        return hash;
    }

[Mercury13]

mayton2019, Тут уже наладили многопоточный расчёт и сделали какую-то защиту от межпоточных гонок, но в целом одно и то же.

[Mercury13]

…даже не защиту, а тупую детекцию межпоточных гонок!

Answer 2

[jcmvbkbc]

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

Если хеши получились разными то со 100% уверенностью можно сказать, что списки разные. Если хеши получились одинаковыми, то с высокой (в зависимости от качества хеширующей функции, но однозначно не 100%) степенью уверенности можно сказать, что списки одинаковые. 100% уверенность в равенстве списков с одинаковыми хешами даёт только поэлементное сравнение списков.

Comments

[anya_hacker]

Безусловно, коллизию никто не отменял, спасибо за ответ!

Answer 3

[mayton2019]

Насколько я вижу хешкод нигде не хранится для 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. Это будет правильный ответ на собеседовании.

Answer 4

[Василий Банников]

Значит, если будет стоять задача сравнить два списка (одинаковы ли они), то достаточно вычислить хеш двух списков?

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

в то время как хеш возьмётся быстрее.

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