Хеш-код ArrayList, который содержит себя как элемент

38

Можем ли мы найти hashcodea, listкоторый содержит себя как element?

Я знаю, что это плохая практика, но это то, что спросил интервьюер.

Когда я запустил следующий код, он выдает StackOverflowError:

public class Main {
    public static void main(String args[]) {
        ArrayList<ArrayList> a = new ArrayList();
        a.add(a);
        a.hashCode();
    }
}

Теперь у меня есть два вопроса:

  1. Почему есть StackOverflowError?
  2. Можно ли найти хеш-код таким образом?
джокер
источник
7
Потому что вы добавляете список в себя. попробуйте a.hashCode () без оператора add
Йенс
Когда вы помещаете объект в arraylist, вы сохраняете ссылку на объект. В вашем случае вы помещаете ArrayList ведьма сама по себе ссылка.
Вишва Ратна
Аналогично: stackoverflow.com/questions/42566559/…
Вишва Ратна
Хорошо, я понял, почему существует переполнение стека, может кто-нибудь помочь мне объяснить проблему № 2 - Как это найти
Джокер
9
Как ответили другие, это невозможно, по самому определению Listинтерфейса hashCodeсписок зависит от его членов. Учитывая, что список является его собственным членом, его хеш-код зависит от его hashCode, который зависит от его hashCode... и так далее, вызывая бесконечную рекурсию и то, с StackOverflowErrorчем вы сталкиваетесь. Теперь вопрос: почему вы требуете, чтобы список содержал себя? Я могу гарантировать вам, что вы можете достичь того, что вы пытаетесь сделать, лучшим способом, не требуя рекурсивного членства, подобного этому.
Александр - Восстановить Монику

Ответы:

36

Хеш-код для соответствующих Listреализаций был указан в интерфейсе :

Возвращает значение хеш-кода для этого списка. Хеш-код списка определяется как результат следующих вычислений:

 int hashCode = 1;
 for (E e : list)
     hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());

Это гарантирует, что list1.equals(list2)подразумевается, что list1.hashCode()==list2.hashCode()для любых двух списков, list1и list2, как того требует общий договор Object.hashCode().

Для этого не требуется, чтобы реализация выглядела именно так (см. Как вычислить хеш-код для потока таким же образом, как List.hashCode () для альтернативы), но правильный хеш-код для списка, содержащего только себя, будет быть числом, для которого x == 31 + xдолжно быть true, другими словами, невозможно вычислить соответствующее число.

Holger
источник
1
@Holger, Eirc хочет заменить код всей функции hashCode()для возврата 0. Это технически решает, x == 31 + xно игнорирует требование, что х должно быть не меньше 1.
bxk21
4
@EricDuminil Суть моего ответа в том, что контракт описывает логику, которая ArrayListреализуется буквально, что приводит к рекурсии, но нет и соответствующей альтернативной реализации. Обратите внимание, что я опубликовал свой ответ в то время, когда ФП уже понял, почему эта конкретная реализация приводит к a StackOverflowError, о чем говорилось в других ответах. Таким образом, я сосредоточился на общей невозможности соответствующей реализации, завершившейся за конечное время со значением.
Хольгер
2
@pdem не имеет значения, использует ли спецификация многословное описание алгоритма, формулы, псевдокода или фактического кода. Как сказано в ответе, приведенный в спецификации код не исключает альтернативных реализаций в целом. Форма спецификации ничего не говорит о том, проводился анализ или нет. Предложение документации интерфейса « Хотя списки могут содержать себя в качестве элементов, рекомендуется соблюдать крайнюю осторожность: методы equals и hashCode более не определены в таком списке », что указывает на то, что такой анализ действительно имел место.
Хольгер
2
@pdem ты меняешь это. Я никогда не говорил, что список должен быть равен из-за хеш-кода. Перечни являются равными, по определению. Arrays.asList("foo")равно Collections.singletonList("foo"), равно List.of("foo")равно new ArrayList<>(List.of("foo")). Все эти списки равны, точка. Затем, поскольку эти списки равны, они должны иметь одинаковый хэш-код. Не наоборот. Поскольку они должны иметь одинаковый хэш-код, он должен быть четко определен. Независимо от того, как они его определили (обратно в Java 2), он должен быть четко определен, чтобы быть согласованным всеми реализациями.
Хольгер
2
@pdem, точнее, пользовательская реализация, которая либо не реализует, Listлибо имеет большой предупреждающий знак «не смешивать с обычными списками», сравните со IdentityHashMapсвоим « Этот класс не является реализацией Map общего назначения! Предупреждение В первом случае вы уже в порядке с реализацией, Collectionно также добавляете методы доступа, основанные на индексе стиля списка. Тогда не существует никакого ограничения равенства, но оно все еще работает гладко с другими типами коллекций.
Хольгер
23

Проверьте скелетную реализацию hashCodeметода в AbstractListклассе.

public int hashCode() {
    int hashCode = 1;
    for (E e : this)
        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
    return hashCode;
}

Для каждого элемента в списке это вызывает hashCode. В вашем случае список имеет себя как единственный элемент. Теперь этот звонок никогда не заканчивается. Метод вызывает себя рекурсивно, и рекурсия продолжает вращаться, пока не встретит StackOverflowError. Таким образом, вы не можете найти hashCodeэтот путь.

