Algoritmos e estruturas de

dados II
Tabela Hash
Professora Ana Mara de Oliveira Figueiredo
[Link]@[Link]
 Problema

● Princípio de funcionamento dos métodos de busca

○ Procurar a informação desejada com base na comparação de suas chaves, isto é com base
em algum valor que a compõe

● Problema
○ Algoritmos eficientes necessitam que os elementos estejam armazenados de forma
ordenada

○ Custo ordenação melhor caso é O(N log N)

○ Custo da busca melhor caso é O(log N)

[Link]@[Link]
 Problema

● Custo da comparação de chaves é alto

● O que seria uma operação de busca ideal?
○ Seria aquela que permitisse o acesso direto ao elemento procurado, sem nenhuma etapa de
comparação de chaves

○ Nesse caso, teríamos um custo O(1)

■ Tempo sempre constante de acesso

3

[Link]@[Link]
 Problema

● Uma saída é usar arrays

○ São estruturas que utilizam índices para armazenar informações

○ Permite acessar uma determinada posição com custo O(1)

● Problema
○ Arrays não possuem nenhum mecanismo que permita calcular a posição onde uma
informação está armazenada

○ A operação de busca não é O(1) 4

[Link]@[Link]
 Problema

● Precisamos do tempo de acesso do array juntamente com a capacidade de

busca um elemento em tempo constante
● Solução: usar uma tabela hash

[Link]@[Link]
 Tabela Hash

● Também conhecidas como tabelas de indexação ou de espalhamento

○ É uma generalização da ideia de array.

● Idéia central
○ Utilizar uma função, chamada de função de hashing, para espalhar os elementos que
queremos armazenar na tabela.

○ Esse espalhamento faz com que os elementos fiquem dispersos de forma não ordenada
dentro do array que define a tabela
6

[Link]@[Link]
 Tabela Hash

● Exemplo

NULL 0

B 1

A NULL 2

A
NULL
C
B E .

D NULL . 7
NULL .
E
D
C
NULL TABLE_SIZE-1
[Link]@[Link]
 Tabela Hash

● Por que espalhar os elementos melhora a busca?

○ A tabela permite a associar valores a chaves

■ chave: parte da informação que compõe o elemento a ser inserido ou buscado na tabela
■ valor: é a posição (índice) onde o elemento se encontra no array que define a tabela
○ Assim, a partir de uma chave podemos acessar de forma rápida uma determinada posição
do array
■ Na média, essa operação tem custo O(1) 8

[Link]@[Link]
 Tabela Hash

● Vantagens
○ Alta eficiência na operação de busca

■ Caso médio é O(1) enquanto o da busca linear é O(N) e a da busca binária é O(log2 N)
○ Tempo de busca é praticamente independente do número de chaves armazenadas na tabela

○ Implementação simples

[Link]@[Link]
 Tabela Hash

● Infelizmente, esse tipo de implementação também tem suas desvantagens

○ Alto custo para recuperar os elementos da tabela ordenados pela chave.

■ Nesse caso, é preciso ordenar a tabela

○ O pior caso é O(N), sendo N o tamanho da tabela

■ Alto número de colisões

10

[Link]@[Link]
 Tabela Hash

● O que é uma colisão?

○ Uma colisão ocorre quando duas (ou mais) chaves diferentes tentam ocupar a mesma
posição na tabela hash.
■ A colisão de chaves não é algo exatamente ruim, é apenas algo indesejável pois diminui
o desempenho do sistema.

11

[Link]@[Link]
 Tabela Hash

● Exemplo de colisão
○ A tenta ocupar a posição onde B está

NULL 0

B 1

A NULL 2

NULL
NULL
C
B E .
12
D NULL .

NULL .
E
D
C
[Link]@[Link] NULL TABLE_SIZE-1
 Aplicações

● A tabela hash pode ser utilizada para

○ busca de elementos em base de dados

■ estruturas de dados em memória, bancos de dados e mecanismos de busca na Internet;

○ verificação de integridade de dados e autenticação de mensagens

■ os dados são enviados juntamente com o resultado da função de hashing

■ Quem receber os dados recalcula a função de hashing usando os dados recebidos e
compara o resultado obtido com o que ele recebeu.
13

■ Resultados diferentes: erro de transmissão

