Java: por que as coleções aceitam um comparador, mas não (um hipotético) Hasher e Equator?

25

Esse problema é mais aparente quando você tem implementações diferentes de uma interface e, para os propósitos de uma coleção específica, você se preocupa apenas com a exibição dos objetos no nível da interface. Por exemplo, suponha que você tenha uma interface como esta:

public interface Person {
    int getId();
}

A maneira usual de implementar hashcode()e equals()implementar classes teria código como este no equalsmétodo:

if (getClass() != other.getClass()) {
    return false;
}

Isso causa problemas quando você combina implementações de Personem a HashMap. Se o HashMapúnico se importar com a visualização no nível da interface Person, poderá acabar com duplicatas que diferem apenas nas classes de implementação.

Você pode fazer esse caso funcionar usando o mesmo equals()método liberal para todas as implementações, mas corre o risco de equals()fazer a coisa errada em um contexto diferente (como comparar dois Persons suportados por registros de banco de dados com números de versão).

Minha intuição me diz que igualdade deve ser definida por coleção em vez de por classe. Ao usar coleções que dependem de pedidos, você pode usar um costume Comparatorpara escolher a ordem certa em cada contexto. Não há análogo para coleções baseadas em hash. Por que é isso?

Apenas para esclarecer, essa pergunta é distinta de " Por que .compareTo () está em uma interface, enquanto .equals () está em uma classe em Java? ", Porque lida com a implementação de coleções. compareTo()e equals()/ hashcode()ambos sofrem com o problema da universalidade ao usar coleções: você não pode escolher diferentes funções de comparação para coleções diferentes. Portanto, para os propósitos desta pergunta, a hierarquia de herança de um objeto não importa; o que importa é se a função de comparação é definida por objeto ou por coleção.

Sam
fonte
5
Você sempre pode introduzir objetos wrapper para Personimplementar o esperado equalse o hashCodecomportamento. Você então teria um HashMap<PersonWrapper, V>. Este é um exemplo em que uma abordagem de POO puro não é elegante: nem toda operação em um objeto faz sentido como método desse objeto. O Objecttipo inteiro de Java é um amálgama de responsabilidades diferentes - apenas os métodos getClass, finalizee toStringparecem remotamente justificáveis ​​pelas melhores práticas de hoje.
amon
1
1) No C #, você pode passar um IEqualityComparer<T>para uma coleção baseada em hash. Se você não especificar um, ele usará uma implementação padrão baseada em Object.Equalse Object.GetHashCode(). 2) A substituição da IMO Equalsem um tipo de referência mutável raramente é uma boa idéia. Dessa forma, a igualdade padrão é bastante rigorosa, mas você pode usar uma regra de igualdade mais relaxada quando precisar através de um costume IEqualityComparer<T>.
CodesInChaos
2
Meta-pergunta relacionada: essas perguntas são duplicadas?

Respostas:

23

Este projeto é conhecido como "Igualdade Universal", é a crença de que se duas coisas são iguais ou não, é uma propriedade universal.

Além disso, a igualdade é uma propriedade de dois objetos, mas no OO, você sempre chama um método em um único objeto , e esse objeto decide apenas como lidar com essa chamada de método. Portanto, em um design como o de Java, em que igualdade é uma propriedade de um dos dois objetos que estão sendo comparados, não é possível garantir algumas propriedades básicas de igualdade, como simetria ( a == bb == a), porque, no primeiro caso, o método está sendo chamado ae, no segundo caso, be devido aos princípios básicos da OO, é auma decisão exclusiva (no primeiro caso) oubdecisão (no segundo caso) se considera ou não igual ao outro. A única maneira de obter simetria é cooperar com os dois objetos, mas se não o fizerem ... azar.

Uma solução seria fazer da igualdade não uma propriedade de um objeto, mas uma propriedade de dois objetos ou uma propriedade de um terceiro objeto. Essa última opção também resolve o problema da igualdade universal, porque se você tornar a igualdade uma propriedade de um terceiro objeto de "contexto", poderá imaginar ter EqualityComparerobjetos diferentes para contextos diferentes.

Esse é o design escolhido para Haskell, por exemplo, com a Eqclasse de tipo. Também é o design escolhido por algumas bibliotecas Scala de terceiros (ScalaZ, por exemplo), mas não a biblioteca principal ou padrão do Scala, que usa igualdade universal para compatibilidade com a plataforma host subjacente.

É, curiosamente, também o design escolhido com as interfaces Comparable/ Java Comparator. Os projetistas de Java estavam claramente cientes do problema, mas por algum motivo o resolveram apenas por pedidos, mas não por igualdade (ou hash).

Então, quanto à questão

