Tabelas de Espalhamento

Prévia do material em texto

DANIELA MAJORIE AKAMA DOS REIS
TABELAS
Sumário
INTRODUÇÃO ������������������������������������������������� 3
ORGANIZAÇÃO INTERNA ������������������������������ 4
ASPECTOS DE IMPLEMENTAÇÃO ����������������� 8
TABELAS DE ESPALHAMENTO (HASHING) 10
Conceitos de funcionamento ��������������������������������������������� 10
Funções de espalhamento ������������������������������������������������� 12
Tratamento de colisões ������������������������������������������������������ 23
Problemas envolvendo hashing ����������������������������������������� 30
CONSIDERAÇÕES FINAIS ����������������������������33
REFERÊNCIAS BIBLIOGRÁFICAS & 
CONSULTADAS ��������������������������������������������35
2
INTRODUÇÃO
Nesse e-book, conheceremos os conceitos funda-
mentais sobre as tabelas em estrutura de dados 
e a organização interna de tabelas, analisando os 
aspectos de implementação de tabelas hash� 
Trataremos, especificamente, sobre os concei-
tos relacionados a tabelas de espalhamento, ou 
hashing, buscando entender sobre o funcionamento 
das funções dessa tabela� Assim, entenderemos 
aspectos sobre as colisões em hash e as formas 
de lidar com este tipo de problema, além dos pro-
blemas relacionados ao hashing�
Bons estudos!
3
ORGANIZAÇÃO INTERNA
Para a maioria das pessoas que trabalham com 
pequenas e grandes quantidades de dados, a tabela 
de dados é a unidade fundamental para organiza-
ção� Ela é, sem dúvidas, a estrutura de dados mais 
antiga, sendo tanto uma forma de organizar dados 
para processamento por máquinas quanto uma 
forma clara e organizada de apresentar os dados 
aos humanos�
Uma tabela do Excel nos ajuda a entender diferentes 
saídas obtidas alterando uma ou duas entradas de 
uma fórmula� Uma tabela de dados não permite 
alterar mais de duas entradas de uma fórmula� 
No entanto, essas duas entradas podem ter tan-
tos valores possíveis (a serem experimentados) 
quanto se queira�
Por exemplo, uma organização pode querer estudar 
como as mudanças no caixa impactam seu capital 
de giro, assim, uma tabela de dados a ajudará a 
saber o nível ideal de caixa (a partir dos valores 
possíveis especificados) a ser mantido para cumprir 
suas obrigações de curto prazo�
O objetivo em criar tabelas de dados no Excel é 
analisar a variação nas saídas resultante de uma 
alteração na entrada� Além disso, uma única tabela 
pode apresentar todas as saídas, o que facilita a 
4
interpretação e permite o rápido compartilhamento 
com outros usuários�
As tabelas de dados são uma ferramenta que 
podem ser usadas também para fazer análises 
do tipo “e se”, ou seja, previsões, permitindo que 
os resultados de um cálculo variem até duas das 
entradas de cálculo� Por exemplo, imaginemos 
que uma agência de consultoria de crédito tem 
um cálculo supercomplexo para determinar a 
classificação de crédito de uma dada empresa. 
O cálculo pode ser feito em muitas planilhas e ter 
muitas entradas, mas resulta em um único valor 
da classificação de crédito sendo retornado. Esse 
cálculo complexo não poderia ser colocado em uma 
única célula para copiá-lo como em uma tabela do 
Excel� Assim, uma tabela de dados seria a única 
solução viável para analisar vários resultados com 
base em entradas variadas desse caso�
Resumidamente, as tabelas de dados exibem infor-
mações em um formato semelhante a uma grade 
de linhas e colunas� Elas organizam as informações 
de uma maneira fácil de verificar, permitindo que os 
usuários possam procurar padrões e desenvolver 
insights a partir dos dados� 
As tabelas de dados podem conter:
 y Componentes interativos (como chips, botões 
ou menus);
5
 y Elementos não interativos (como emblemas);
 y Ferramentas para consulta e manipulação de 
dados�
A partir dessas informações, podemos tratar do 
hashing, que é uma técnica usada para identificar, 
exclusivamente, um objeto específico de um grupo 
de objetos semelhantes�
Alguns exemplos de como o hashing é usado em 
nossas vidas incluem escolas e universidades, em 
que cada aluno recebe um número de matrícula 
exclusivo, que pode ser usado para recuperação 
de informações sobre eles ou em bibliotecas, em 
que cada livro recebe um número único que pode 
ser usado para determinar informações sobre 
ele, como sua posição exata na biblioteca ou os 
usuários para os quais emprestado, por exemplo�
Em ambos os exemplos, os alunos e os livros foram 
agrupados em um único número� Suponhamos, 
então, que temos um objeto e desejamos atribuir 
uma chave a ele para facilitar a pesquisa� Para 
armazenar a chave/valor podemos usar um array 
simples como uma estrutura de dados, onde as 
chaves (inteiros) podem ser aplicadas diretamente 
como um índice para armazenar valores� No en-
tanto, nos casos em que as chaves são grandes e 
não podem ser usadas diretamente como índice, 
devemos usar o hash�
6
No hashing, chaves grandes são convertidas em 
chaves pequenas usando funções de hash� Assim, 
os valores são armazenados em uma estrutura de 
dados chamada tabela hash� 
A ideia do hash é distribuir entradas (pares chave/
valor) uniformemente em uma matriz e a cada ele-
mento é atribuída uma chave (chave convertida)� 
Usando essa chave, podemos acessar o elemento 
em tempo O(1)� Ainda usando a chave, o algoritmo 
(função hash) calcula um índice que sugere onde 
uma entrada pode ser encontrada ou inserida�
O hash é implementado em duas etapas:
 y Um elemento é convertido em um inteiro usando 
uma função hash� Esse elemento pode ser usado 
como índice para armazenar o elemento original, 
que cai na tabela hash;
 y O elemento é armazenado na tabela hash, 
onde pode ser recuperado rapidamente usando a 
chave de hash�
7
ASPECTOS DE 
IMPLEMENTAÇÃO
Qualquer implementação de tabela hash deve 
conter três componentes:
 y Uma boa função hash para mapear chaves 
