Por que não permitir uma interface externa para fornecer hashCode / iguais para um HashMap?

StackOverflow https://stackoverflow.com/questions/214136

Pergunta

Com um TreeMap é trivial para fornecer uma Comparator costume, substituindo, assim, a semântica fornecidos pelo Comparable objetos adicionados ao mapa. HashMaps no entanto não pode ser controlada desta maneira; as funções que fornecem os valores de hash e controlos de igualdade não pode ser 'lado-carregada'.

Eu suspeito que seria fácil e útil para projetar uma interface e para adaptar isso em HashMap (ou uma nova classe)? Algo parecido com isto, a não ser com melhores nomes: 

  interface Hasharator<T> {
    int alternativeHashCode(T t);
    boolean alternativeEquals(T t1, T t2);
  }

  class HasharatorMap<K, V> {
    HasharatorMap(Hasharator<? super K> hasharator) { ... }
  }

  class HasharatorSet<T> {
    HasharatorSet(Hasharator<? super T> hasharator) { ... }
  }

O maiúsculas e minúsculas problema Map recebe uma solução trivial: 

 new HasharatorMap(String.CASE_INSENSITIVE_EQUALITY);

Será que isso é factível, ou você pode ver todos os problemas fundamentais com esta abordagem?

É a abordagem usada em qualquer (não-JRE) libs existentes? (Google tentou, sem sorte.)

EDIT: Nice solução alternativa apresentada pelo hazzen, mas tenho medo esta é a solução que eu estou tentando evitar ...;)

EDIT: Mudou título para mais nenhuma menção "Comparador"; Eu suspeito que este foi um pouco confuso.

EDIT: resposta aceita com relação ao desempenho; adoraria uma resposta mais específica!

EDIT: Há uma implementação; ver a resposta aceite abaixo.

EDIT:. Reformulada a primeira frase para indicar mais claramente que é o lado-loading que eu estou atrás (e não ordenar; ordenação não pertence a HashMap)

Foi útil?

Solução 4

Trove4j tem a característica que eu estou atrás e que eles chamam de hash estratégias.

O mapa tem uma implementação com diferentes limitações e, portanto, diferentes pré-requisitos, então isso não significa implicitamente que uma implementação para HashMap "nativo" do Java seria viável.

Outras dicas

Um pouco tarde para você, mas para os futuros visitantes, pode valer a pena sabendo que commons-coleções tem uma AbstractHashedMap (em 3.2.2 e com os genéricos em 4.0 ). Você pode substituir esses métodos protegidos para atingir o seu comportamento desejado: 

protected int hash(Object key) { ... }
protected boolean isEqualKey(Object key1, Object key2) { ... }
protected boolean isEqualValue(Object value1, Object value2) { ... }
protected HashEntry createEntry(
    HashEntry next, int hashCode, Object key, Object value) { ... }

Um exemplo de implementação de um HashedMap dessas alternativas é própria IdentityMap commons-coleções (apenas até 3.2.2 como Java tem seu próprio desde 1.4).

Este não é tão poderoso como o fornecimento de um "Hasharator" externo a uma instância Map. Você tem que implementar uma nova classe de mapa para cada estratégia de hashing (composição vs. herança de volta impressionante ...). Mas ainda é bom saber.

.NET tem esta via IEqualityComparer (por um tipo que pode comparar dois objectos) e IEquatable (por um tipo que pode comparar-se a um outro exemplo).

Na verdade, eu acredito que foi um erro para definir a igualdade e hashcodes em java.lang.Object ou System.Object em tudo. Igualdade, em particular, é difícil de definir de uma maneira que faz sentido com a herança. I manter significado para o blog sobre isso ...

Mas sim, basicamente, a idéia é boa.

HashingStrategy é o conceito que você está procurando. É uma interface estratégia que permite definir implementações personalizadas de iguais e hashCode. 

public interface HashingStrategy<E>
{
    int computeHashCode(E object);
    boolean equals(E object1, E object2);
}