[Link]@[Link]
 Aplicações

● A tabela hash pode ser utilizada para

○ armazenamento de senhas com segurança

■ a senha não é armazenada no servidor, mas sim o resultado da função de hashing

○ implementação da tabela de símbolos dos compiladores

○ Criptografia

■ MD5 e família SHA (Secure Hash Algorithm).

14

[Link]@[Link]
 TAD Tabela Hash

15

[Link]@[Link]
 TAD Tabela Hash

● Importante
○ Por questões de desempenho, a tabela irá armazenar apenas o endereço para a estrutura
que contém os dados e não os dados em si

○ Isso evita o gasto excessivo de memória

○ A medida que os elementos são inseridos na tabela, nós realizamos a alocação daquele
único elemento

16

[Link]@[Link]
 TAD Tabela Hash

● Criando a tabela

17

[Link]@[Link]
 Tamanho da Tabela Hash

● O ideal é escolher um número primo e evitar valores que sejam uma

potência de dois
○ Número primo

■ reduz a probabilidade de colisões, mesmo que a função de hashing utilizada não seja
muito eficaz

○ Potência de dois

■ melhora a velocidade, mas pode aumentar os problemas de colisão se estivermos

18
utilizando uma função de hashing mais simples

[Link]@[Link]
 TAD Tabela Hash

● Destruindo a tabela

19

[Link]@[Link]
 Função de Hashing

● Inserção e busca: é necessário calcular a posição dos dados dentro da

tabela.

● Função de Hashing
○ Calcula a posição a partir de uma chave escolhida a partir dos dados manipulados

20

FUNÇÃO
CHAVE POSIÇÃO
HASHING

[Link]@[Link]
 Função de Hashing

● Função de Hashing
○ É extremamente importante para o bom desempenho da tabela.

○ Ela é responsável por distribuir as informações de forma equilibrada pela tabela hash

21

FUNÇÃO
CHAVE POSIÇÃO
HASHING

[Link]@[Link]
 Função de Hashing

● Exemplo de funcionamento

B 1

A 2
CHAVE POSIÇÃO A
B
FUNÇÃO
C E .
HASHING .
D 22
.
E D
C
TABLE_SIZE-1

[Link]@[Link]
 Função de Hashing

● Para um bom funcionamento, deve satisfazer às seguintes condições

○ Ser simples e barata de se calcular

○ Garantir que valores diferentes produzem posições diferentes

○ Gerar uma distribuição equilibrada dos dados na tabela

■ Cada posição da tabela tem a mesma chance de receber uma chave (máximo
espalhamento)

23

[Link]@[Link]
 Função de Hashing

● Sua implementação depende do conhecimento prévio da natureza e

domínio da chave a ser utilizada
○ Exemplo: utilizar apenas três dígitos do número de telefone de uma pessoa para
armazená-lo na tabela.
■ Neste caso, seria melhor usar os três últimos dígitos do que os três primeiros, pois os
primeiros costumam se repetir com maior frequência e iriam gerar posições iguais na
tabela.
■ Assim, o ideal é usar um cálculo diferente de Hash para cada tipo de chave. 24

[Link]@[Link]
 Função de Hashing

● Alguns exemplos de função de hashing comumente utilizadas

○ Método da Divisão

○ Método da Multiplicação

○ Método da Dobra

25

[Link]@[Link]
 Função de Hashing

● Método da Divisão
○ Ou método da congruência linear

○ Consiste em calcular o resto da divisão do valor inteiro que representa o elemento pelo
tamanho da tabela, TABLE_SIZE
■ Simples e direta
■ A operação de E bit-a-bit (&) com o valor 0x7FFFFFFF elimina o bit de sinal e evita o
risco de ocorrer um overflow e obtermos um número negativo
26

[Link]@[Link]
 Função de Hashing

● Método da Divisão
○ Apesar de simples, apresenta alguns problemas.

■ Resto da divisão: valores diferentes podem resultar na mesma posição

○ Exemplo

■ O resto da divisão de 11 por 10 e de 21 por 10 são o mesmo valor de posição: 1

■ Uma maneira de reduzir esse tipo de problema é utilizar como tamanho da tabela,
TABLE_SIZE, um número primo
27

[Link]@[Link]
 Função de Hashing

● Método da Multiplicação
○ Também chamado de método da congruência linear multiplicativo