para valores;
 y Uma estrutura de dados de tabela hash que 
suporta operações de inserção, pesquisa e exclusão;
 y Uma estrutura de dados para levar em conta 
a colisão de chaves�
Considerando isso, o primeiro passo para a im-
plementação é escolher uma função hash razoa-
velmente boa e que tenha uma baixa chance de 
colisão�
Uma tabela hash em C/C++ é uma estrutura de 
dados que mapeia chaves para valores, ou seja, 
utiliza uma função de hash para calcular índices 
para uma chave� Com base no índice tabela hash, 
podemos armazenar o valor no local apropriado, 
se duas chaves diferentes obtiverem o mesmo 
índice, precisaremos usar outras estruturas de 
dados (buckets) para contabilizar essas colisões�
Todo o benefício de usar uma tabela hash é devido 
ao seu tempo de acesso muito rápido� Embora 
possa haver uma colisão, se escolhermos uma 
8
função hash muito boa, essa chance é quase zero� 
Assim, em média, a complexidade de tempo é um 
tempo de acesso O(1) constante� 
O Python é uma linguagem que usa tabelas hash 
em todos os lugares para tornar as pesquisas de 
nomes quase instantâneas� Embora, venha com 
sua própria tabela hash, chamada dict, pode ser útil 
entender como as tabelas hash funcionam� Uma 
avaliação de codificação pode até encarregá-lo 
de construir um� 
Por isso, estarmos familiarizados com dicionários 
Python e ter conhecimento básico dos princípios 
de programação orientada a objetos, ajuda muito 
na implementação com esta linguagem� 
Além de C e C++ e Python, outras linguagens podem 
ser usadas para implementar tabelas, como o Java�
Para conhecer alguns exemplos de implementação de 
tabelas hash nos sites abaixo, acesse o artigo “Tabelas 
Hash”, de João Arthur Brunet, disponível em:
https://joaoarthurbm�github�io/eda/posts/hashtable/#:~:-
text=O%20m%C3%A9todo%20da%20divis%C3%A3o%20
por,podem%20ter%20o%20mesmo%20hash�
https://acervolima�com/implementando-nossa-propria-
-tabela-de-hash-com-encadeamento-separado-em-java/� 
SAIBA MAIS
9
https://acervolima.com/implementando-nossa-propria-tabela-de-hash-com-encadeamento-separado-em-java/
https://acervolima.com/implementando-nossa-propria-tabela-de-hash-com-encadeamento-separado-em-java/
TABELASDE 
ESPALHAMENTO 
(HASHING)
CONCEITOS DE FUNCIONAMENTO
Técnicas para gerenciar dados com eficiência são 
tópicos tradicionais em ciência da computação� 
Além de armazenar dados, recuperá-los com efi-
ciência é outra preocupação relevante, para tanto, 
algoritmos são utilizados�
Um algoritmo de hash é uma fórmula matemática 
que recebe determinada entrada de dados e gera 
um valor de comprimento fixo chamado valor de 
hash, que atua como uma representação resumida 
do valor original� Por exemplo, se um computador 
contém uma senha que diz “P1234”, o computador 
usará uma função hash para truncar “P1234” em 
um valor de hash de tamanho fixo, como “01”.
Pensemos, então, em um valor de hash como uma 
série de caixas numeradas que variam de um a 
cem, onde a primeira senha que um usuário insere 
é um cartão com nome atribuído à primeira caixa� 
O valor de sequência de caracteres da senha é 
protegido porque o computador só precisa ir para 
a caixa com um valor de hash correspondente em 
vez de lembrar toda a sequência de caracteres�
10
Da mesma forma, o computador verificará se a 
sequência de caracteres corresponde ao valor de 
hash atribuído a essa entrada sempre que “P1234” 
for inserido, concedendo acesso de acordo�
A segurança é garantida se “P1234” for o único 
dado de entrada que produz o valor de hash “01”� 
Portanto, mesmo com o melhor algoritmo fazendo 
algum processamento de dados específico, tere-
mos um desempenho ruim se o gerenciamento 
de dados não for otimizado� Assim, recuperar e 
fornecer dados ao algoritmo, bem como salvar 
suas saídas, torna-se um gargalo de desempenho� 
Observemos outro exemplo de função da hash na 
figura a seguir:
Figura 1: Função hash
Informação Valores
Hash
Fox Função
hash DFCD34534
A raposa
vermelha
corre
pelo gelo
A raposa
vermelha
corre
pelo gelo
Função
hash 52ED879E
Função
hash 46042841
Fonte: Adaptado de wikimedia�
11
https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Hash_function.svg/640px-Hash_function.svg.png
Várias técnicas para manter e gerenciar dados 
foram propostas ao longo do tempo� Exemplos 
são matrizes, listas vinculadas e árvores, que 
são estruturas de dados excelentes para vários 
propósitos, mas a complexidade de tempo para 
encontrar e recuperar dados armazenados neles 
é normalmente maior do que em outra estrutura 
de dados: as tabelas hash�
FUNÇÕES DE ESPALHAMENTO
Antes de estudar especificamente as tabelas hash, 
precisamos entender o hash� 
Em resumo, hashing é o processo que recebe uma 
entrada de comprimento variável e produz um valor 
de saída de comprimento fixo, chamado código 
hash ou apenas hash�
Uma função hash é responsável por transformar 
uma entrada de comprimento variável em um 
hash. Não há função hash padrão e isso significa 
que podemos desenvolver as funções de hash de 
acordo com as características gerais esperadas 
das entradas de dados�
É relevante notar que a função hash pode aumentar 
ou diminuir o número de bytes da entrada de com-
primento variável� Assim, se a entrada for maior 
que o código hash, o número de bytes diminuirá� 
Caso contrário, aumentará�
12
As tabelas hash são consideradas associativas, 
o que significa que para cada chave, os dados 
ocorrem no máximo uma vez� As tabelas hash 
nos permitem implementar coisas, como listas 
telefônicas ou dicionários� Nelas armazenamos a 
associação entre um valor (como uma definição 
de dicionário da palavra “carro”) e sua chave (a 
própria palavra “carro”)�
Podemos usar tabelas hash para armazenar, recu-
perar e excluir dados exclusivamente com base em 
sua chave exclusiva� Resumindo, o hashing tem 
várias aplicações em ciência da computação, como 
armazenar e verificar senhas, criar assinaturas de 
mensagens e fornecer estruturas de gerenciamento 
de dados�
Para entender mais sobre a aplicação do hashing, assis-
ta ao vídeo “O que é uma função hash Criptográfica?”, 
disponível em: https://youtu.be/gdgfl5evAUI; “Entenda 
Rápido! O que é Hash?”, disponível em: https://youtu�
be/HMwIQLVM8Iw; 
“Assinatura Digital e Hash - Segurança da Informação”, 
disponível em: https://youtu�be/UlRCVihN3pE� 
As tabelas de dispersão, de espalhamento ou hash, 
são uma das estruturas de dados mais críticas 
SAIBA MAIS
13
https://youtu.be/gdgfl5evAUI
https://youtu.be/HMwIQLVM8Iw
https://youtu.be/HMwIQLVM8Iw
https://youtu.be/UlRCVihN3pE
que todos os desenvolvedores devem dominar� No 
nível da classe, elas nos ajudam a resolver vários 
desafios algorítmicos.
Beneficiadas pela recuperação rápida de dados 
como um ponto forte, as tabelas hash são fun-
damentais para ferramentas e técnicas padrão, 
como armazenamento em cache e indexação de 
banco de dados�
As tabelas hash são estruturas de dados que asso-
ciam chaves específicas a valores correspondentes. 
Essas tabelas geralmente são implementadas 
com uma matriz associativa para armazenar os 
dados� Além disso, elas usam uma função hash 
para calcular em qual ponto da matriz os dados 
devem ser armazenados (o índice)� Observemos 
um exemplo na figura a seguir:
14
Figura 2: Tabela hash simples
Chaves Valores
521-8976
000
001
000
872
873
874
872
872
998
999
521-5030
521-1234
John
Smith
Lisa
Smith
Sam Doe
Fonte: Adaptado de https://upload�wikimedia�org/wiki-
pedia/commons/thumb/b/b6/Hash_table_simple_999�
svg/640px-Hash_table_simple_999�svg�png�
Assim, podemos entender uma tabela hash como 
uma pesquisa de valor-chave� Dada uma chave 
associada a um valor (dados), podemos recupe-
rar o valor correspondente através de uma rápida 
pesquisa na tabela�
Quando nos preocupamos em aprender os meandros 
de uma linguagem, é necessário dominar a base 
algorítmica do desenvolvimento de software, códi-
go em métodos e funções e uma das ferramentas 
15
https://upload.wikimedia.org/wikipedia/commons/thumb/b/b6/Hash_table_simple_999.svg/640px-Hash_table_simple_999.svg.png
https://upload.wikimedia.org/wikipedia/commons/thumb/b/b6/Hash_table_simple_999.svg/640px-Hash_table_simple_999.svg.png
https://upload.wikimedia.org/wikipedia/commons/thumb/b/b6/Hash_table_simple_999.svg/640px-Hash_table_simple_999.svg.png
mais integrais para resolver esses problemas são 
as estruturas de dados�
Como uma das principais estruturas de dados, uma 
tabela hash pode ser usada para armazenar dados 
no formato de valor-chave com acesso direto a 
seus itens constantemente�
Dessa forma, o aspecto mais valioso de uma tabela 
hash sobre outras estruturas de dados abstratas é 
sua velocidade para realizar operações de inserção, 
exclusão e pesquisa�
Para aqueles que não estão familiarizados com 
a complexidade do tempo (notação O-grande), o 
tempo constante é a complexidade de tempo mais 
rápida possível� As tabelas hash podem executar 
quase todos os métodos (exceto lista) muito ra-
pidamente em tempo O(1)�
Por causa dessa eficiência, as tabelas hash são 
bastante úteis em muitos casos de uso� É possível 
notarmos que elas são realmente implementadas 
em vários lugares em suas ferramentas, como 
bancos de dados, caches, bibliotecas de busca 
de dados e assim por diante�
Existem quatro aspectos distintos sobre como 
funcionam as tabelas hash:
 y Com base no armazenamento;
 y Com base nos pares de valor chave;