por que existe uma Comparatorinterface, mas não Hashere Equator?

a resposta é "eu não sei". Claramente, os projetistas de Java estavam cientes do problema, como evidenciado pela existência de Comparator, mas obviamente não consideravam um problema de igualdade e hash. Outras linguagens e bibliotecas fazem escolhas diferentes.

Jörg W Mittag
fonte
7
+1, mas observe que existem idiomas OO nos quais existem vários despachos (Smalltalk, Common Lisp). Portanto, sempre é muito forte na seguinte frase: "no OO, você sempre chama um método em um único objeto".
Coredump
Encontrei a citação que estava procurando; de acordo com o JLS 1.0, The methods equals and hashCode are declared for the benefit of hashtables such as java.util.Hashtableou seja, ambos equalse hashCodeforam introduzidos como Objectmétodos pelos desenvolvedores Java apenas por uma questão de Hashtable- não há noção de UE nem nada de silimar em nenhum lugar da especificação, e a citação é clara o suficiente para mim; se não fosse o Hashtable, equalsprovavelmente teria sido em uma interface como Comparable. Como tal, embora eu acreditasse anteriormente que sua resposta estava correta, agora a considero sem fundamento.
vaxquis
@ JörgWMittag foi um erro de digitação, IFTFY. BTW, falando sobre clone- era originalmente um operador , não um método (consulte Oak Language Specification), citação: The unary operator clone is applied to an object. (...) The clone operator is normally used inside new to clone the prototype of some class, before applying the initializers (constructors)- os três operadores semelhantes a palavras-chave eram instanceof new clone(seção 8.1, operadores). Suponho que essa é a verdadeira razão (histórica) da bagunça clone/ Cloneable- Cloneablefoi simplesmente uma invenção posterior, e o clonecódigo existente foi adaptado a ela.
vaxquis
2
"Esse é o design escolhido para Haskell, por exemplo, com a classe Eq". Isso é verdade, mas vale a pena notar que Haskell afirma explicitamente de antemão que dois objetos de tipos diferentes nunca são iguais, enquanto a abordagem de Java não. A operação de igualdade faz parte do tipo (portanto, "typeclass") não faz parte de um terceiro valor de contexto.
Jack
19

A verdadeira resposta para

por que existe uma Comparatorinterface, mas não Hashere Equator?

é, citação cortesia de Josh Bloch :

As APIs Java originais foram feitas muito rapidamente, dentro de um prazo apertado, para atender a uma janela de fechamento do mercado. A equipe original do Java fez um trabalho incrível, mas nem todas as APIs são perfeitas.

O problema reside unicamente na história do Java, como com outros assuntos semelhantes, por exemplo, .clone()vs Cloneable.

tl; dr

é principalmente por razões históricas; o comportamento / abstração atual foi introduzido no JDK 1.0 e não foi corrigido posteriormente porque era praticamente impossível fazê-lo com a manutenção da compatibilidade com o código anterior.


Primeiro, vamos resumir alguns fatos Java conhecidos:

  1. O Java, desde o início até os dias atuais, era orgulhosamente compatível com versões anteriores, exigindo que as APIs herdadas ainda fossem suportadas nas versões mais recentes,
  2. como tal, quase todos os construtos de idiomas introduzidos no JDK 1.0 sobreviveram até os dias atuais,
  3. Hashtable, .hashCode()& .equals()foram implementados no JDK 1.0, ( Hashtable )
  4. Comparable/ Comparatorfoi introduzido no JDK 1.2 ( comparável ),

Agora, segue:

  1. era praticamente impossível e sem sentido adaptar .hashCode()e .equals()interfaces distintas, mantendo a compatibilidade com versões anteriores, depois que as pessoas perceberam que há abstrações melhores do que colocá-las em superobjetos, porque, por exemplo, todo e qualquer programador Java da 1.2 sabia que cada Objectum deles os possuía, e eles tinham ficar lá fisicamente para fornecer compatibilidade com código compilado (JVM) também - e adicionar uma interface explícita a todas as Objectsubclasses que realmente as implementaram tornaria essa bagunça igual (sic!) a Clonableuma ( Bloch discute por que Cloneable é péssimo , também discutido em, por exemplo, EJ 2nd e muitos outros lugares, incluindo SO),
  2. eles apenas os deixaram lá para a geração futura ter uma fonte constante de WTFs.

Agora, você pode perguntar "o que Hashtabletem tudo isso"?

A resposta é: hashCode()/ equals()contrato e habilidades de design de linguagem não tão boas dos principais desenvolvedores de Java em 1995/1996.

Citação de Java 1.0 Language Spec, datado de 1996 - 4.3.2 The Class Object, p.41:

