Código hash de ArrayList que se contém como elemento

38

Podemos encontrar o hashcodede a listque se contém como element?

Sei que é uma prática ruim, mas foi o que o entrevistador perguntou.

Quando executei o seguinte código, ele lança um StackOverflowError:

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

Agora, aqui tenho duas perguntas:

  1. Por que existe um StackOverflowError?
  2. É possível encontrar o código hash dessa maneira?
Palhaço
fonte
7
Porque você adiciona a lista a si mesma. tente a.hashCode () sem a instrução add
Jens
Quando você coloca um objeto em uma lista de matrizes, está armazenando a referência ao objeto. No seu caso, você está colocando uma matriz ArrayList como referência.
Vishwa Ratna 7/01
Ok, eu entendi por que existe stackoverflow, alguém pode me ajudar a explicar o problema número 2 - Como encontrar isso
Joker
9
Como outros responderam, isso não é possível, pela própria definição da Listinterface, o hashCodede uma lista depende de seus membros. Dado que a lista é seu próprio membro, seu código de hash depende do seu hashCode, que depende do seu hashCode... e assim por diante, causando recursão infinita e o que StackOverflowErrorvocê está enfrentando. Agora, a pergunta é: por que você exige que uma lista se contenha? Posso garantir que você pode conseguir o que quer que esteja tentando fazer, de uma maneira melhor, sem a necessidade de associação recursiva como esta.
Alexander - Restabelecer Monica

Respostas:

36

O código de hash para Listimplementações em conformidade foi especificado na interface :

Retorna o valor do código de hash para esta lista. O código hash de uma lista é definido para ser o resultado do seguinte cálculo:

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

Isso garante que isso list1.equals(list2)implica list1.hashCode()==list2.hashCode()em duas listas list1e list2, conforme exigido pelo contrato geral de Object.hashCode().

Isso não exige que a implementação seja exatamente assim (consulte Como calcular o código de hash para um fluxo da mesma maneira que List.hashCode () para uma alternativa), mas o código de hash correto para uma lista que apenas se contenha um número para o qual x == 31 + xdeve ser true, em outras palavras, é impossível calcular um número em conformidade.

Holger
fonte
11
@ Holger, Eirc quer substituir o código de toda a função hashCode()para retornar 0. Este tecnicamente resolve x == 31 + x, mas ignora a exigência de que x deve ser pelo menos 1.
bxk21
4
@EricDuminil, o ponto da minha resposta é que o contrato descreve uma lógica que é ArrayListimplementada literalmente, levando a uma recursão, mas também não há implementação alternativa em conformidade. Observe que eu postei minha resposta em um momento em que o OP já entendia por que essa implementação específica leva a um StackOverflowError, que foi abordada em outras respostas. Então, concentrei-me na impossibilidade geral de uma implementação em conformidade ser concluída em tempo finito com um valor.
Holger
2
@pdem, não importa se a especificação usa uma descrição detalhada de um algoritmo, fórmula, pseudo-código ou código real. Como dito na resposta, o código fornecido na especificação não exclui implementações alternativas em geral. A forma da especificação não diz nada sobre se a análise ocorreu ou não. A sentença da documentação da interface “ Embora seja permitido que as listas se contenham como elementos, recomenda-se extrema cautela: os métodos equals e hashCode não estão mais bem definidos nessa lista ” sugere que essa análise ocorreu.
Holger
2
@pdem você está revertendo. Eu nunca disse que a lista tinha que ser igual por causa do código hash. As listas são iguais, por definição. Arrays.asList("foo")é igual a Collections.singletonList("foo"), é igual a List.of("foo")é igual a new ArrayList<>(List.of("foo")). Todas essas listas são iguais, ponto. Então, como essas listas são iguais, elas devem ter o mesmo código de hash. Não o contrário. Como eles devem ter o mesmo código de hash, ele deve estar bem definido. Independentemente de como eles o definiram (em Java 2), ele deve estar bem definido, para ser acordado por todas as implementações.
Holger
2
@pdem exatamente, uma implementação personalizada que não implementa Listou tem um grande sinal de aviso "não se misture com listas comuns", compare com IdentityHashMape com " Esta classe não é uma implementação de mapa de uso geral! " Atenção. No primeiro caso, você já está bem em implementar, Collectionmas também adicionando os métodos de acesso baseados em índices de estilo de lista. Portanto, não existe restrição de igualdade, mas ainda funciona sem problemas com outros tipos de coleção.
Holger
23

Confira a implementação esquelética do hashCodemétodo na AbstractListclasse.

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

Para cada elemento da lista, isso chama hashCode. No seu caso, a lista tem como elemento único. Agora essa ligação nunca termina. O método chama a si próprio recursivamente e a recursão continua girando até encontrar o StackOverflowError. Então você não pode encontrar hashCodedesta maneira.

