Como o HashTables lida com as colisões?

97

Ouvi em minhas aulas de graduação que a HashTablecolocará uma nova entrada no bloco 'próximo disponível' se a nova entrada de chave colidir com outra.

Como o HashTableainda retornaria o valor correto se essa colisão ocorrer ao chamar alguém de volta com a chave de colisão?

Estou assumindo que o tipo Keysare Stringe hashCode()retorna o padrão gerado por, digamos, Java.

Se eu implementar minha própria função de hashing e usá-la como parte de uma tabela de consulta (ou seja, a HashMapou Dictionary), quais estratégias existem para lidar com colisões?

Eu até vi notas relacionadas a números primos! Informações não tão claras na pesquisa do Google.

Alex
fonte

Respostas:

92

As tabelas de hash lidam com as colisões de duas maneiras.

Opção 1: cada bucket contém uma lista vinculada de elementos que são hash para esse bucket. É por isso que uma função de hash ruim pode tornar as pesquisas em tabelas de hash muito lentas.

Opção 2: se as entradas da tabela hash estiverem todas cheias, a tabela hash pode aumentar o número de depósitos que possui e, em seguida, redistribuir todos os elementos da tabela. A função hash retorna um inteiro e a tabela hash tem que pegar o resultado da função hash e modificá-lo em relação ao tamanho da tabela de forma que possa ter certeza de que chegará ao intervalo. Portanto, ao aumentar o tamanho, ele irá refazer e executar os cálculos do módulo que, se você tiver sorte, poderá enviar os objetos para diferentes baldes.

Java usa as opções 1 e 2 em suas implementações de tabela hash.

ams
fonte
1
No caso da primeira opção, há algum motivo para usar uma lista vinculada em vez de um array ou mesmo uma árvore de pesquisa binária?
1
a explicação acima é de alto nível, não acho que faça muita diferença quanto à lista vinculada vs. array. Acho que uma árvore de pesquisa binária seria um exagero. Também acho que se você se aprofundar em coisas como ConcurrentHashMap e outros, existem muitos detalhes de implementação de baixo nível que podem fazer uma diferença de desempenho, que a explicação de alto nível acima não leva em consideração.
ams
2
Se o encadeamento for usado, ao receber uma chave, como saberemos qual item retornar?
ChaoSXDemon
1
@ChaoSXDemon você pode percorrer a lista na cadeia por chave, chaves duplicadas não são o problema, o problema é que duas chaves diferentes têm o mesmo hashcode.
ams
1
@ams: Qual é o preferido? Existe algum limite para colisão de Hash, após o qual o segundo ponto é executado por JAVA?
Shashank Vivek
77

Quando você falou sobre "A tabela de hash colocará uma nova entrada no depósito 'próximo disponível' se a nova entrada de chave colidir com outra.", Você está falando sobre a estratégia de endereçamento aberto de resolução de colisão da tabela de hash.


Existem várias estratégias para a tabela de hash resolver a colisão.

O primeiro tipo de método grande exige que as chaves (ou ponteiros para elas) sejam armazenadas na tabela, junto com os valores associados, que incluem ainda:

  • Encadeamento separado

insira a descrição da imagem aqui

  • Endereçamento aberto

insira a descrição da imagem aqui

  • Hash misturado
  • Cuco hashing
  • Robin Hood hashing
  • Hashing de 2 opções
  • Hopscotch hashing

Outro método importante para lidar com a colisão é por redimensionamento dinâmico , que ainda tem várias maneiras:

  • Redimensionar copiando todas as entradas
  • Redimensionamento incremental
  • Teclas monotônicas

EDITAR : os itens acima foram emprestados de wiki_hash_table , onde você deve dar uma olhada para obter mais informações.

herohuyongtao
fonte
3
"[...] requer que as chaves (ou ponteiros para elas) sejam armazenadas na tabela, junto com os valores associados". Obrigado, este é o ponto que nem sempre fica imediatamente claro ao ler sobre mecanismos para armazenar valores.
mtone
27