Os métodos equalse hashCodesão declarados para o benefício de hashtables, como java.util.Hashtable(§21.7). O método equals define uma noção de igualdade de objeto, que se baseia na comparação de valor, não de referência.

(note que essa declaração exata foi alterado em versões posteriores, quer dizer, a citar: The method hashCode is very useful, together with the method equals, in hashtables such as java.util.HashMap., tornando-se impossível fazer a direta Hashtable- hashCode- equalsconexão sem ler JLS históricos!)

A equipe Java decidiu que queria uma boa coleção no estilo de dicionário e criou Hashtable(boa ideia até agora), mas queria que o programador fosse capaz de usá-la com o mínimo de curva de código / aprendizado possível (opa! Problemas ao receber!) - e, como ainda não havia genéricos [afinal de contas, é o JDK 1.0], isso significaria que todos os Object envolvidos Hashtableteriam que implementar explicitamente alguma interface (e as interfaces ainda estavam no seu início naquela época ... Comparableainda nem!) , tornando isso um impedimento para usá-lo para muitos - ou Objectteria que implementar implicitamente algum método de hash.

Obviamente, eles foram com a solução 2, pelas razões descritas acima. Sim, agora sabemos que eles estavam errados. ... é fácil ser inteligente em retrospectiva. rir

Agora, hashCode() exige que todo objeto que o possua tenha um equals()método distinto - portanto, era óbvio que equals()ele também deveria ser colocado Object.

Desde as padrão implementações destes métodos sobre válida a& b Objects são essencialmente inútil por ser redundante (tornando a.equals(b) igual a a==be a.hashCode() == b.hashCode() aproximadamente igual a a==btambém, a menos que hashCodee / ou equalsé anulado, ou você GC centenas de milhares de Objects durante o ciclo de vida de sua aplicação 1 ) , é seguro dizer que eles foram fornecidos principalmente como medida de backup e por conveniência de uso. É exatamente assim que chegamos ao fato conhecido de que sempre substitui os dois .equals()e .hashCode()se você pretende realmente comparar os objetos ou armazená-los com hash. Substituir apenas um deles sem o outro é uma boa maneira de estragar o seu código (comparando resultados incorretos ou valores de colisão de balde insanamente altos) - e contornar isso é uma fonte de confusão e erros constantes para iniciantes (pesquise SO para ver para você) e incômodo constante para os mais experientes.

Além disso, observe que, embora o C # lide com iguais e hashcode de uma maneira um pouco melhor, o próprio Eric Lippert afirma que eles cometeram quase o mesmo erro com o C # que a Sun com o Java anos antes do início do C # :

Mas por que deveria ser o caso de todo objeto ser capaz de fazer um hash próprio para inserção em uma tabela de hash? Parece uma coisa estranha exigir que todos os objetos possam fazer. Acho que se estivéssemos redesenhando o sistema de tipos do zero hoje, o hash pode ser feito de maneira diferente, talvez com uma IHashableinterface. Porém, quando o sistema de tipos CLR foi projetado, não havia tipos genéricos e, portanto, uma tabela de hash de uso geral precisava ser capaz de armazenar qualquer objeto.

1 , é claro, Object#hashCodeainda pode colidir, mas é preciso um pouco de esforço para fazer isso, consulte: http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6809470 e relatórios de erros vinculados para obter detalhes; /programming/1381060/hashcode-uniqueness/1381114#1381114 aborda esse assunto mais detalhadamente.

vaxquis
fonte
Não é apenas Java, no entanto. Muitos de seus contemporâneos (Ruby, Python, ...) e predecessores (Smalltalk, ...) e alguns de seus sucessores também têm Igualdade Universal e Hasabilidade Universal (isso é uma palavra?).
Jörg W Mittag
@ JörgWMittag veja programmers.stackexchange.com/questions/283194/… - Eu tenho que discordar sobre "UE" em Java; Historicamente, o UE nunca foi uma preocupação real no Objectdesign; hashability era.
vaxquis
@ vaxquis Eu não quero discutir isso, mas meu comentário anterior mostra que dois objetos alcançáveis ​​simultaneamente podem ter o mesmo código de hash (padrão).
Reponha Monica
1
@vaxquis OK. Eu compro isso. Minha preocupação é que alguém que esteja aprendendo veja isso e pense que é inteligente usando o código de hash do sistema em vez de iguais etc. Se o fizerem, provavelmente funcionará bem, exceto nos raros momentos em que não ocorrer e nenhuma maneira de reproduzir o problema de maneira confiável.
precisa saber é o seguinte
1
Esta deve ser a resposta aceita, desde a conclusão do resposta aceita é "eu não sei"
Phoenix