Uma das coisas mais comuns em programação é realizar uma pesquisa por um item que pode estar armazenado em alguma estrutura.
Será apresentada a ideia da implementação interna de estruturas como Dict em Python, HashMap em Java, Map ou Object em JavaScript, entre outras.
Arrays de Acesso Direto - arr[i]
Arrays estáticos de acesso direto possuem complexidade de busca O(1), então se meu usuário precisa pesquisar por uma chave que representa um número inteiro, basta pesquisar diretamente arr[chave].
O que acontece quando o usuário precisa armazenar 10^9 itens? Vamos alocar um array com tamanho 10^9? Seria um uso exacerbado de memória.
Hashing & HashTable
É possível manter a busca em O(1) usando menos espaço em memória? Podemos armazenar itens em um array menor para continuarmos com os benefícios do array estático, mas precisamos de uma técnica de mapeamento de chaves para pesquisar em um índice diferente nesse array. Essa técnica é chamada de hashing e o array menor é chamado de hashtable. Esse array menor pode diminuir ou aumentar de tamanho conforme necessidade, por exemplo em muitas operações de inserção e deleção.
Quando recebermos a chave de um item, passaremos ela por uma função chamada de hash function. O resultado dessa função de hash será o índice que devemos acessar na hashtable. Porém, essa função de hash pode causar um problema conhecido como colisão, que é quando duas chaves possuem o mesmo resultado após passar pela função de hash.
No caso abaixo, as chaves são nomes de pessoas. Os nomes Rose e Zig após passarem pela função de hash resultaram no mesmo índice da hashtable.
Se cada posição da hashtable pode armazenar apenas um item, como resolveremos isso?
Chaining
Chaining é uma estratégia onde as posições da hashtable armazenam um ponteiro para uma estrutura de dado sequencial, essa estrutura sequencial pode ser um array dinâmico ou uma lista encadeada.
Após a chave passar pela hash function, é necessário efetuar uma busca linear na estrutura sequencial daquele índice da hashtable e comparar as chaves que estão na lista.
Essa busca linear não é um problema desde que a lista encadeada permaneça muito pequena. Para isso, a função de hash precisa evitar ao máximo as colisões.
Open Addressing
Não considero uma solução muito adequada, pois precisamos garantir que todas chaves terão um lugar próprio na hashtable. Isso significa que se o usuário necessitar de 10^9 chaves, nossa hashtable terá 10^9 índices.
Mas como se resolve o problema de colisões em open addressing? Uma das técnicas é chamada de linear probing. Se o retorno da função de hash é de um índice já utilizado, simplesmente executamos a função até que um índice vazio seja encontrado.
A próxima seção será especificamente sobre hash functions, mas por agora considere M como o tamanho atual da hashtable e hash(chave) como sendo a chamada da função de hash.
Sendo assim, para buscar um índice vazio utilizando linear probing podemos fazer:
Se hash(chave) % M não está vazio, tentamos (hash(chave) + 1) % M.
Se (hash(chave) + 1) % M não está vazio, tentamos (hash(chave) + 2) % M, e assim por diante.
Existem outras estratégias para lidar com o problema de colisões em open addressing, algumas delas podem ser encontradas nas referências. Geralmente não é uma técnica utilizada pela dificuldade de implementação de acordo com a técnica para escapar de colisões e por quase sempre não conhecermos previamente o total de chaves.
Hash Functions
Após visto duas técnicas para implementação de hashtable, precisamos saber como implementar efetivamente a função de hash. Afinal, essa implementação é o coração da estrutura de dado, pois precisa praticamente evitar colisões distribuindo as chaves pela hashtable.
Método da Divisão — Hash Function
É o método mais simples para mapear um inteiro que pertence a um domínio de dados grande para um domínio menor.
h(k) = k mod m — (k % m) — , onde k é a chave original que está sendo buscada ou inserida e m é o tamanho atual da hashtable. Sendo assim, todo inteiro k será mapeado para algum índice dentro do domínio da nossa tabela hash.
Porém, teremos muitas colisões se muitas chaves por mod m começarem a ter o mesmo resto de divisão.
Hash Universal
Se quisermos que a performance da estrutura seja independente das chaves. O problema mencionado no método da divisão pode ocorrer com qualquer função de hash escolhida, mas há uma fórmula que gera uma família de funções de hash boas o suficiente para grande parte.
h(k) = (((ak + b) mod p) mod m)
A fórmula acima é uma geradora de funções de hash. Os valores a e b são escolhidos de forma aleatória, desde que a seja diferente de zero. O valor p é um número primo maior do que m. Por fim, m é o tamanho atual da hashtable.
Os valores acima não mudam a cada chave que vamos mapear na hashtable, eles são escolhidos e utilizados de forma fixa para distribuir os dados na estrutura. O único momento que esses valores mudam é quando precisamos realocar o tamanho da hashtable.
Realocação da Tabela de Hash
Pode ser necessário quando há muito espaço livre na tabela, e para economizar espaço resolvemos diminuí-la ou quando a quantidade de chaves está perto do tamanho total da tabela, nesse caso precisamos aumentá-la.
Além de escolher uma nova função de hash a partir da fórmula geradora, também precisamos pegar todos os itens que estavam na tabela antiga e passar eles pela nova função da hash para inserirmos na nova tabela. Essa operação custa O(n) tempo e é comum em estruturas que encapsulam arrays estáticos.
Top comments (0)
Some comments have been hidden by the post's author - find out more