Равиндра Ранвала
источник
Таким образом, ответ: нет способа найти хэш-код таким образом?
Джокер
3
Да, из-за рекурсивного состояния
Спринге
Мало того, это определено таким образом.
Хрилис - по забастовке -
14

Вы определили (патологический) список, который содержит себя.

Почему есть StackOverflowError?

Согласно javadocs (то есть спецификации), хеш -код a Listопределяется функцией хеш-кода каждого из его элементов. Это говорит:

«Хеш-код списка определяется как результат следующего вычисления:»

int hashCode = 1;
    for (E e : list)
         hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());

Итак, чтобы вычислить хеш-код a, вы сначала вычисляете хеш-код a. Это бесконечно рекурсивно и быстро приводит к переполнению стека.

Можно ли таким образом найти хеш-код?

Нет. Если вы рассмотрите приведенную выше алгоритмическую спецификацию в математических терминах, хеш-код List, содержащий себя, является невычислимой функцией . Невозможно вычислить это таким образом (используя вышеупомянутый алгоритм) или любым другим способом .

Стивен С
источник
Я не знаю, почему этот ответ ниже, чем два других, поскольку он на самом деле отвечает на вопросы ОП с объяснениями.
Нейт
1
@ Не некоторые пользователи читают только ответы вверху.
Хольгер
8

Нет, в документации есть ответ

В документации структуры List прямо говорится:

Примечание. Хотя списки могут содержать себя в качестве элементов, рекомендуется соблюдать крайнюю осторожность: методы equals и hashCode более не определены в таком списке.

Больше сказать нечего - согласно спецификации Java, вы не сможете рассчитать hashCode для списка, который содержит сам себя; другие ответы подробно объясняют, почему это так, но дело в том, что это известно и намеренно.

Петерис
источник
1
Вы сказали, почему это не в спецификации, поэтому это объясняет, что это не ошибка. Этой части не хватало в других ответах.
pdem
3

Ответ Равиндры дает хорошее объяснение для пункта 1. Чтобы прокомментировать вопрос 2:

Можно ли таким образом найти хеш-код?

Здесь что-то круглое. По крайней мере, один из этих 2 должен быть неправильным в контексте этой ошибки переполнения стека:

  • что хеш-код списка должен принимать во внимание те его элементы
  • что для списка нормально быть своим собственным элементом

Теперь, поскольку мы имеем дело с ArrayList, первая точка исправлена. Другими словами, может быть, вам нужна другая реализация, чтобы иметь возможность осмысленно вычислять хеш-код рекурсивного списка ... Можно расширить ArrayListи пропустить добавление хеш-кодов элементов, что-то вроде

for (E e : this)
  if(e == this) continue; //contrived rules
  hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());

Используя такой класс вместо ArrayList, вы могли бы.

Со ArrayListвторым пунктом это неправильно. Так что, если интервьюер имел в виду «Можно ли таким образом найти хэш-код (с помощью списка массивов)?» тогда ответ - нет, потому что это абсурд.

ernest_k
источник
1
Расчет хэш - код уполномочена в Listконтракте . Никакая действительная реализация не может пропустить себя. Из спецификации можно вывести, что если вы найдете intчисло, для которого x == 31 + xесть true, то вы можете реализовать действительный сокращенный ...
Хольгер
Я не совсем понял, что говорит @Holger. Но есть 2 проблемы с решением: во-первых: это решает проблему только тогда, когда этот список является элементом самого себя, а не в том случае, если список, в котором находится элемент самого себя (более глубокие слои рекурсии), во-вторых: если список пропустил сам себя может быть равен пустому списку.
Джонас Мишель
1
@JonasMichel Я не совсем предложил решение. Я просто философски обсуждаю абсурдность вопроса 2. Если мы должны вычислить хеш-код для такого списка, то он не будет работать, если мы не удалим ограничение списка массивов (а Хольгер усиливает это, говоря, что Listформально диктует логика хеш-кода, которую должны соблюдать реализации)
ernest_k
Мое (ограниченное) понимание состоит в том, что он Listобеспечивает вычисление хеш-кода, но мы можем переопределить его. Единственным реальным требованием является требование общих хеш-кодов: если объекты равны, то хеш-коды должны быть равны. Эта реализация следует этому требованию.
Teepeemm
1
@Teepeemm List- это интерфейс. Он определяет контракт , он не обеспечивает реализацию. Конечно, контракт охватывает как равенство, так и хеш-код. Поскольку общий контракт равенства состоит в том, что он должен быть симметричным, если вы измените одну реализацию списка, вам придется изменить все существующие реализации списка, в противном случае вы даже нарушите фундаментальный контракт java.lang.Object.
Хольгер
1

Потому что, когда вы вызываете одну и ту же функцию из одной и той же функции, это создает условие рекурсии, которое никогда не заканчивается. И чтобы предотвратить эту операцию, JAVA вернетсяjava.lang.StackOverflowError

Ниже приведен пример кода, который объясняет похожий сценарий:

public class RefTest {

    public static void main(String... strings) {
        RefTest rf = new RefTest();
        rf.message(message("test"));
    }

    public static String message2(String s){
        return message(s);
    }

    public static String message(String s){
        return message2(s);
    }

}   
Simmant
источник