🤸🏿 ⬅️ 👩🏼 O que você precisa saber sobre coleções baseadas em hash 🎅🏿 👂🏽 👩🏾‍🤝‍👩🏽

Olá a todos. Em contato com Vladislav Rodin. Atualmente, sou o chefe do curso de arquiteto de carga alta da OTUS e também ensino cursos de arquitetura de software.

Além do ensino, como você deve ter notado, também estou escrevendo material com direitos autorais para o blog OTUS em Habré e quero dedicar o artigo de hoje ao lançamento de um novo fluxo do curso "Algoritmos para desenvolvedores" .

Introdução

Tabelas de hash (HashMap), juntamente com matrizes dinâmicas, são as estruturas de dados mais populares usadas na produção. Muitas vezes, você pode ouvir perguntas em entrevistas sobre seus propósitos, recursos de sua estrutura interna e algoritmos relacionados. Essa estrutura de dados é clássica e é encontrada não apenas em Java, mas também em muitas outras linguagens de programação.

Formulação do problema

Vamos definir uma meta para criar uma estrutura de dados que permita:

contém (elemento Elemento) verifica se um elemento está nele ou não, para O (1)
add (elemento Element) adiciona um elemento em O (1)
delete (elemento Element) exclui um elemento em O (1)

Matriz

Vamos tentar fazer essas operações sobre uma matriz, que é a estrutura de dados mais simples. Concordamos que consideraremos a célula vazia se ela contiver nulo.

Verificação de disponibilidade

É necessário fazer uma pesquisa linear através da matriz, porque o elemento pode estar potencialmente em qualquer célula. Assintoticamente, isso pode ser feito em O (n), onde n é o tamanho da matriz.

Adicionando

Se precisarmos adicionar um elemento em qualquer lugar, primeiro precisamos encontrar uma célula vazia e depois gravar o elemento nela. Assim, realizamos novamente uma pesquisa linear e obtemos o comportamento assintótico de O (n).

Excluir

Para excluir um elemento, você deve primeiro encontrá-lo e depois escrever nulo na célula encontrada. Novamente, a pesquisa linear nos leva a O (n).

O conjunto de hash mais simples

Observe que, a cada operação, primeiro pesquisamos o índice da célula desejada e, em seguida, realizamos a operação, e é a pesquisa que estraga os assintóticos para nós! Se aprendêssemos a obter esse índice para O (1), o problema original seria resolvido.

Vamos agora substituir a pesquisa linear pelo seguinte algoritmo: calcularemos o valor de uma determinada função - uma função hash que mapeia um objeto de classe para um número inteiro. Depois disso, compararemos o número inteiro resultante com o índice da célula da matriz (isso é bastante fácil, por exemplo, tomar o restante da divisão desse número pelo tamanho da matriz). Se a função hash é escrita de tal maneira que é considerada O (1) (e geralmente é escrita assim), obtemos a implementação mais simples do conjunto de hash. Uma célula de matriz em termos de um conjunto de hash pode ser chamada de bucket .

Os problemas da implementação mais simples de um conjunto de hash

Não importa como a função hash seja escrita, o número de células na matriz é sempre limitado, enquanto o conjunto de elementos que queremos armazenar na estrutura de dados é ilimitado. Afinal, não nos preocuparíamos com a estrutura de dados se houvesse a necessidade de salvar apenas dez elementos conhecidos anteriormente, certo? Esse estado de coisas leva a conflitos inevitáveis . Uma colisão é uma situação em que, ao adicionar objetos diferentes, caímos na mesma célula na matriz.

Dois métodos foram inventados para resolver colisões: o método de encadeamento e o método de endereçamento aberto .

Método de encadeamento

O método de encadeamento é o método mais simples para resolver colisões. Na célula da matriz, não armazenaremos os elementos, mas uma lista vinculada desses elementos. Como adicionar ao topo da lista (e não nos importamos com qual parte da lista adicionar o elemento) tem o comportamento assintótico de O (1), não estragaremos o comportamento assintótico geral e permanecerá igual a O (1).

Essa implementação tem um problema: se as listas crescem muito (como último recurso, podemos considerar uma função hash que retorna uma constante para qualquer objeto), obtemos os assintóticos O (m), em que m é o número de elementos no conjunto, se o tamanho matriz é fixa. Para evitar tais problemas, o conceito de ciclo de serviço é introduzido.(pode ser igual, por exemplo, 1,5). Se ao adicionar um elemento, verifica-se que a fração do número de elementos que estão na estrutura de dados em relação ao tamanho da matriz excede o fator de preenchimento, acontece o seguinte: uma nova matriz é selecionada cujo tamanho excede o tamanho da matriz antiga (por exemplo, 2 vezes) e a estrutura de dados é reconstruída na nova matriz.

Esse método de resolução de colisões é usado em Java e a estrutura de dados é chamada HashSet .

Método de endereçamento aberto

Nesse método, os próprios elementos são armazenados nas células e, no caso de uma colisão, ocorre uma sequência de amostras , ou seja, começamos a classificar as células usando algum algoritmo na esperança de encontrar um livre. Isso pode ser feito por diferentes algoritmos ( sequência linear / quadrática de amostras , hash duplo ), cada um com seus próprios problemas (por exemplo, o surgimento de clusters primários ou secundários ).

De um conjunto de hash para uma tabela de hash (HashMap)

Vamos criar uma estrutura de dados que permita adicionar, excluir, procurar itens, mas por alguma chave, tão rapidamente quanto um conjunto de hash (ou seja, além de O (1)).

Usaremos a mesma estrutura de dados que o conjunto de hash, mas não armazenaremos elementos, mas pares de elementos.

Assim, a inserção (put (Key key, Value value)) será realizada da seguinte forma: calcularemos a célula da matriz por um objeto do tipo Key, obteremos o número de bucket. Vamos percorrer a lista no balde, comparando a chave com a chave em pares armazenados. Se você encontrar a mesma chave - basta extrair o valor antigo, se você não a encontrar - adicione um par.

Como um item é recebido pela chave? Sim, de acordo com um princípio semelhante: obtemos um balde por chave, examinamos os pares e retornamos o valor em um par, cuja chave é igual à chave na solicitação, se houver um par, e nulo de outra forma.

Essa estrutura de dados é chamada de tabela de hash .

Perguntas típicas da entrevista

P: Como o HashSet e o HashMap são organizados? Como são realizadas as principais operações nessas coleções? Como os métodos equals () e hashCode () são aplicados?
R : As respostas para essas perguntas podem ser encontradas acima.

P: Qual é o contrato para equals () e hashCode ()? A que se deve?
R : Se os objetos forem iguais, eles deverão ter o hashCode igual. Portanto, o hashCode deve ser determinado pela capacidade dos campos envolvidos em iguais. A violação deste contrato pode levar a efeitos muito interessantes. Se os objetos forem iguais, mas seu hashCode for diferente, talvez você não obtenha o valor correspondente à chave pela qual você acabou de adicionar o objeto ao HashSet ou ao HashMap.

Conclusão

Nas entrevistas, eles gostam de perguntar casos diferentes relacionados a essas estruturas de dados. Além disso, a decisão de qualquer um deles pode ser deduzida da compreensão dos princípios de seu trabalho sem nenhum "empilhamento".

Isso é tudo. Se você leu o material até o final, convido minha colega Evgeny Volosatov a mostrar como resolver o problema das olimpíadas usando as idéias da programação dinâmica para uma lição gratuita sobre o tema "Segredos da programação dinâmica" .

O que você precisa saber sobre coleções baseadas em hash