Existem várias técnicas disponíveis para lidar com a colisão. Vou explicar alguns deles

Encadeamento: no encadeamento, usamos índices de array para armazenar os valores. Se o código hash do segundo valor também aponta para o mesmo índice, então substituímos esse valor de índice por uma lista encadeada e todos os valores que apontam para esse índice são armazenados na lista encadeada e o índice de array real aponta para o início da lista encadeada. Mas se houver apenas um código hash apontando para um índice de array, o valor é armazenado diretamente nesse índice. A mesma lógica é aplicada ao recuperar os valores. Isso é usado em Java HashMap / Hashtable para evitar colisões.

Sondagem linear: esta técnica é usada quando temos mais índice na tabela do que os valores a serem armazenados. A técnica de sondagem linear funciona com o conceito de continuar incrementando até encontrar um slot vazio. O pseudocódigo tem a seguinte aparência:

index = h(k) 

while( val(index) is occupied) 

index = (index+1) mod n

Técnica de hash duplo: nesta técnica, usamos duas funções de hash h1 (k) e h2 (k). Se o slot em h1 (k) estiver ocupado, a segunda função de hashing h2 (k) usada para incrementar o índice. O pseudocódigo tem a seguinte aparência:

index = h1(k)

while( val(index) is occupied)

index = (index + h2(k)) mod n

As técnicas de sondagem linear e hashing duplo fazem parte da técnica de endereçamento aberto e só podem ser usadas se os slots disponíveis forem mais do que o número de itens a serem adicionados. Leva menos memória do que o encadeamento porque não há nenhuma estrutura extra usada aqui, mas é lento porque muitos movimentos acontecem até encontrarmos um slot vazio. Também na técnica de endereçamento aberto, quando um item é removido de um slot, colocamos uma marca de exclusão para indicar que o item foi removido daqui, por isso está vazio.

Para obter mais informações, consulte este site .

Jatinder Pal
fonte
18

Eu sugiro fortemente que você leia esta postagem do blog que apareceu no HackerNews recentemente: Como o HashMap funciona em Java

Em suma, a resposta é

O que acontecerá se dois objetos-chave HashMap diferentes tiverem o mesmo código hash?

Eles serão armazenados no mesmo intervalo, mas nenhum nó seguinte da lista vinculada. E o método keys equals () será usado para identificar o par de valores-chave correto no HashMap.

Zengr
fonte
3
HashMaps são muito interessantes e vão fundo! :)
Alex
1
Eu acho que a questão é sobre HashTables, não HashMap
Prashant Shubham
10

Ouvi em minhas aulas de graduação que um HashTable colocará uma nova entrada no bloco 'próximo disponível' se a nova entrada de chave colidir com outra.

Na verdade, isso não é verdade, pelo menos para o Oracle JDK ( é um detalhe de implementação que pode variar entre as diferentes implementações da API). Em vez disso, cada depósito contém uma lista vinculada de entradas anteriores ao Java 8 e uma árvore balanceada no Java 8 ou superior.

então, como o HashTable ainda retornaria o valor correto se essa colisão ocorrer ao chamar alguém de volta com a chave de colisão?

Ele usa o equals()para encontrar a entrada realmente correspondente.

Se eu implementar minha própria função de hashing e usá-la como parte de uma tabela de consulta (ou seja, um HashMap ou Dicionário), quais estratégias existem para lidar com as colisões?

Existem várias estratégias de tratamento de colisões com diferentes vantagens e desvantagens. A entrada da Wikipedia em tabelas de hash oferece uma boa visão geral.

