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

Question

Можем ли мы найти hashcode из 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. Можно ли таким образом найти код ha sh?

Answer 1

Код ha sh для соответствия List реализаций указан в интерфейсе :

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

 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().

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

Answer 2

Ознакомьтесь со скелетной реализацией метода 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 таким образом.

Answer 3

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

Почему существует StackOverflowError?

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

"Код ха sh списка определен как результат следующего вычисления:"

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

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

Можно ли таким образом найти код ha sh?

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

Answer 4

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

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

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

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

Answer 5

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

Можно ли таким образом найти код ha sh?

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

• , что код ha sh списка должен учитывать все его элементы
• все в порядке, если список является отдельным элементом

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

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

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

С ArrayList вторая точка неверна. Поэтому, если интервьюер имел в виду «Можно ли таким образом найти код ha sh (со списком массивов)?» , тогда ответ «нет», потому что это абсурд.

Answer 6

Потому что, когда вы вызываете одну и ту же функцию из одной и той же функции, это создает условие рекурсии, которое никогда не заканчивается. И для предотвращения этой операции 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);
    }

}