Ravindra Ranwala
fonte
Portanto, a resposta é que não há como encontrar o código hash dessa maneira?
Joker
3
Sim, por causa da condição recursiva
springe 07/01
Não é só isso, é definido dessa maneira.
chrylis -on strike -
14

Você definiu uma lista (patológica) que se contém.

Por que existe StackOverflowError?

De acordo com os javadocs (ou seja, a especificação), o código de hash de a Listé definido como uma função do código de hash de cada um de seus elementos. Diz:

"O código de hash de uma lista é definido como o resultado do seguinte cálculo:"

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

Portanto, para calcular o hashcode de a, você primeiro calcula o hashcode de a. Isso é infinitamente recursivo e leva rapidamente a um estouro de pilha.

É possível encontrar o código hash dessa maneira?

Não. Se você considerar a especificação algorítmica acima em termos matemáticos, o código hash de a Listque se contém é uma função não computável . Não é possível computá-lo dessa maneira (usando o algoritmo acima) ou de qualquer outra maneira .

Stephen C
fonte
Não sei por que essa resposta é mais baixa que as outras duas, pois na verdade responde às perguntas do OP com explicações.
Neyt
11
@Nem alguns usuários leem apenas as respostas na parte superior.
Holger
8

Não, a documentação tem uma resposta

A documentação da estrutura da lista declara explicitamente:

Nota: Embora seja permitido que as listas se contenham como elementos, recomenda-se extrema cautela: os métodos equals e hashCode não estão mais bem definidos nessa lista.

Não há muito mais a dizer além disso - de acordo com a especificação Java, você não poderá calcular o hashCode para uma lista que se contenha; outras respostas entram em detalhes por que é assim, mas o ponto é que é conhecido e intencional.

Peter é
fonte
11
Você disse por que está fora da especificação, por isso explica que não é um bug. Essa foi a parte que faltava nas outras respostas.
pdem 8/01
3

A resposta de Ravindra dá uma boa explicação para o ponto 1. Para comentar a pergunta 2:

É possível encontrar o código hash dessa maneira?

Algo é circular aqui. Pelo menos um desses 2 deve estar errado no contexto desse erro de estouro de pilha:

  • que o código hash da lista deve levar em consideração os elementos
  • que não há problema em uma lista ser seu próprio elemento

Agora, porque estamos lidando com um ArrayList, o primeiro ponto é fixo. Em outras palavras, talvez você precise de uma implementação diferente para poder calcular significativamente um código de hash de uma lista recursiva ... Pode-se estender ArrayListe pular a adição dos códigos de hash dos elementos, algo como

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

Usando essa classe em vez de ArrayList, você poderia.

Com ArrayList, o segundo ponto está errado. Portanto, se o entrevistador quis dizer "É possível encontrar o código hash dessa maneira (com uma lista de matrizes)?" , então a resposta é não, porque isso é um absurdo.

ernest_k
fonte
11
O cálculo código hash é obrigatória pelo Listcontrato . Nenhuma implementação válida pode ignorar-se. A partir da especificação, você pode derivar que, se encontrar um intnúmero para o qual x == 31 + xé true, poderá implementar um atalho válido ...
Holger
Não entendi direito o que @Holger estava dizendo. Mas existem 2 problemas com a solução: Primeiro: Isso resolve o problema apenas quando esta lista é um item em si e não se a lista em que um item de um item é seu (camadas mais profundas de recursão). Segundo: Se a lista for ignorada, pode ser igual a uma lista vazia.
Jonas Michel
11
@JonasMichel Não propus uma solução. Estou apenas debatendo filosoficamente sobre o absurdo da pergunta 2. Se precisarmos calcular um código de hash para essa lista, ele não funcionará, a menos que removamos a restrição de uma lista de matrizes (e Holger reforça isso dizendo que Listformalmente dita a lógica do código hash a ser cumprida pelas implementações)
ernest_k 7/01
Meu entendimento (limitado) é que Listfornece um cálculo de código de hash, mas que podemos substituí-lo. O único requisito real é o de códigos hash gerais: se os objetos forem iguais, os códigos hash deverão ser iguais. Esta implementação segue esse requisito.
Teepeemm 7/01
11
@Teepeemm Listé uma interface. Ele define um contrato , não fornece uma implementação. Obviamente, o contrato abrange tanto a igualdade quanto o código de hash. Como o contrato geral de igualdade é que ele deve ser simétrico, se você alterar uma implementação de lista, você precisará alterar todas as implementações de lista existentes; caso contrário, você quebraria o contrato fundamental de java.lang.Object.
Holger
1

Porque quando você chama a mesma função com a mesma função, ela cria uma condição de recursão que nunca termina. E para impedir esta operação, o JAVA retornarájava.lang.StackOverflowError

Abaixo está um código de exemplo que explica o cenário semelhante:

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
fonte