16
 y Com base em uma função hash;
 y Com base em operações de tabela�
Uma tabela hash é um tipo de dado abstrato que 
depende do uso de um tipo de dado base, como 
uma matriz ou um objeto para armazenar os dados� 
É possível usar qualquer um, mas pequenas impli-
cações de implementação ocorrem dependendo 
da escolha�
Independentemente da estrutura de dados primiti-
va subjacente usada para armazenar dados, para 
armazená-los como um valor em uma tabela hash, 
precisamos de alguma maneira identificá-los de 
forma exclusiva com uma chave�
Às vezes, os dados contêm uma propriedade indi-
vidual que pode naturalmente assumir a responsa-
bilidade pela chave� Por exemplo, se presumirmos 
que um usuário tem um e-mail e um nome de 
usuário, o e-mail ou o nome de usuário podem ser 
usadoscomo a chave se forem garantidos como 
exclusivos� Outras vezes, trabalhamos com dados 
em que a exclusividade é um pouco mais ambígua�
Podemos associar os nomes das pessoas às suas 
informações pessoais com uma tabela hash� Dessa 
forma, os nomes das pessoas são nossas “chaves 
brutas”� Assim, uma função hash processa essas 
chaves para determinar seus índices correspon-
17
dentes na tabela hash, fornecendo acesso direto 
às informações pessoais�
Com o tempo, as tabelas hash tornaram-se muito 
populares no cenário da computação� Assim, dife-
rentes linguagens de programação movimentaram 
esforços para fornecer esse tipo de estrutura de 
dados de forma nativa ou por meio de bibliotecas 
embutidas�
Exemplos de estruturas desenvolvidas são os 
HashMaps em Java, a classe dict (dicionário) em 
Python, a classe map em C++ e o a-list em Lisp.
As tabelas hash são bons exemplos de uma troca 
tempo-espaço. Se o tempo disponível for infinito, 
podemos apenas manter todas as chaves vincula-
das ao mesmo índice e executar uma busca binária 
para recuperar os dados específicos.
Por outro lado, se o espaço for infinito, podemos 
usar a chave completa como o próprio índice, 
tendo quantos buckets de memória individuais 
forem necessários para armazenar os dados cor-
respondentes às chaves�
No entanto, não temos tempo ou espaço infinito no 
mundo real� Assim, eventualmente, lidaremos com 
colisões de hash e compartilhamento de índice�
18
Entenda mais sobre tabelas hash com os “Tabelas 
Hash”, disponível em:
https://youtu�be/sRmazVRHm1M e “Tabelas de Dispersão 
(Hashing)”, disponível em: https://youtu�be/osy1xBefHsU� 
Entendemos que as tabelas hash são essenciais 
em vários aspectos da estrutura de dados, por isso, 
precisamos compreender sobre o funcionamento 
e funções de espalhamento, ou hash�
Hashing é uma maneira de armazenar dados em 
alguma estrutura de dados (geralmente a tabela 
hash é usada) de tal forma que as operações 
básicas sobre esses dados, ou seja, a inserção, 
exclusão e pesquisa possam ser executadas em 
tempo O(1)� 
Lembremos que os dados são armazenados na 
forma de pares chave-valor, ou seja, para cada dado 
atribuímos alguma chave e com base nessa chave 
será realizada a inserção, exclusão e pesquisa de 
seus dados� Desse modo, analisemos aspectos 
pertinentes sobre a versão básica da tabela hash, 
ou seja, a Tabela de Endereço Direto�
A Tabela de Endereço Direto (Direct Address Table) 
é a versão básica da tabela hash, onde usamos 
SAIBA MAIS
19
https://youtu.be/sRmazVRHm1M
https://youtu.be/osy1xBefHsU
uma estrutura simples, tipo array para armazenar 
os dados relacionados a cada chave� 
Por exemplo, se as chaves estiverem no intervalo de 
0 a 99, será possível criar uma tabela de tamanho 
100 e armazenar todos os dados relacionados às 
chaves nessa tabela� Portanto, para armazenar 
dados relacionados à chave com valor 10, será 
possível armazená-los no índice número 10� Da 
mesma forma, para armazenar dados relacionados 
à chave 55, será possível armazená-los no índice 
número 55�
Considerando a abordagem acima, a inserção, 
exclusão e busca serão em O(1)� Analisemos a 
seguir como essas operações ocorrem�
 y Inserção: quando temos alguns pares de valo-