Michael Borgwardt
fonte
É verdade para ambos Hashtablee HashMapno JDK 1.6.0_22 da Sun / Oracle.
Nikita Rybak
@Nikita: não tenho certeza sobre o Hashtable e não tenho acesso às fontes no momento, mas estou 100% certo que o HashMap usa encadeamento e não teste linear em todas as versões que já vi em meu depurador.
Michael Borgwardt
@Michael Bem, estou olhando a fonte do HashMap public V get(Object key)agora (mesma versão acima). Se você encontrar uma versão precisa onde essas listas vinculadas aparecem, eu gostaria de saber.
Nikita Rybak
@Niki: Agora estou olhando para o mesmo método e o vejo usando um loop for para iterar por meio de uma lista vinculada de Entryobjetos:localEntry = localEntry.next
Michael Borgwardt
@Michael Desculpe, é meu erro. Interpretei o código de maneira errada. naturalmente, e = e.nextnão é ++index. +1
Nikita Rybak
7

Atualização desde Java 8: Java 8 usa uma árvore auto-balanceada para tratamento de colisão, melhorando o pior caso de O (n) para O (log n) para pesquisa. O uso de uma árvore auto-balanceada foi introduzido no Java 8 como uma melhoria sobre o encadeamento (usado até o java 7), que usa uma lista vinculada e tem um pior caso de O (n) para pesquisa (uma vez que precisa atravessar a lista)

Para responder à segunda parte da sua pergunta, a inserção é feita mapeando um determinado elemento para um determinado índice na matriz subjacente do hashmap, no entanto, quando ocorre uma colisão, todos os elementos ainda devem ser preservados (armazenados em uma estrutura de dados secundária , e não apenas substituído na matriz subjacente). Isso geralmente é feito fazendo com que cada componente da matriz (slot) seja uma estrutura de dados secundária (também conhecido como balde), e o elemento é adicionado ao depósito que reside no índice de matriz fornecido (se a chave ainda não existir no depósito, em caso em que é substituído).

Durante a pesquisa, a chave é hash para seu índice de matriz correspondente, e a pesquisa é realizada por um elemento que corresponda à chave (exata) no intervalo fornecido. Como o balde não precisa lidar com colisões (compara as chaves diretamente), isso resolve o problema das colisões, mas o faz ao custo de ter que realizar a inserção e consulta na estrutura de dados secundária. O ponto principal é que em um hashmap, a chave e o valor são armazenados e, portanto, mesmo se o hash colidir, as chaves são comparadas diretamente quanto à igualdade (no balde) e, portanto, podem ser identificadas exclusivamente no balde.

Tratamento de colisão traz o pior caso de desempenho de inserção e pesquisa de O (1) no caso de não tratamento de colisão para O (n) para encadeamento (uma lista vinculada é usada como estrutura de dados secundária) e O (log n) para árvore auto-equilibrada.

Referências:

Java 8 veio com as seguintes melhorias / alterações de objetos HashMap no caso de grandes colisões.

  • A função hash de String alternativa incluída no Java 7 foi removida.

  • Buckets contendo um grande número de chaves em conflito irão armazenar suas entradas em uma árvore balanceada em vez de em uma lista vinculada após determinado limite ser atingido.

As alterações acima garantem o desempenho de O (log (n)) nos piores cenários ( https://www.nagarro.com/en/blog/post/24/performance-improvement-for-hashmap-in-java-8 )

Daniel Valland
fonte
Você pode explicar como a inserção de pior caso para um HashMap de lista vinculada é apenas O (1), e não O (N)? Parece-me que se você tiver uma taxa de colisão de 100% para chaves não duplicadas, você acaba tendo que percorrer todos os objetos no HashMap para encontrar o final da lista vinculada, certo? o que estou perdendo?
mbm29414
No caso específico da implementação de hashmap, você está realmente certo, mas não porque precisa encontrar o final da lista. Em uma implementação de lista encadeada de caso geral, um ponteiro é armazenado tanto para a cabeça quanto para a cauda e, portanto, a inserção pode ser feita em O (1) anexando o próximo nó à cauda diretamente, mas no caso de hashmap, o método de inserção precisa garantir que não haja duplicatas e, portanto, deve pesquisar a lista para verificar se o elemento já existe e, portanto, acabamos com O (n). E, portanto, é a propriedade definida imposta a uma lista vinculada que está causando O (N). Farei uma correção à minha resposta :)
Daniel Valland
4

