A tabela hash permite implementar uma estrutura de dados de array associativo (dicionário) com desempenho médio O(1) para operações de inserção, exclusão e pesquisa.
Abaixo está um exemplo da implementação mais simples de um mapa hash em nodeJS:
Como funciona? Cuidado com as mãos:
- Dentro do mapa hash há um array
- Dentro do elemento array há um ponteiro para o primeiro nó da lista vinculada
- A memória é alocada para uma matriz de ponteiros (por exemplo, 65.535 elementos)
- Eles implementam uma função hash, a chave do dicionário é a entrada e na saída pode fazer qualquer coisa, mas no final retorna o índice do elemento do array
Como funciona a gravação:
- Na entrada há um par de chaves – valor
- A função hash retorna índice por chave
- Obter um nó de lista vinculada de um array por índice
- Verifique se corresponde à chave
- Se corresponder, substitua o valor
- Se não corresponder, passe para o próximo nó até encontrarmos ou encontrarmos um nó com a chave necessária.
- Se o nó ainda não for encontrado, crie-o no final da lista vinculada
Como funciona a pesquisa por chave:
- Na entrada há um par de chaves – valor
- A função hash retorna índice por chave
- Obter um nó de lista vinculada de um array por índice
- Verifique se corresponde à chave
- Se corresponder, retorne o valor
- Se não corresponder, passe para o próximo nó até encontrarmos ou encontrarmos um nó com a chave necessária.
Por que precisamos de uma lista vinculada dentro de um array? Devido a possíveis colisões ao calcular a função hash. Nesse caso, vários pares de valores-chave diferentes estarão localizados no mesmo índice da matriz, caso em que a lista vinculada é percorrida para encontrar a chave necessária.
Fontes
https://ru.wikipedia.org/wiki/Tabela hash
https://www.youtube.com/watch?v=wg8hZxMRwcw
Código fonte
https://gitlab.com/demensdeum/datastructures