res-chave e desejamos armazená-los na Tabela de 
Endereço Direto, tudo o que precisamos fazer é criar 
uma tabela de tamanho m, onde “m” é o número de 
todas as chaves possíveis� Em seguida, podemos 
armazenar os dados relacionados a cada chave na 
tabela apenas acessando esse índice� Por exem-
plo, se a chave for 5 e o intervalo de chaves puder 
estar entre 0-9, os dados relacionados à chave “5” 
serão armazenados no índice 5 (arr[key] = data) e 
isso pode ser feito em O(1) tempo;
 y Exclusão: para a operação de exclusão, po-
demos acessar o elemento a ser deletado em 
O(1)� Por exemplo, se desejamos excluir os dados 
20
relacionados à chave com valor “5”, já que está 
usando a Tabela de Endereço Direto, arr[5] será o 
local onde os dados serão armazenados� Então, 
basta excluí-lo no tempo O(1);
 y Busca: a operação de pesquisa também pode 
ser realizada em tempo O(1), pois a chave a ser 
pesquisada pode ser encontrada diretamente 
acessando esse índice� Por exemplo, se desejamos 
pesquisar os dados relacionados à chave com valor 
“5”, sabemos que ela será armazenada em arr[5], 
para que possamos obter os dados diretamente 
no tempo O(1)�
Dessa forma, entendemos que a função hash é 
uma função aplicada em uma chave que produz 
um inteiro, que pode ser usado como endereço 
de uma tabela hash� Portanto, podemos usar a 
mesma função hash para acessar os dados da 
tabela hash� Nesse caso, o inteiro retornado pela 
função hash é chamado de chave hash�
Existem vários tipos de funções de hash que são 
usadas para colocar os dados em uma tabela hash, 
verifiquemos algumas delas a seguir: 
 y Método de divisão (Division method): neste 
método, a função hash depende do restante de 
uma divisão;
 y Método do quadrado médio (Mid square me-
thod): neste método, primeiro a chave é quadrada 
21
e, em seguida, a parte do meio do resultado é 
tomada como índice;
 y Método de dobra de dígitos (Digit folding me-
thod): neste método, a chave é dividida em partes 
separadas e, usando algumas operações simples, 
essas partes são combinadas para produzir uma 
chave de hash�
Pensando em todos os aspectos sobre as funções 
de hash, também temos outras características 
marcantes:
 y Deve gerar valores de hash diferentes para a 
string semelhante;
 y É fácil de entender e simples de calcular;
 y Deve produzir as chaves que serão distribuídas 
uniformemente em uma matriz;
 y Um número de colisões deve ser menor ao 
colocar os dados na tabela hash;
 y É considerada perfeita quando faz uso de todos 
