Neste tutorial, você aprenderá o que é um Hashing.
Hashing é uma técnica de mapeamento de um grande conjunto de dados arbitrários para índices tabulares usando uma função hash. É um método para representar dicionários para grandes conjuntos de dados.
Ele permite que as operações de pesquisa, atualização e recuperação ocorram em um tempo constante, ou seja O(1)
.
Por que o hash é necessário?
Depois de armazenar uma grande quantidade de dados, precisamos realizar várias operações nesses dados. As pesquisas são inevitáveis para os conjuntos de dados. A pesquisa linear e a pesquisa binária executam pesquisas / pesquisas com complexidade de tempo de O(n)
e, O(log n)
respectivamente. À medida que o tamanho do conjunto de dados aumenta, essas complexidades também se tornam significativamente altas, o que não é aceitável.
Precisamos de uma técnica que não dependa do tamanho dos dados. O hash permite que as pesquisas ocorram em tempo constante, ou seja O(1)
.
Função Hash
Uma função hash é usada para mapear cada elemento de um conjunto de dados para índices na tabela.
Para obter mais informações sobre a tabela de hash, técnicas de resolução de colisão e funções de hash, visite Tabela de hash.