■ Usa uma constante fracionária A, 0 < A < 1, para multiplicar o valor da chave que
representa o elemento
■ Em seguida, a parte fracionária resultante é multiplicada pelo tamanho da tabela para
calcular a posição do elemento

28

[Link]@[Link]
 Função de Hashing

● Método da Multiplicação
○ Exemplo: calcular a posição da chave 123456, usando a constante fracionária A = 0,618 e
que o tamanho da tabela seja 1024

posição = ParteInteira(TABLE_SIZE * ParteFracionária(chave * A))

posição = ParteInteira(1024 * ParteFracionária(123456 * 0,618))

29

posição = ParteInteira(1024 * ParteFracionária(762950,808))

posição = ParteInteira(1024 * 0,808)

[Link]@[Link]
posição = ParteInteira(827,392)
 Função de Hashing

● Método da Dobra
○ Utiliza um esquema de dobrar e somar os dígitos do valor para calcular a sua posição

■ Considera o valor inteiro que representa o elemento como uma sequência de dígitos
escritos num pedaço de papel.
■ Enquanto esse valor for maior que o tamanho da tabela, o papel é dobrado e os dígitos
sobrepostos são somados, desconsiderando-se as dezenas
■ Note que este processo deve ser repetido enquanto os dígitos formarem um número
maior que o tamanho da tabela. 30

[Link]@[Link]
 Função de Hashing

● Método da Dobra 5 2 9 3 6 4 1 0
○ Exemplo
5 2 9 3
6 4 1 0
DOBRAR 6 4 1 0
3 9 2 5
SOMAR
9 3 3 5
9 3 3 5 31

3 5
DOBRAR 3 9
SOMAR
[Link]@[Link] 6 4
 Função de Hashing

● Método da Dobra
○ Pode ser usado com valores binários

■ Utiliza a operação de OU exclusivo

■ Não se usa as operações de E e OU binário pois estas produzem resultados menores e
maiores, respectivamente, que os operandos

32

[Link]@[Link]
 Função de Hashing

● Método da Dobra
○ No caso de valores binários, a dobra é realizada de k em k bits, o que resulta em um valor
de posição entre 0 e 2k+1.
■ Exemplo: queremos calcular a posição do valor 71 (0001000111 em binário), usando k =
5:

33
posição = 00010 “OU exclusivo” 00111
posição = 00101
posição = 5

[Link]@[Link]
 Função de Hashing

● Tratando uma string como chave

○ Podemos optar por calcular um valor numérico a partir dessa string

■ Esse valor pode ser facilmente calculado somando os valores ASCII dos caracteres que
compõem a string

○ O resultado pode então ser utilizado como parâmetro para um função de hashing

34

[Link]@[Link]
 Função de Hashing

● Tratando uma string como chave

○ Por que não devemos simplesmente somar os valores ASCII dos caracteres da string?

■ Porque palavras com letras trocadas irão produzir o mesmo valor e, consequentemente,
uma colisão

○ Exemplo

cama: 99 + 97 + 109 + 97 = 402 35

maca: 109 + 97 + 99 + 97 = 402

[Link]@[Link]
 TAD Tabela Hash

● Inserção e busca sem tratamento de colisão

○ Inserção

■ Calcular a posição da chave no array

■ Alocar espaço para os dados
■ Armazenar os dados na posição calculada

36

[Link]@[Link]
 TAD Tabela Hash

● Inserção sem tratamento de colisão

37

[Link]@[Link]
 TAD Tabela Hash

● Inserção e busca sem tratamento de colisão

○ Busca

■ Calcular a posição da chave no array

■ Verificar se há dados na posição calculada
■ Retornar os dados

38

[Link]@[Link]
 TAD Tabela Hash

● Busca sem tratamento de colisão

39

[Link]@[Link]
 Hashing Universal

● Função de hashing está sujeita ao problema de gerar posições iguais para

chaves diferentes
○ Por se tratar de uma função determinística, ela pode ser manipulada de forma indesejada.

○ Conhecendo a função de hashing, pode-se escolher as chaves de entrada de modo que

todas colidam, diminuindo o desempenho da tabela na busca para O(N)

40

[Link]@[Link]
 Hashing Universal

● Hashing universal é uma estratégia que busca minimizar esse problema de