os dados de entrada�
Para conhecer mais exemplos e análises sobre funções 
de hash, assista aos vídeos “Criptografia - funções de 
hash, disponível em: https://youtu�be/ZTJEWeWRUkc; “O 
que são funções de hash?”, disponível em: https://youtu.
be/AS_G9LCx6p0 e “Funções de hash e Criptografia”, 
disponível em: https://youtu.be/zJTMLwZrNyw. 
SAIBA MAIS
22
https://youtu.be/ZTJEWeWRUkc
https://youtu.be/AS_G9LCx6p0
https://youtu.be/AS_G9LCx6p0
https://youtu.be/zJTMLwZrNyw
TRATAMENTO DE COLISÕES
Como as funções de hash mapeiam chaves de ta-
manho variável para índices de tamanho fixo, elas 
mapeiam um conjunto infinito para um finito. Dessa 
forma, as colisões eventualmente ocorrerão� Ou 
seja, quando a função hash gera o mesmo índice 
para várias chaves, haverá um conflito (relacionado 
ao valor que deverá ser armazenado no índice)� 
Isso é chamado de colisão de hash e, em dados 
momentos, para resolver a colisão, pode ocorrer 
uma condição de estouro, que tornam a função 
hash inadequada�
Existem muitas tabelas hash com dados que cau-
sam problemas constantemente. Imaginemos um 
cenário em que se aplicarmos uma função hash em 
dois casos diferentes, ela gera o mesmo número 
de índice para os dois casos, mas em ambos os 
itens não podem ir no mesmo lugar, isso é cha-
mado de colisão�
Desse modo, dois objetos idênticos sempre têm os 
mesmos dígitos, enquanto dois objetos desiguais 
nem sempre podem ter dígitos diferentes� Ao colocar 
um objeto na tabela hash, existe a possibilidade de 
que objetos diferentes possam ter um código de 
hash igual, caracterizando, justamente, a colisão� 
Para retificar esta matriz de listas é usada uma 
tabela hash, observemos a seguir:
23
Figura 3: Colisão hash�
Chaves Valores Hash
00
01
02
03
04
05
:
15
John
Smith
Lisa
Sam Doe
Sandra
Dee
Fonte: Adaptado de wikimedia�
Na figura apresentada, verificamos uma colisão das 
setas em vermelho, apontando para o valor “02”� 
Para resolver uma colisão colocando o item em 
outro lugar é a prática chamada de Open Addres-
sing, ou Endereçamento Aberto, que é uma forma 
para resolver as colisões utilizando encadeamento�
Podem ser usadas muitas variedades de técnicas 
para decidir onde colocar um item� Uma técnica 
de endereçamento específicachama-se Linear 
Probing (Sondagem Linear).
Quando o endereço calculado estiver ocupado, 
então a pesquisa linear é usada para encontrar o 
24
https://upload.wikimedia.org/wikipedia/commons/thumb/5/58/Hash_table_4_1_1_0_0_1_0_LL.svg/640px-Hash_table_4_1_1_0_0_1_0_LL.svg.png
próximo bucket disponível� Se a sondagem linear 
terminar e ainda não tiver encontrado uma posição, 
esta poderá circular em torno do início da matriz 
e continuar pesquisando a partir daí�
Quanto mais itens houver em uma tabela hash, 
maiores são as chances de uma colisão� Uma ma-
neira de lidar com isso é tornar a tabela hash maior 
para a quantidade total de dados que se espera�
Ao realizar essa prática, estima-se que cerca de 70% 
da tabela esteja ocupada, com isso, a proporção 
entre o número de itens armazenados e o tama-
nho de um array é conhecido como Load Factor 
(a razão entre o número de registros e o número 
de endereços dentro de uma estrutura de dados)�
Então, em tabelas hash, uma colisão significa que 
a função hash mapeou várias chaves necessárias 
para o mesmo índice e, consequentemente, para 
o mesmo bucket de memória da tabela�
Mesmo que o tamanho da tabela hash seja grande 
o suficiente para acomodar todos os objetos, encon-
trar uma função hash que gere um hash exclusivo 
para cada objeto na tabela é uma tarefa difícil�
Colisões podem ocorrer (a menos que encontremos 
uma função hash perfeita, o que é difícil), mas podem 
ser significativamente reduzidas com a ajuda de 
25
várias técnicas de resolução de colisões� A seguir 
indicaremos e analisaremos as mais relevantes:
 y Open Hashing ou Hash aberto (encadeamento 
separado);
 y Closed Hashing ou Hash fechado (endereça-
mento aberto);
 � Linear Probing ou Sondagem Linear;
 � Quadratic Probing ou Sondagem quadrática;
 � Double Hashing ou Hash duplo�
