Можем ли мы найти hashcode
a, list
который содержит себя как element
?
Я знаю, что это плохая практика, но это то, что спросил интервьюер.
Когда я запустил следующий код, он выдает StackOverflowError
:
public class Main {
public static void main(String args[]) {
ArrayList<ArrayList> a = new ArrayList();
a.add(a);
a.hashCode();
}
}
Теперь у меня есть два вопроса:
- Почему есть
StackOverflowError
? - Можно ли найти хеш-код таким образом?
java
java-8
stack-overflow
hashcode
джокер
источник
источник
List
интерфейсаhashCode
список зависит от его членов. Учитывая, что список является его собственным членом, его хеш-код зависит от егоhashCode
, который зависит от егоhashCode
... и так далее, вызывая бесконечную рекурсию и то, сStackOverflowError
чем вы сталкиваетесь. Теперь вопрос: почему вы требуете, чтобы список содержал себя? Я могу гарантировать вам, что вы можете достичь того, что вы пытаетесь сделать, лучшим способом, не требуя рекурсивного членства, подобного этому.Ответы:
Хеш-код для соответствующих
List
реализаций был указан в интерфейсе :Для этого не требуется, чтобы реализация выглядела именно так (см. Как вычислить хеш-код для потока таким же образом, как List.hashCode () для альтернативы), но правильный хеш-код для списка, содержащего только себя, будет быть числом, для которого
x == 31 + x
должно бытьtrue
, другими словами, невозможно вычислить соответствующее число.источник
hashCode()
для возврата0
. Это технически решает,x == 31 + x
но игнорирует требование, что х должно быть не меньше 1.ArrayList
реализуется буквально, что приводит к рекурсии, но нет и соответствующей альтернативной реализации. Обратите внимание, что я опубликовал свой ответ в то время, когда ФП уже понял, почему эта конкретная реализация приводит к aStackOverflowError
, о чем говорилось в других ответах. Таким образом, я сосредоточился на общей невозможности соответствующей реализации, завершившейся за конечное время со значением.Arrays.asList("foo")
равноCollections.singletonList("foo")
, равноList.of("foo")
равноnew ArrayList<>(List.of("foo"))
. Все эти списки равны, точка. Затем, поскольку эти списки равны, они должны иметь одинаковый хэш-код. Не наоборот. Поскольку они должны иметь одинаковый хэш-код, он должен быть четко определен. Независимо от того, как они его определили (обратно в Java 2), он должен быть четко определен, чтобы быть согласованным всеми реализациями.List
либо имеет большой предупреждающий знак «не смешивать с обычными списками», сравните соIdentityHashMap
своим « Этот класс не является реализацией Map общего назначения! Предупреждение В первом случае вы уже в порядке с реализацией,Collection
но также добавляете методы доступа, основанные на индексе стиля списка. Тогда не существует никакого ограничения равенства, но оно все еще работает гладко с другими типами коллекций.Проверьте скелетную реализацию
hashCode
метода вAbstractList
классе.Для каждого элемента в списке это вызывает
hashCode
. В вашем случае список имеет себя как единственный элемент. Теперь этот звонок никогда не заканчивается. Метод вызывает себя рекурсивно, и рекурсия продолжает вращаться, пока не встретитStackOverflowError
. Таким образом, вы не можете найтиhashCode
этот путь.источник
Вы определили (патологический) список, который содержит себя.
Согласно javadocs (то есть спецификации), хеш -код a
List
определяется функцией хеш-кода каждого из его элементов. Это говорит:Итак, чтобы вычислить хеш-код
a
, вы сначала вычисляете хеш-кодa
. Это бесконечно рекурсивно и быстро приводит к переполнению стека.Нет. Если вы рассмотрите приведенную выше алгоритмическую спецификацию в математических терминах, хеш-код
List
, содержащий себя, является невычислимой функцией . Невозможно вычислить это таким образом (используя вышеупомянутый алгоритм) или любым другим способом .источник
Нет, в документации есть ответ
В документации структуры List прямо говорится:
Больше сказать нечего - согласно спецификации Java, вы не сможете рассчитать hashCode для списка, который содержит сам себя; другие ответы подробно объясняют, почему это так, но дело в том, что это известно и намеренно.
источник
Ответ Равиндры дает хорошее объяснение для пункта 1. Чтобы прокомментировать вопрос 2:
Здесь что-то круглое. По крайней мере, один из этих 2 должен быть неправильным в контексте этой ошибки переполнения стека:
Теперь, поскольку мы имеем дело с
ArrayList
, первая точка исправлена. Другими словами, может быть, вам нужна другая реализация, чтобы иметь возможность осмысленно вычислять хеш-код рекурсивного списка ... Можно расширитьArrayList
и пропустить добавление хеш-кодов элементов, что-то вродеИспользуя такой класс вместо
ArrayList
, вы могли бы.Со
ArrayList
вторым пунктом это неправильно. Так что, если интервьюер имел в виду «Можно ли таким образом найти хэш-код (с помощью списка массивов)?» тогда ответ - нет, потому что это абсурд.источник
List
контракте . Никакая действительная реализация не может пропустить себя. Из спецификации можно вывести, что если вы найдетеint
число, для которогоx == 31 + x
естьtrue
, то вы можете реализовать действительный сокращенный ...List
формально диктует логика хеш-кода, которую должны соблюдать реализации)List
обеспечивает вычисление хеш-кода, но мы можем переопределить его. Единственным реальным требованием является требование общих хеш-кодов: если объекты равны, то хеш-коды должны быть равны. Эта реализация следует этому требованию.List
- это интерфейс. Он определяет контракт , он не обеспечивает реализацию. Конечно, контракт охватывает как равенство, так и хеш-код. Поскольку общий контракт равенства состоит в том, что он должен быть симметричным, если вы измените одну реализацию списка, вам придется изменить все существующие реализации списка, в противном случае вы даже нарушите фундаментальный контрактjava.lang.Object
.Потому что, когда вы вызываете одну и ту же функцию из одной и той же функции, это создает условие рекурсии, которое никогда не заканчивается. И чтобы предотвратить эту операцию, JAVA вернется
java.lang.StackOverflowError
Ниже приведен пример кода, который объясняет похожий сценарий:
источник