colisões
○ Basicamente, devemos escolher aleatoriamente (em tempo de execução) a função de
hashing que será utilizada.

○ Para tanto, construimos um conjunto (ou família) de funções de hashing

41

[Link]@[Link]
 Hashing Universal

● Existem várias maneiras diferentes de construir uma família de funções de

hashing.
○ Uma família de funções pode ser facilmente obtida da seguinte forma:

■ Escolha um número primo p. Ele deve ser maior do que qualquer chave k a ser inserida.
■ p também deve ser maior do que o tamanho da tabela, TABLE_SIZE
■ Escolha, aleatoriamente, dois números inteiros, a e b, de tal modo que 0 < a ≤ p e 0 ≤ b
≤p
42

[Link]@[Link]
 Hashing Universal

● Dados os valores p, a, e b, definimos a função de hashing universal como

sendo

○ h(k)a,b = ((ak + b) % p) % TABLE_SIZE

■ Esse tipo de função de hashing universal permite o tamanho da tabela, TABLE_SIZE,

não seja necessariamente primo
■ Além disso, como existem p-1 valores diferentes para o valor de a e p valores possíveis
para b, é possível gerar p(p-1) funções de hashing diferentes. 43

[Link]@[Link]
 Hashing imperfeito e perfeito

● A depender do tamanho da tabela, TABLE_SIZE, e dos valores inseridos,

uma função de hashing pode ser definida como
○ Hashing imperfeito

○ Hashing perfeito

44

[Link]@[Link]
 Hashing imperfeito e perfeito

● Hashing imperfeito
○ Para duas chaves diferentes a saída da função de hashing é a mesma posição na tabela

○ Ou seja, podem ocorrer colisões das chaves

■ A colisão de chaves não é algo exatamente ruim, é apenas algo indesejável pois diminui
o desempenho do sistema
■ De modo geral, muitas tabelas hash fazem uso de alguma outra estrutura de dados para
lidar com o problema da colisão, como veremos adiante.
45

[Link]@[Link]
 Hashing imperfeito e perfeito

● Hashing perfeito
○ Nunca ocorre colisão

■ Chaves diferentes irão sempre produzir posições diferentes

○ No pior caso, as operações de busca e inserção são sempre executadas em tempo
constante, O(1).
■ É utilizado onde a colisão não é tolerável
■ Trata-se de um tipo de aplicação muito especifica, por exemplo, o conjunto de palavras 46
reservadas de uma linguagem de programação. Nesse caso, conhecemos
previamente o conteúdo a ser armazenado na tabela

[Link]@[Link]
 Tratamento de Colisões

● Mundo ideal
○ Hashing perfeito

■ Função de hashing irá sempre fornecer posições diferentes para cada uma das chaves
inseridas

● Mundo real
○ Independente da função de hashing utilizada, a mesma vai retornar a mesma posição para
duas chaves diferentes: colisão!
47

[Link]@[Link]
 Tratamento de Colisões

● A criação de uma tabela hash consiste de duas coisas

○ uma função de hashing

○ uma abordagem para o tratamento de colisões

48

[Link]@[Link]
 Tratamento de Colisões

● Uma escolha adequada do tamanho da tabela pode minimizar as colisões

○ Colisões ocorrem porque temos mais chaves para armazenar do que o tamanho da tabela
suporta

○ Não há espaço suficiente para todas as chaves

49

[Link]@[Link]
 Tratamento de Colisões

● Uma escolha adequada da função de hashing pode minimizar as colisões

○ Escolher uma função que produza um espalhamento uniforme das chaves reduz o número
de colisões
■ Infelizmente, não se pode garantir que as funções de hashing possuam um bom
potencial de espalhamento por que as colisões também são uniformemente distribuídas.
■ Colisões são teoricamente inevitáveis

50

[Link]@[Link]
 Tratamento de Colisões

● Colisões são teoricamente inevitáveis. Por isso, devemos sempre ter uma
abordagem para tratá-las.
○ Existem diversas formas de se tratar a colisão

○ Duas técnicas muito comuns

■ endereçamento aberto
■ encadeamento separado
51

[Link]@[Link]
 Endereçamento Aberto

● Definição
○ Também conhecido como open addressing ou rehash