No Open Hashing ou Hash aberto, as colisões 
são resolvidas usando uma lista de elementos 
para armazenar objetos com a mesma chave 
juntos� Na prática, o tamanho da tabela pode ser 
significativamente grande e a função hash pode 
ser ainda mais complexa� Assim, os dados que 
estão sendo espalhados seriam mais complexos 
e não primitivos, mas a ideia permanece a mesma� 
Essa é uma maneira fácil de implementar o hash, 
mesmo com alguns problemas�
26
Figura 4: Colisão hash
Chaves Valores Hash
000
001
002
253
254
255
151
152
153
154
155
John
Smith
Lisa
Smith
Sam Doe
Ted Baker
Sandra
Dee
Lisa 521-8976
Sam Doe 521-5030
John
Sandra
521-1234
521-9655
418-4165Ted Baker
Fonte: Adaptado de wikimedia�
Na figura apresentada, as colisões foram resol-
vidas por endereçamento aberto com sondagem 
linear, registros no array bucket, chaves e valores 
armazenados na tabela�
O Closed Hashing, ou Hash fechado, é uma técnica 
de resolução de colisão que requer uma tabela 
hash com tamanho fixo e conhecido. Durante a 
inserção, se uma colisão for encontrada, células 
alternativas são tentadas até que um bucket vazio 
seja encontrado� Essa técnica exige que o tamanho 
da tabela hash seja supostamente maior que o 
número de objetos a serem armazenados�
27
https://upload.wikimedia.org/wikipedia/commons/thumb/b/bf/Hash_table_5_0_1_1_1_1_0_SP.svg/640px-Hash_table_5_0_1_1_1_1_0_SP.svg.png
Para encontrar esses buckets vazios podemos 
contar com três métodos, conforme analisamos 
a seguir: 
A ideia de Linear Probing, ou Sondagem Linear, é 
simples. Pegamos uma tabela hash de tamanho fixo 
e toda vez que enfrentamos uma colisão de hash, 
percorremos linearmente a tabela de maneira cíclica 
para encontrar o próximo bucket vazio� Apesar de 
ser fácil de calcular, implementar e fornecer o me-
lhor desempenho de cache, isso afeta o problema 
de clustering (muitos elementos consecutivos são 
agrupados, o que acaba reduzindo a eficiência de 
encontrar elementos ou buckets vazios)�
Quadratic Probing, ou Sondagem quadrática, é o 
método que está entre o bom desempenho do cache 
e do problema de clustering� Apesar de resolver o 
problema de agrupamento de forma significativa, 
pode acontecer que em algumas situações esta 
técnica não encontre nenhum bucket disponível, ao 
contrário da sondagem linear que sempre encontra 
um. Observemos um exemplo na figura a seguir:
28
Figura 5: Sondagem quadrática
Fonte: wikimedia 
Double Hashing, ou Hash duplo, é o método ba-
seado na ideia de que, no caso de uma colisão, 
usamos uma outra função hash com o valor da 
chave, como entrada para descobrir onde no es-
quema de endereçamento aberto os dados devem 
realmente ser colocados�
Para conhecer outros exemplos sobre o tratamento de 
colisões, assista aos vídeos “Estrutura de Dados - Tabela 
Hash - Tratamento de Colisões”, disponível em:
SAIBA MAIS
29
https://upload.wikimedia.org/wikipedia/commons/thumb/e/ee/Quadratic_probing_png.png/640px-Quadratic_probing_png.png
https://youtu�be/eSklGt_70-U e “Tabelas Hash - Tra-
tamento de Colisão”, disponível em: https://youtu�be/
rUR051P-qLg. 
PROBLEMAS ENVOLVENDO 
HASHING
A partir disso, entendemos quais são alguns dos 
possíveis problemas relacionados ao hashing�
Embora as pesquisas de tabela hash usem tempo 
constante em média, o tempo gasto pode ser sig-
nificativo. Avaliar uma boa função hash pode ser 
uma operação lenta� Em particular, se a indexação 
de array simples puder ser usada, isso geralmente 
ocorre de forma mais rápida�
As tabelas hash, em geral, exibem baixa localidade 
de referência, ou seja, os dados a serem acessados 
são distribuídos aparentemente de forma aleatória 
na memória� 
Como as tabelas hash causam padrões de acesso 
que variam, isso pode acionar faltas de cache do 
microprocessador que causam longos atrasos� 
Estruturas de dados compactas, como matrizes, 
pesquisadas com busca linear, podem ser mais 
rápidas se a tabela for relativamente pequena e 
as chaves forem baratas para comparar, como 
chaves inteiras simples� 
30
https://youtu.be/eSklGt_70-U
https://youtu.be/rUR051P-qLg
https://youtu.be/rUR051P-qLg
De acordo com a Lei de Moore, os tamanhos de 
cache estão crescendo exponencialmente e, por-
tanto, o que é considerado “pequeno” pode estar 
aumentando� O ponto de desempenho ideal varia 
de sistema para sistema, por exemplo, um teste no 
Parrot Language Testing mostra que suas tabelas 
hash superam a pesquisa linear em todos os casos, 
exceto nos mais triviais (uma a três entradas)�
Em relação à Lei de Moore, assista aos vídeos “A Lei De 
Moore - Alto Desenvolvimento Tecnológico Previsto 50 
Anos Atrás”, disponível em:
https://youtu.be/PiqqYLJ_gzQ e “A Lei de Moore e o 
desenvolvimento”, disponível em: https://youtu�be/
Y9eVOGLICGA, para conhecer exemplos e entender 
melhor seus métodos� 
As tabelas hash exigem o design de uma função 
hash efetiva para cada tipo de chave, que em muitas 
situações é mais difícil e demorado para projetar 
e depurar do que a mera função de comparação 
necessária para uma árvore de pesquisa binária 
autoequilibrada� Em tabelas hash de endereço aber-
to, é ainda mais fácil criar uma função hash ruim�
Além disso, em algumas aplicações, um hacker 
black hat com conhecimento da função hash pode 
SAIBA MAIS
31
https://youtu.be/PiqqYLJ_gzQ
https://youtu.be/Y9eVOGLICGA
https://youtu.be/Y9eVOGLICGA
fornecer informações a um hash para criar um 
comportamento inadequado, causando colisões 
excessivas e resultando em desempenho ruim (ou 
seja, um ataque de negação de serviço)�
Além de problemas envolvendo hackers e hashing, 
muitos outros são possíveis� 
Para quem quer entender mais sobre os problemas 
relacionados ao hashing, é possível encontrar diver-
sos com exercícios para serem resolvidos, como o 
“Techie Delight” (https://www�techiedelight�com/pt/
hashing-in-data-structure/)�
SAIBA MAIS
32
https://www.techiedelight.com/pt/hashing-in-data-structure/
https://www.techiedelight.com/pt/hashing-in-data-structure/
CONSIDERAÇÕES FINAIS
Nesse e-book, conhecemos os conceitos básicos 
sobre tabelas, entendendo que a tabela de dados 
é a unidade fundamental para trabalhar com pe-
quenasou grandes quantidades de dados� Ela 
é sem dúvida a estrutura de dados mais antiga 
tanto na forma de organizar dados para proces-
samento por máquinas quanto para apresentar 
dados visualmente para humanos� Existem vários 
tipos de tabela, desde as feitas no Excel, até as 
mais complexas usando diferentes linguagens de 
programação, mas o foco de nossas discussões 
foram as tabelas hash�
Compreendemos também os conceitos introdutó-
rios sobre tabelas de espalhamento, justamente, 
as tabelas hash, entendendo que técnicas para 
gerenciar dados com eficiência são tópicos tra-
dicionais em ciência da computação� Além de 
armazenar dados, recuperá-los com eficiência é 
outra preocupação relevante� As tabelas hash são 
estruturas de dados que associam chaves espe-
cíficas a valores correspondentes. Essas tabelas 
geralmente são implementadas com uma matriz 
associativa para armazenar os dados�
Apresentamos diversos conceitos relacionados 
às tabelas de espalhamento� Hashing, que é uma 
maneira de armazenar dados em alguma estrutura 
33
de dados de tal forma que as operações básicas 
sobre esses dados, ou seja, a inserção, exclusão e 
pesquisa possam ser executadas em tempo O(1) e 
os objetivos de uma função de hash, que buscam 
minimizar colisões, proporcionar a distribuição 
uniforme de valores de hash, serem fáceis de 
calcular e resolver quaisquer colisões� 
Tratamos dos aspectos das colisões, compreen-
dendo que uma colisão de hash ocorre quando 
um algoritmo produz o mesmo valor de hash para 
dois valores de entrada diferentes. Idealmente, 
uma boa função de hash deve processar o valor 
de entrada rapidamente, minimizando a possibili-
dade de colisão�
Os programadores usam diferentes tipos de algo-
ritmos de hash, dependendo do nível de segurança 
que desejam, pois existem várias formas de tratar 
colisões e algumas são mais eficazes que outras. 
Por fim, entendemos que podem existir vários pro-
blemas relacionados ao hashing, pois as tabelas 
hash em geral exibem baixa localidade de referência 
e os dados a serem acessados são distribuídos 
de forma aleatória na memória� Devido ao fato 
das tabelas hash causarem padrões de acesso 
que variam, isso pode acionar faltas de cache do 
microprocessador que causam longos atrasos�
34
Referências Bibliográficas 
& Consultadas
A LEI de Moore - alto desenvolvimento 
tecnológico previsto 50 anos atrás� Binário, 30 
jul� 2021� 1 vídeo (4m8s)� Disponível em: https://
www.youtube.com/watch?v=PiqqYLJ_gzQ&ab_
channel=Bin%C3%A1rio � Acesso em: 20 set� 
2022�
A LEI de Moore e o desenvolvimento. 
Tapa da Mão Invisível. 1 vídeo (2m49s). 
Disponível em: https://www�youtube�
com/watch?v=Y9eVOGLICGA&ab_
channel=TapadaM%C3%A3oInvis%C3%ADvel � 
Acesso em: 20 set� 2022� 
ASCENCIO, A. F. G.; ARAÚJO, G. S. Estruturas de 
dados: algoritmos, análise da complexidade e 
implementações em JAVA e C/C++� São Paulo: 
Pearson Prentice Hall, 2010� [Biblioteca Virtual] 
ASSINATURA Digital e Hash - Segurança 
da Informação – Informática. Dicionário 
de Informática. 1 vídeo (6m13s). 
Disponível em: https://www�youtube�
com/watch?v=UlRCVihN3pE&ab_
channel=Dicion%C3%A1riodeInform%C3%A1tica 
� Acesso em: 20 set� 2022� 
https://www.youtube.com/watch?v=PiqqYLJ_gzQ&ab_channel=Bin%C3%A1rio
https://www.youtube.com/watch?v=PiqqYLJ_gzQ&ab_channel=Bin%C3%A1rio
https://www.youtube.com/watch?v=PiqqYLJ_gzQ&ab_channel=Bin%C3%A1rio
https://www.youtube.com/watch?v=Y9eVOGLICGA&ab_channel=TapadaM%C3%A3oInvis%C3%ADvel
https://www.youtube.com/watch?v=Y9eVOGLICGA&ab_channel=TapadaM%C3%A3oInvis%C3%ADvel
https://www.youtube.com/watch?v=Y9eVOGLICGA&ab_channel=TapadaM%C3%A3oInvis%C3%ADvel
https://www.youtube.com/watch?v=UlRCVihN3pE&ab_channel=Dicion%C3%A1riodeInform%C3%A1tica
https://www.youtube.com/watch?v=UlRCVihN3pE&ab_channel=Dicion%C3%A1riodeInform%C3%A1tica
https://www.youtube.com/watch?v=UlRCVihN3pE&ab_channel=Dicion%C3%A1riodeInform%C3%A1tica
AULA 09 Estrutura de Dados - Tabela Hash - 
Tratamento de Colisões� Professor Douglas 
Maioli� 1 vídeo (41m37s)� Disponível em: https://
www.youtube.com/watch?v=eSklGt_70-U&ab_
channel=ProfessorDouglasMaioli � Acesso em: 
20 set� 2022�
AULA 10 - Tabelas Hash. João Paulo 
Leite, 06 jul. 2021. 1 vídeo (59m11s). 
Disponível em: https://www�youtube�
com/watch?v=sRmazVRHm1M&ab_
channel=Jo%C3%A3oPauloLeite � Acesso em: 20 
set� 2022�
BRUNET, J� A� Tabela hash� João Arthur BM, 24 
out� 2019� Disponível em: https://joaoarthurbm�
github�io/eda/posts/hashtable/#:~:text=O%20
m%C3%A9todo%20da%20divis%C3%A3o%20
por,podem%20ter%20o%20mesmo%20hash�
https://acervolima�com/implementando-nossa-
propria-tabela-de-hash-com-encadeamento-
separado-em-java/� Acesso em: 20 set� 2022� 
CRIPTOGRAFIA - Funções Hash. 
Fábrica de Noobs� 1 vídeo (5m9s)� 
Disponível em: https://www�youtube�
com/watch?v=ZTJEWeWRUkc&ab_
channel=F%C3%A1bricadeNoobs � Acesso em: 
20 set� 2022� 
https://www.youtube.com/watch?v=eSklGt_70-U&ab_channel=ProfessorDouglasMaioli
https://www.youtube.com/watch?v=eSklGt_70-U&ab_channel=ProfessorDouglasMaioli
https://www.youtube.com/watch?v=eSklGt_70-U&ab_channel=ProfessorDouglasMaioli
https://www.youtube.com/watch?v=sRmazVRHm1M&ab_channel=Jo%C3%A3oPauloLeite
https://www.youtube.com/watch?v=sRmazVRHm1M&ab_channel=Jo%C3%A3oPauloLeite
https://www.youtube.com/watch?v=sRmazVRHm1M&ab_channel=Jo%C3%A3oPauloLeite
https://www.youtube.com/watch?v=ZTJEWeWRUkc&ab_channel=F%C3%A1bricadeNoobs
https://www.youtube.com/watch?v=ZTJEWeWRUkc&ab_channel=F%C3%A1bricadeNoobs
https://www.youtube.com/watch?v=ZTJEWeWRUkc&ab_channel=F%C3%A1bricadeNoobs
ENTENDA Rápido! O que é Hash? TI & INFO 
Sem Medo Com Roberto Andrade, 21 jul� 2018� 
1 vídeo (3m9s)� Disponível em: https://www�
youtube.com/watch?v=HMwIQLVM8Iw&ab_
channel=TI%26INFOSemMedoComRobertoAndrade. 
Acesso em: 20 set� 2022�
FORBELLONE, A. L. V.; EBERSPÄCHER, H. F. 
Lógica de programação: a construção de 
algoritmos e estruturas de dados� 3� ed� São 
Paulo: Prentice Hall, 2005� [Minha Biblioteca]
FUNÇÕES Hash e Criptografia. Programando 
com Nilo Menezes, 5 dez� 2020� 1 vídeo 
(28m53s)� Disponível em: https://www�
youtube.com/watch?v=zJTMLwZrNyw&ab_
channel=ProgramandocomNiloMenezes � 
Acesso em: 20 set� 2022� 
GRUS, J� Data science do zero: noções 
fundamentais com Python� 2 ed� Rio de Janeiro: 
Alta Books, 2016� [Minha Biblioteca]
HASHING - Problemas de prática. Techie Delight. 
Disponível em: https://www�techiedelight�com/
pt/hashing-in-data-structure/ � Acesso em: 20 
set� 2022� 
MANZANO, J� A� N� G� Algoritmos: lógica 
para desenvolvimento de programação de 
https://www.youtube.com/watch?v=HMwIQLVM8Iw&ab_channel=TI%26INFOSemMedoComRobertoAndrade
https://www.youtube.com/watch?v=HMwIQLVM8Iw&ab_channel=TI%26INFOSemMedoComRobertoAndrade
https://www.youtube.com/watch?v=HMwIQLVM8Iw&ab_channel=TI%26INFOSemMedoComRobertoAndrade
https://www.youtube.com/watch?v=zJTMLwZrNyw&ab_channel=ProgramandocomNiloMenezes
https://www.youtube.com/watch?v=zJTMLwZrNyw&ab_channel=ProgramandocomNiloMenezes
https://www.youtube.com/watch?v=zJTMLwZrNyw&ab_channel=ProgramandocomNiloMenezes
https://www.techiedelight.com/pt/hashing-in-data-structure/
https://www.techiedelight.com/pt/hashing-in-data-structure/
computadores� 29 ed� São Paulo: Érica, 2019� 
[Minha Biblioteca]
O QUE é uma Função Hashing Criptográfica? 
(Exemplo + Propósito)� Whiteboard 
Crypto – Português, 08 mar. 2022. 1 vídeo 
(7m44s)� Disponível em: https://www�
youtube.com/watch?v=gdgfl5evAUI&ab_
channel=WhiteboardCrypto-Portugu%C3%AAs � 
Acesso em: 20 set� 2022�
O QUE são Funções Hash? Criptos, 08 ago. 
2019� 1 vídeo (13m20s)� Disponível em: https://
www.youtube.com/watch?v=AS_G9LCx6p0&ab_
channel=Criptos � Acesso em: 20 set� 2022�
PUGA, S.; RISSETI, G. Lógica de programação e 
estrutura de dados: com aplicações em Java� 
2� ed� São Paulo: Prentice Hall, 2009� [Biblioteca 
Virtual] 
SOUZA, M� A� F� et al� Algoritmos e lógica de 
programação: um texto introdutório para a 
engenharia� 3� ed� São Paulo: Cengage, 2019� 
[Minha Biblioteca] 
TABELAS de Dispersão (Hashing)- Conceitos 
Básicos� Computação com Prof� Foleis, 16 set� 
2020� 1 vídeo (15m32s)� Disponível em: https://
www.youtube.com/watch?v=osy1xBefHsU&ab_
https://www.youtube.com/watch?v=gdgfl5evAUI&ab_channel=WhiteboardCrypto-Portugu%C3%AAs
https://www.youtube.com/watch?v=gdgfl5evAUI&ab_channel=WhiteboardCrypto-Portugu%C3%AAs
https://www.youtube.com/watch?v=gdgfl5evAUI&ab_channel=WhiteboardCrypto-Portugu%C3%AAs
https://www.youtube.com/watch?v=AS_G9LCx6p0&ab_channel=Criptos
https://www.youtube.com/watch?v=AS_G9LCx6p0&ab_channel=Criptos
https://www.youtube.com/watch?v=AS_G9LCx6p0&ab_channel=Criptos
https://www.youtube.com/watch?v=osy1xBefHsU&ab_channel=Computa%C3%A7%C3%A3ocomProf.Foleis
https://www.youtube.com/watch?v=osy1xBefHsU&ab_channel=Computa%C3%A7%C3%A3ocomProf.Foleis
channel=Computa%C3%A7%C3%A3ocomProf�
Foleis � Acesso em: 20 set� 2022� 
TABELAS Hash - Tratamento de Colisão. 
Joaquim Quinteiro Uchôa� 1 vídeo 
(11m39s)� Disponível em: https://www�
youtube.com/watch?v=rUR051P-qLg&ab_
channel=JoaquimQuinteiroUch%C3%B4a � 
Acesso em: 20 set� 2022�
https://www.youtube.com/watch?v=osy1xBefHsU&ab_channel=Computa%C3%A7%C3%A3ocomProf.Foleis
https://www.youtube.com/watch?v=osy1xBefHsU&ab_channel=Computa%C3%A7%C3%A3ocomProf.Foleis
https://www.youtube.com/watch?v=rUR051P-qLg&ab_channel=JoaquimQuinteiroUch%C3%B4a
https://www.youtube.com/watch?v=rUR051P-qLg&ab_channel=JoaquimQuinteiroUch%C3%B4a
https://www.youtube.com/watch?v=rUR051P-qLg&ab_channel=JoaquimQuinteiroUch%C3%B4a
	_heading=h.u3b19ysbev6i
	_heading=h.8833gg8gjohd
	_heading=h.30j0zll
	_GoBack
	Introdução
	Organização Interna
	Aspectos de implementação
	Tabelas de espalhamento (hashing)
	Conceitos de funcionamento
	Funções de espalhamento
	Tratamento de colisões
	Problemas envolvendo hashing
	Considerações finais
	Referências Bibliográficas & Consultadas