Você não pode usar uma HashingStrategy com o construído em HashSet ou HashMap. GS coleções inclui uma java.util.Set chamado UnifiedSetWithHashingStrategy e um java.util.Map chamado UnifiedMapWithHashingStrategy.

Vamos olhar um exemplo. 

public class Data
{
    private final int id;

    public Data(int id)
    {
        this.id = id;
    }

    public int getId()
    {
        return id;
    }

    // No equals or hashcode
}

Veja como você pode configurar uma UnifiedSetWithHashingStrategy e usá-lo. 

java.util.Set<Data> set =
  new UnifiedSetWithHashingStrategy<>(HashingStrategies.fromFunction(Data::getId));
Assert.assertTrue(set.add(new Data(1)));

// contains returns true even without hashcode and equals
Assert.assertTrue(set.contains(new Data(1)));

// Second call to add() doesn't do anything and returns false
Assert.assertFalse(set.add(new Data(1)));

Porque não basta usar um Map? UnifiedSetWithHashingStrategy utiliza metade da memória de um UnifiedMap, e um quarto a memória de um HashMap. E às vezes você não tem uma chave conveniente e tem que criar um sintético, como uma tupla. Isso pode desperdiçar mais memória.

Como podemos realizar pesquisas? Lembre-se de que os conjuntos têm contains(), mas não get(). implementos UnifiedSetWithHashingStrategy Pool além Set, por isso também implementa uma forma de get().

Aqui está uma abordagem simples para lidar com cadeias de maiúsculas e minúsculas. 

UnifiedSetWithHashingStrategy<String> set = 
  new UnifiedSetWithHashingStrategy<>(HashingStrategies.fromFunction(String::toLowerCase));
set.add("ABC");
Assert.assertTrue(set.contains("ABC"));
Assert.assertTrue(set.contains("abc"));
Assert.assertFalse(set.contains("def"));
Assert.assertEquals("ABC", set.get("aBc"));

Esta mostra o API, mas não é apropriado para a produção. O problema é que o HashingStrategy constantemente delegados String.toLowerCase() que cria um monte de Cordas de lixo. Veja como você pode criar uma estratégia de hashing eficiente para Cordas insensíveis ao caso. 

public static final HashingStrategy<String> CASE_INSENSITIVE =
  new HashingStrategy<String>()
  {
    @Override
    public int computeHashCode(String string)
    {
      int hashCode = 0;
      for (int i = 0; i < string.length(); i++)
      {
        hashCode = 31 * hashCode + Character.toLowerCase(string.charAt(i));
      }
      return hashCode;
    }

    @Override
    public boolean equals(String string1, String string2)
    {
      return string1.equalsIgnoreCase(string2);
    }
  };

Nota:. Eu sou um desenvolvedor de coleções GS

Nota: Como foi observado em todas as outras respostas, HashMaps não têm uma ordenação explícita. Eles só reconhecem "igualdade". Obtendo uma ordem a partir de uma estrutura de dados com base em hash é insignificante, uma vez que cada objecto é transformado em um hash -., Essencialmente, um número aleatório

Você sempre pode escrever uma função hash para uma classe (e muitas vezes deve), contanto que você fazê-lo com cuidado. Isso é uma coisa difícil de fazer corretamente porque estruturas de dados baseadas em hash contar com uma distribuição aleatória, uniforme de valores hash. Em Java eficaz, há uma grande quantidade de texto dedicado a aplicar correctamente um método de hash com bom comportamento.

Com tudo o que está sendo dito, se você só quer o seu hash para ignorar o caso de um String, você pode escrever uma classe wrapper em torno String para este fim e insira-os na sua estrutura de dados em vez disso.

Uma implementação simples: 

public class LowerStringWrapper {
    public LowerStringWrapper(String s) {
        this.s = s;
        this.lowerString = s.toLowerString();
    }

    // getter methods omitted

    // Rely on the hashing of String, as we know it to be good.
    public int hashCode() { return lowerString.hashCode(); }