Ele usará o método equals para ver se a chave está presente mesmo e, especialmente, se houver mais de um elemento no mesmo intervalo.

Hovercraft cheio de enguias
fonte
4

Como há alguma confusão sobre qual algoritmo o HashMap do Java está usando (na implementação Sun / Oracle / OpenJDK), aqui estão os trechos de código-fonte relevantes (do OpenJDK, 1.6.0_20, no Ubuntu):

/**
 * Returns the entry associated with the specified key in the
 * HashMap.  Returns null if the HashMap contains no mapping
 * for the key.
 */
final Entry<K,V> getEntry(Object key) {
    int hash = (key == null) ? 0 : hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

Este método (cite é das linhas 355 a 371) é chamado ao pesquisar uma entrada na tabela, por exemplo get(), from containsKey()e alguns outros. O loop for aqui passa pela lista encadeada formada pelos objetos de entrada.

Aqui está o código para os objetos de entrada (linhas 691-705 + 759):

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    final int hash;

    /**
     * Creates new entry.
     */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }

  // (methods left away, they are straight-forward implementations of Map.Entry)

}

Logo em seguida vem o addEntry()método:

/**
 * Adds a new entry with the specified key, value and hash code to
 * the specified bucket.  It is the responsibility of this
 * method to resize the table if appropriate.
 *
 * Subclass overrides this to alter the behavior of put method.
 */
void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

Isso adiciona a nova entrada na frente do depósito, com um link para a primeira entrada antiga (ou nulo, se não houver). Da mesma forma, oremoveEntryForKey() método percorre a lista e se encarrega de excluir apenas uma entrada, deixando o resto da lista intacto.

Então, aqui está uma lista de entrada vinculada para cada segmento e duvido muito que isso tenha mudado de _20para_22 , já que foi assim a partir de 1.2.

(Este código é (c) 1997-2007 Sun Microsystems, e disponível sob GPL, mas para copiar melhor use o arquivo original, contido em src.zip em cada JDK da Sun / Oracle, e também no OpenJDK.)

Paŭlo Ebermann
fonte
1
Eu marquei isso como wiki da comunidade , já que não é realmente uma resposta, mais um pouco de discussão para as outras respostas. Nos comentários, simplesmente não há espaço suficiente para tais citações de código.
Paŭlo Ebermann
3

aqui está uma implementação de tabela hash muito simples em java. em apenas implementos put()e get(), mas você pode adicionar facilmente o que quiser. ele depende do hashCode()método java que é implementado por todos os objetos. você pode facilmente criar sua própria interface,

interface Hashable {
  int getHash();
}

e force sua implementação pelas chaves, se desejar.

public class Hashtable<K, V> {
    private static class Entry<K,V> {
        private final K key;
        private final V val;

        Entry(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }

    private static int BUCKET_COUNT = 13;

    @SuppressWarnings("unchecked")
    private List<Entry>[] buckets = new List[BUCKET_COUNT];

    public Hashtable() {
        for (int i = 0, l = buckets.length; i < l; i++) {
            buckets[i] = new ArrayList<Entry<K,V>>();
        }
    }

    public V get(K key) {
        int b = key.hashCode() % BUCKET_COUNT;
        List<Entry> entries = buckets[b];
        for (Entry e: entries) {
            if (e.key.equals(key)) {
                return e.val;
            }
        }
        return null;
    }

    public void put(K key, V val) {
        int b = key.hashCode() % BUCKET_COUNT;
        List<Entry> entries = buckets[b];
        entries.add(new Entry<K,V>(key, val));
    }
}
Jeffrey Blattman
fonte
2

Existem vários métodos para resolução de colisão. Alguns deles são encadeamento separado, endereçamento aberto, hashing Robin Hood, hashing cuco etc.

Java usa o encadeamento separado para resolver colisões em tabelas de Hash. Este é um ótimo link para saber como isso acontece: http://javapapers.com/core-java/java-hashtable/

Infusão de absinto n Asfodel
fonte