○ No caso de um colisão, percorrer a tabela hash buscando por uma posição ainda não
ocupada

○ Os elementos são armazenados na própria tabela hash

■ Evita o uso de listas encadeadas

52

[Link]@[Link]
 Endereçamento Aberto

● A tenta ocupar a posição de B

○ Devemos percorrer a tabela até achar uma posição vaga (NULL)

NULL 0

B 1

A NULL 2

NULL
NULL
E .
53
NULL .

NULL .

D
C
[Link]@[Link] NULL TABLE_SIZE-1
 Endereçamento Aberto

● Vantagens
○ Maior número de posições na tabela para a mesma quantidade de memória usada no
encadeamento separado
■ A memória utilizada para armazenar os ponteiros da lista encadeada no encadeamento
separado pode ser aqui usada para aumentar o tamanho da tabela, diminuindo o
número de colisões

54

[Link]@[Link]
 Endereçamento Aberto

● Vantagens
○ Busca é realizada dentro da própria tabela

■ Recuperação mais rápida de elementos

○ Voltada para aplicações com restrições de memória

○ Ao invés de acessarmos ponteiros extras, calculamos a sequência de posições a serem

armazenadas.

55

[Link]@[Link]
 Endereçamento Aberto

● Desvantagens
○ Maior esforço de processamento no cálculo das posições

○ Esse esforço maior se deve ao fato de que, quando uma colisão ocorre, devemos calcular
uma nova posição da tabela
■ Colisões sucessivas

56

[Link]@[Link]
 Endereçamento Aberto

● Se apenas percorrermos o array, teremos colisões sucessivas

NULL 0

B 1

A F 2

G
NULL
E .
57
NULL .

NULL .

D
C
[Link]@[Link] NULL TABLE_SIZE-1
 Encadeamento Separado

● Também conhecido como separate chaining

○ Não procura por posições vagas (valor NULL) dentro do array que define a tabela

○ Armazena dentro de cada posição do array o início de uma lista dinâmica encadeada

■ É dentro dessa lista que serão armazenadas as colisões (elementos com chaves iguais)
para aquela posição do array

58

[Link]@[Link]
 Encadeamento Separado

● Exemplo

0 NULL
1 B
CHAVE POSIÇÃO 2 NULL
A 3
3 A G
B 1
4 NULL
C 9
5 E
D 8
6 NULL
E 5 59
7 NULL
F 8
G 3 8 D F
9 C
10 NULL
[Link]@[Link]
 Encadeamento Separado

● Características
○ A lista dinâmica encadeada mantida em cada posição da tabela pode ser ordenada ou não

○ Lista não ordenada

■ Inserção tem complexidade O(1) no pior caso: basta inserir o elemento no início da lista.
■ Busca tem complexidade O(M) no pior caso: busca linear
○ Desvantagem

■ Quantidade de memória consumida: gastamos mais memória para manter os ponteiros 60

que ligam os diferentes elementos dentro de cada lista

[Link]@[Link]
 Endereçamento Aberto

● Para a realização do cálculo da nova posição após a colisão, existem três

estratégias muito utilizadas
○ Sondagem linear

○ Sondagem quadrática

○ Duplo hash

61

[Link]@[Link]
 Endereçamento Aberto

● Sondagem linear
○ Também conhecida como tentativa linear, espalhamento linear ou rehash linear

○ Tenta espalhar os elementos de forma sequencial a partir da posição calculada utilizando a

função de hashing

62

[Link]@[Link]
 Endereçamento Aberto

● Sondagem linear
○ Funcionamento

■ Primeiro elemento (i = 0) é colocado na posição obtida pela função de hashing: pos

■ Segundo elemento (colisão) é colocado na posição pos+1
■ Terceiro elemento (nova colisão) é colocado na posição pos+2

63

[Link]@[Link]
 Endereçamento Aberto

● Sondagem linear

NULL 0 E 0
CHAVE POSIÇÃO INSERÇÃO
NULL 1
A 2 Posição 2 vazia. Insere elemento
NULL 1

NULL 2 B 6 Posição 6 vazia. Insere elemento A 2

NULL 3 Posição 2 ocupada, procura na próxima C 3

NULL 4 C 2 posição: 3 NULL 4

Posição 3 vazia. Insere elemento
NULL 5
D 10 Posição 10 vazia. Insere elemento
NULL 5