    // We overrode hashCode, so we MUST also override equals. It is required
    // that if a.equals(b), then a.hashCode() == b.hashCode(), so we must
    // restore that invariant.
    public boolean equals(Object obj) {
        if (obj instanceof LowerStringWrapper) {
            return lowerString.equals(((LowerStringWrapper)obj).lowerString;
        } else {
            return lowerString.equals(obj);
        }
    }

    private String s;
    private String lowerString;
}

boa pergunta, peça Bloch josh. i submetido esse conceito como um RFE em Java 7, mas foi abandonada, acredito que o motivo foi o desempenho algo relacionado. Concordo, porém, deveria ter sido feito.

Eu suspeito que isso não foi feito porque iria impedir o cache hashCode?

Eu tentei criar uma solução Mapa genérico, onde todas as chaves são silenciosamente embrulhado. Descobriu-se que o invólucro que tem que segurar o objeto embrulhado, o hashCode em cache e uma referência para o retorno de chamada de interface responsável pela igualdade de verificações. Isso obviamente não é tão eficiente quanto usar uma classe wrapper, onde você só tem que armazenar em cache a chave original, acrescido de mais um objeto (veja hazzens resposta).

(Eu também esbarrou em um problema relacionado com os genéricos; o método get aceita objeto como entrada, de modo que o retorno de chamada de interface responsável por hashing teria que realizar uma instanceof-verificação adicional Ou isso, ou a classe mapa teria que. conhecer a Classe de suas chaves.)

Esta é uma idéia interessante, mas é absolutamente horrendo para o desempenho. A razão para isso é muito fundamental para a idéia de um hashtable: a ordenação não pode ser invocado . Hashtables são muito rápidos ( constante de tempo ) por causa da maneira em que elementos de índice da tabela : calculando um hash pseudo inteiro único para esse elemento e aceder a essa localização de uma matriz. É, literalmente, computando uma posição na memória e armazenar diretamente o elemento.

Isto contrasta com uma árvore equilibrada binária de pesquisa (TreeMap), que deve começar na raiz e trabalhar seu caminho até o nó desejado cada vez que é necessária uma pesquisa. Wikipedia tem algum mais aprofundada análise . Para resumir, a eficiência de um mapa de árvore é dependente de uma ordenação consistente, assim, a ordem dos elementos é previsível e sã. No entanto, por causa do desempenho hit imposta pelo "travessia para o seu destino" abordagem, BSTs só são capazes de fornecer O (log (n)) performance. Para grandes mapas, isso pode ser um sucesso significativo no desempenho.

É possível impor uma ordenação consistente em um hashtable, mas para fazê-lo envolve o uso de técnicas semelhantes para LinkedHashMap e manter manualmente a ordenação. Alternativamente, duas estruturas de dados separadas podem ser mantidas internamente: a hashtable e uma árvore. A tabela pode ser usado para pesquisas, enquanto a árvore pode ser usado para iteração. O problema, claro, é isso usa mais do que o dobro da memória necessária. Além disso, as inserções são somente tão rápido como a árvore: O (log (n)). truques simultâneos podem trazer esta um pouco para baixo, mas isso não é uma otimização de desempenho confiável.

Em suma, a sua ideia sons realmente bom, mas se você realmente tentou implementá-lo, você verá que a fazê-lo iria impor limitações de desempenho maciças. O veredicto final é (e tem sido há décadas): se você precisa de desempenho, use uma tabela hash; se você precisa de ordenação e pode viver com um desempenho degradado, usar uma árvore de pesquisa balanceada binário. Eu tenho medo não há realmente combinando nenhuma forma eficiente as duas estruturas sem perder algumas das garantias de um ou outro.

Não há tal recurso no com.google.common.collect.CustomConcurrentHashMap, infelizmente, não há atualmente nenhuma maneira pública como definir o Equivalence (sua Hasharator). Talvez eles ainda não está feito com ele, talvez eles não consideram o recurso ser suficiente útil. Pergunte na goiaba lista de discussão .

Eu me pergunto por que isso ainda não aconteceu, como foi mencionado neste talk mais de dois anos atrás.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top