NULL 6 Posição 10 ocupada, procura na próxima B 664

NULL 7 posição. Como a posição 10 é a última, volta NULL 7

E 10
para o início: 0
NULL 8 Posição 0 vazia. Insere elemento NULL 8

NULL 9 NULL 9

NULL 10 D 10

[Link]@[Link]
 Endereçamento Aberto

● Sondagem linear
○ Estratégia simples

○ Apresenta um problema conhecido como agrupamento primário

■ A medida que a tabela hash fica cheia, o tempo para incluir ou buscar um elemento
aumenta
■ A medida que os elementos são inseridos surgem longas sequências de posições
ocupadas
65
■ A ocorrência desses agrupamentos aumenta o tempo de pesquisa, diminuindo o
desempenho

[Link]@[Link]
 Endereçamento Aberto

● Sondagem quadrática
○ Também conhecida como tentativa quadrática, espalhamento quadrático ou rehash
quadrático

○ Tenta espalhar os elementos utilizando uma equação do segundo grau

○ Exemplo

■ pos + (c1 * i) + (c2 * i2)

● pos é a posição obtida pela função de hashing
66
● i é tentativa atual
● c1 e c2 são os coeficientes da equação

[Link]@[Link]
 Endereçamento Aberto

● Sondagem quadrática
○ Funcionamento

■ Primeiro elemento (i = 0) é colocado na posição obtida pela função de hashing: pos

■ Segundo elemento (colisão) é colocado na posição pos + (c1 * 1) + (c2 * 12)
■ Terceiro elemento (nova colisão) é colocado na posição pos + (c1 * 2) + (c2 * 22)

67

[Link]@[Link]
 Endereçamento Aberto

● Sondagem quadrática

Sondagem quadrática

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
68

Sondagem linear

[Link]@[Link]
 Endereçamento Aberto

● Sondagem quadrática
○ Resolve o problema de agrupamento primário

○ Porém, gera outro problema conhecido como agrupamento secundário

■ Todas as chaves que produzam a mesma posição inicial também produzem as mesmas
posições na sondagem quadrática
■ Felizmente, a degradação produzida pelos agrupamentos secundários ainda é menor
que a produzida pelos agrupamentos primários
69

[Link]@[Link]
 Endereçamento Aberto

● Duplo hash
○ Também conhecida como espalhamento duplo

○ Tenta espalhar os elementos utilizando duas funções de hashing:

■ a primeira função de hashing, H1, é utilizada para calcular a posição inicial do elemento
■ a segunda função de hashing, H2, é utilizada para calcular os deslocamentos em
relação a posição inicial (no caso de uma colisão)

70

[Link]@[Link]
 Endereçamento Aberto

● Duplo hash
○ A posição de um novo elemento na tabela hash é obtida como sendo

■ H1 + i * H2
■ onde i é tentativa atual de inserção do elemento
○ É necessário que as duas funções de hashing sejam diferentes.

■ A segunda função de hashing não pode resultar em um valor igual a ZERO pois, neste
caso, não haveria deslocamento
71

[Link]@[Link]
 Endereçamento Aberto

● Duplo hash
○ Funcionamento

■ Primeiro elemento (i = 0) é colocado na posição obtida por H1

■ Segundo elemento (colisão) é colocado na posição H1 + 1 * H2
■ Terceiro elemento (nova colisão) é colocado na posição H1 + 2 * H2

72

[Link]@[Link]
 TAD Tabela Hash

● Inserção e busca com tratamento de colisão

○ Inserção

■ Calcular a posição da chave no array

■ Recalcular a posição enquanto houver colisão (limitar o número de tentativas)
■ Alocar espaço para os dados
■ Armazenar os dados na posição calculada
73

[Link]@[Link]
 TAD Tabela Hash

● Inserção com tratamento de colisão

74

[Link]@[Link]
 TAD Tabela Hash

● Inserção e busca com tratamento de colisão

○ Busca

■ Calcular a posição da chave no array

■ Verificar se há dados na posição calculada e se esses dados combinam com a chave
■ Recalcular a posição enquanto os dados forem diferentes da chave
■ Retornar os dados
75

[Link]@[Link]
 TAD Tabela Hash

● Busca com tratamento de colisão

76

[Link]@[Link]