Aula 7 - Tabela Hash_vILFM-convertido

Prévia do material em texto

Estrutura de Dados
Tabela Hash
Estrutura de Dados – Tabela Hash
Prof. Osmar Betazzi Dordal
Objetivos
Embasar os princípios das Estruturas de Dados;
Dialogar sobre a estrutura de dados tabela hash;
Trabalhar com as tabelas hash.
Conteúdos
Manipulação de tabelas hash;
Definições das tabelas hash;
Domínio básico sobre a estrutura de dados tabela hash.
Tabela Hashing
• Uma tabela hashing é uma generalização de um vetor com posições.
• Cada posição na tabela representa um endereço.
• Os elementos a serem armazenados nela possuem um valor-chave que é 
utilizado para calcular o endereço na tabela onde serão alocados.
• A ideia central do Hash é utilizar uma função, aplicada sobre parte da 
informação (chave), para retornar o índice onde a informação deve ou 
deveria estar armazenada.
Tabela Hashing
• Temos uma técnica para o hashing que se chama tentativa linear. 
• Nessa técnica, quando uma chave x deve ser inserida e ocorre uma colisão, 
uma função é utilizada para obter um novo endereço
• ℎ′(𝑥) = (ℎ(𝑥) + 𝑗) 𝑚𝑜𝑑 𝑚, para 1 ≤ 𝑗 ≤ 𝑚 − 1, sendo que ℎ(𝑥) = 𝑥 𝑚𝑜𝑑 𝑚.
• O objetivo é armazenar a chave no endereço consecutivo ℎ(𝑥) + 1, ℎ(𝑥) + 2,… , até 
encontrar uma posição vazia.
• A seguir, um exemplo de tabela hashing implementada com tentativa linear. 
• Neste exemplo, usaremos uma tabela hashing com 8 posições, ou melhor 
tamanho 8.
Tabela Hashing
• A seguir, um exemplo de tabela hashing implementada com tentativa linear. 
• Neste exemplo, usaremos uma tabela hashing com 8 posições, ou melhor 
tamanho 8.
0 L
1 L
2 L
3 L
4 L
5 L
6 L
7 L
Situação Chave
Tabela Hashing
• Primeira operação:
• Tabela hashing está vazia
0 L
1 L
2 L
3 L
4 L
5 L
6 L
7 L
Situação Chave
Tabela Hashing
• Segunda operação:
• Inserção do número 16 na tabela
Situação Chave
16
num
8
tam
0
i
0
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 16%8
𝑝𝑜𝑠 = 0
𝑖 < 𝑡𝑎𝑚 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 0 + 0 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 0 + 0 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 0%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 0%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 0 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 0 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 ′𝐿′ ≠ ′𝐿′𝑎𝑛𝑑 ′𝐿′ ≠ ′𝑅′
𝑉 𝑎𝑛𝑑 𝐹 𝑎𝑛𝑑 𝑉 ⟶ 𝑣𝑒𝑟𝑖𝑓𝑖𝑐𝑎 𝑠𝑒 𝑎 𝑝𝑜𝑠𝑖çã𝑜 𝑒𝑛𝑐𝑜𝑛𝑡𝑟𝑎𝑑𝑎, 𝑖 é 𝑣á𝑙𝑖𝑑𝑎 𝑝𝑎𝑟𝑎 𝑖𝑛𝑠𝑒𝑟çã𝑜
Tabela Hashing
• Segunda operação:
• Número 16 inserido na tabela
Situação Chave
16
num
8
tam
0
i
0
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 16%8
𝑝𝑜𝑠 = 0
𝑉 𝑎𝑛𝑑 𝐹 𝑎𝑛𝑑 𝑉 ⟶ 𝑣𝑒𝑟𝑖𝑓𝑖𝑐𝑎 𝑠𝑒 𝑎 𝑝𝑜𝑠𝑖çã𝑜 𝑒𝑛𝑐𝑜𝑛𝑡𝑟𝑎𝑑𝑎, 𝑖 é 𝑣á𝑙𝑖𝑑𝑎 𝑝𝑎𝑟𝑎 𝑖𝑛𝑠𝑒𝑟çã𝑜
0 < 𝑡𝑎𝑚
0 < 8
𝑉 ⟶ 𝑖𝑛𝑠𝑒𝑟𝑒 𝑜 16 𝑛𝑎 𝑝𝑜𝑠𝑖çã𝑜 0 𝑒 𝑎𝑙𝑡𝑒𝑟𝑎 𝑡𝑎𝑏𝑒𝑙𝑎 0 . 𝑙𝑖𝑣𝑟𝑒 𝑝𝑎𝑟𝑎 ′𝑂′
Tabela Hashing
• Terceira operação:
• Inserção do número 23 na tabela
Situação Chave
23
num
8
tam
0
i
7
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 23%8
𝑝𝑜𝑠 = 7
𝑖 < 𝑡𝑎𝑚 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7 + 0 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7 + 0 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 ′𝐿′ ≠ ′𝐿′𝑎𝑛𝑑 ′𝐿′ ≠ ′𝑅′
𝑉 𝑎𝑛𝑑 𝐹 𝑎𝑛𝑑 𝑉 = 𝐹 ⟶ 𝑣𝑒𝑟𝑖𝑓𝑖𝑐𝑎 𝑠𝑒 𝑎 𝑝𝑜𝑠𝑖çã𝑜 𝑒𝑛𝑐𝑜𝑛𝑡𝑟𝑎𝑑𝑎, 𝑖 é 𝑣á𝑙𝑖𝑑𝑎 𝑝𝑎𝑟𝑎 𝑖𝑛𝑠𝑒𝑟çã𝑜
Tabela Hashing
• Quarta operação:
• Número 23 inserido na tabela
Situação Chave
23
num
8
tam
0
i
7
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 23%8
𝑝𝑜𝑠 = 7
𝑉 𝑎𝑛𝑑 𝐹 𝑎𝑛𝑑 𝑉 = 𝐹 ⟶ 𝑣𝑒𝑟𝑖𝑓𝑖𝑐𝑎 𝑠𝑒 𝑎 𝑝𝑜𝑠𝑖çã𝑜 𝑒𝑛𝑐𝑜𝑛𝑡𝑟𝑎𝑑𝑎, 𝑖 é 𝑣á𝑙𝑖𝑑𝑎 𝑝𝑎𝑟𝑎 𝑖𝑛𝑠𝑒𝑟çã𝑜
0 < 𝑡𝑎𝑚
0 < 8
𝑉 ⟶ 𝑖𝑛𝑠𝑒𝑟𝑒 𝑜 23 𝑛𝑎 𝑝𝑜𝑠𝑖çã𝑜 7 𝑒 𝑎𝑙𝑡𝑒𝑟𝑎 𝑡𝑎𝑏𝑒𝑙𝑎 7 . 𝑙𝑖𝑣𝑟𝑒 𝑝𝑎𝑟𝑎 ′𝑂′
Tabela Hashing
• Quarta operação:
• Inserção do número 41 na tabela
Situação Chave
41
num
8
tam
0
i
1
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 41%8
𝑝𝑜𝑠 = 1
𝑖 < 𝑡𝑎𝑚 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1 + 0 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1 + 0 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 ′𝐿′ ≠ ′𝐿′𝑎𝑛𝑑 ′𝐿′ ≠ ′𝑅′
𝑉 𝑎𝑛𝑑 𝐹 𝑎𝑛𝑑 𝑉 = 𝐹 ⟶ 𝑣𝑒𝑟𝑖𝑓𝑖𝑐𝑎 𝑠𝑒 𝑎 𝑝𝑜𝑠𝑖çã𝑜 𝑒𝑛𝑐𝑜𝑛𝑡𝑟𝑎𝑑𝑎, 𝑖 é 𝑣á𝑙𝑖𝑑𝑎 𝑝𝑎𝑟𝑎 𝑖𝑛𝑠𝑒𝑟çã𝑜
Tabela Hashing
• Quarta operação:
• Número 41 inserido na tabela
Situação Chave
41
num
8
tam
0
i
1
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 41%8
𝑝𝑜𝑠 = 1
𝑉 𝑎𝑛𝑑 𝐹 𝑎𝑛𝑑 𝑉 = 𝐹 ⟶ 𝑣𝑒𝑟𝑖𝑓𝑖𝑐𝑎 𝑠𝑒 𝑎 𝑝𝑜𝑠𝑖çã𝑜 𝑒𝑛𝑐𝑜𝑛𝑡𝑟𝑎𝑑𝑎, 𝑖 é 𝑣á𝑙𝑖𝑑𝑎 𝑝𝑎𝑟𝑎 𝑖𝑛𝑠𝑒𝑟çã𝑜
0 < 𝑡𝑎𝑚
0 < 8
𝑉 ⟶ 𝑖𝑛𝑠𝑒𝑟𝑒 𝑜 41 𝑛𝑎 𝑝𝑜𝑠𝑖çã𝑜 1 𝑒 𝑎𝑙𝑡𝑒𝑟𝑎 𝑡𝑎𝑏𝑒𝑙𝑎 1 . 𝑙𝑖𝑣𝑟𝑒 𝑝𝑎𝑟𝑎 ′𝑂′
Tabela Hashing
• Quinta operação:
• Inserção do número 25 na tabela
Situação Chave
25
num
8
tam
0
i
1
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 25%8
𝑝𝑜𝑠 = 1
𝑖 < 𝑡𝑎𝑚 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1 + 0 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1 + 0 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 ′𝐿′ ≠ ′𝐿′𝑎𝑛𝑑 ′𝐿′ ≠ ′𝑅′
𝑉 𝑎𝑛𝑑 𝑉 𝑎𝑛𝑑 𝑉 = 𝑉 ⟶ 𝑖𝑛𝑐𝑟𝑒𝑚𝑒𝑛𝑡𝑎 𝑖
Tabela Hashing
• Quinta operação:
• Inserção do número 25 na tabela
Situação Chave
25
num
8
tam
1
i
1
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 25%8
𝑝𝑜𝑠 = 1
𝑉 𝑎𝑛𝑑 𝑉 𝑎𝑛𝑑 𝑉 = 𝑉 ⟶ 𝑖𝑛𝑐𝑟𝑒𝑚𝑒𝑛𝑡𝑎 𝑖
Tabela Hashing
• Quinta operação:
• Inserção do número 25 na tabela
Situação Chave
25
num
8
tam
1
i
1
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 25%8
𝑝𝑜𝑠 = 1
𝑖 < 𝑡𝑎𝑚 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1 + 1 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1 + 1 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 2%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 2%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 2 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 2 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 ′𝐿′ ≠ ′𝐿′𝑎𝑛𝑑 ′𝐿′ ≠ ′𝑅′
𝑉 𝑎𝑛𝑑 𝐹 𝑎𝑛𝑑 𝑉 = 𝐹 ⟶ 𝑣𝑒𝑟𝑖𝑓𝑖𝑐𝑎 𝑠𝑒 𝑎 𝑝𝑜𝑠𝑖çã𝑜 𝑒𝑛𝑐𝑜𝑛𝑡𝑟𝑎𝑑𝑎, 𝑖 é 𝑣á𝑙𝑖𝑑𝑎 𝑝𝑎𝑟𝑎 𝑖𝑛𝑠𝑒𝑟çã𝑜
Tabela Hashing
• Quinta operação:
• Número 25 inserido na tabela
Situação Chave
25
num
8
tam
1
i
1
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 25%8
𝑝𝑜𝑠 = 1
𝑉 𝑎𝑛𝑑 𝐹 𝑎𝑛𝑑 𝑉 = 𝐹 ⟶ 𝑣𝑒𝑟𝑖𝑓𝑖𝑐𝑎 𝑠𝑒 𝑎 𝑝𝑜𝑠𝑖çã𝑜 𝑒𝑛𝑐𝑜𝑛𝑡𝑟𝑎𝑑𝑎, 𝑖 é 𝑣á𝑙𝑖𝑑𝑎 𝑝𝑎𝑟𝑎 𝑖𝑛𝑠𝑒𝑟çã𝑜
0 < 𝑡𝑎𝑚
0 < 8
𝑉 ⟶ 𝑖𝑛𝑠𝑒𝑟𝑒 𝑜 25 𝑛𝑎 𝑝𝑜𝑠𝑖çã𝑜 2 𝑒 𝑎𝑙𝑡𝑒𝑟𝑎 𝑡𝑎𝑏𝑒𝑙𝑎 2 . 𝑙𝑖𝑣𝑟𝑒 𝑝𝑎𝑟𝑎 ′𝑂′
Tabela Hashing
• Sexta operação:
• Inserção do número 39 na tabela
Situação Chave
39
num
8
tam
0
i
7
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 39%8
𝑝𝑜𝑠 = 7
𝑖 < 𝑡𝑎𝑚 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
Toda nova inserção i = 0
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7 + 0 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7+ 0 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 ′𝐿′ ≠ ′𝐿′𝑎𝑛𝑑 ′𝐿′ ≠ ′𝑅′
𝑉 𝑎𝑛𝑑 𝑉 𝑎𝑛𝑑 𝑉 = 𝑉 ⟶ 𝑖𝑛𝑐𝑟𝑒𝑚𝑒𝑛𝑡𝑎 𝑖
Tabela Hashing
• Sexta operação:
• Inserção do número 39 na tabela
Situação Chave
39
num
8
tam
1
i
7
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 39%8
𝑝𝑜𝑠 = 7
𝑉 𝑎𝑛𝑑 𝑉 𝑎𝑛𝑑 𝑉 = 𝑉 ⟶ 𝑖𝑛𝑐𝑟𝑒𝑚𝑒𝑛𝑡𝑎 𝑖
Tabela Hashing
• Sexta operação:
• Inserção do número 39 na tabela
Situação Chave
39
num
8
tam
1
i
7
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 39%8
𝑝𝑜𝑠 = 7
𝑖 < 𝑡𝑎𝑚 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7 + 1 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7 + 1 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 8%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 8%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 0 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 0 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 ′𝐿′ ≠ ′𝐿′𝑎𝑛𝑑 ′𝐿′ ≠ ′𝑅′
𝑉 𝑎𝑛𝑑 𝑉 𝑎𝑛𝑑 𝑉 = 𝑉 ⟶ 𝑖𝑛𝑐𝑟𝑒𝑚𝑒𝑛𝑡𝑎 𝑖
Tabela Hashing
• Sexta operação:
• Inserção do número 39 na tabela
Situação Chave
39
num
8
tam
2
i
7
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 39%8
𝑝𝑜𝑠 = 7
𝑉 𝑎𝑛𝑑 𝑉 𝑎𝑛𝑑 𝑉 = 𝑉 ⟶ 𝑖𝑛𝑐𝑟𝑒𝑚𝑒𝑛𝑡𝑎 𝑖
Tabela Hashing
• Sexta operação:
• Inserção do número 39 na tabela
Situação Chave
39
num
8
tam
2
i
7
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 39%8
𝑝𝑜𝑠 = 7
𝑖 < 𝑡𝑎𝑚 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7 + 2 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7 + 2 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 9%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 9%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 ′𝐿′ ≠ ′𝐿′𝑎𝑛𝑑 ′𝐿′ ≠ ′𝑅′
Tabela Hashing
• Sexta operação:
• Inserção do número 39 na tabela
Situação Chave
39
num
8
tam
2
i
7
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 39%8
𝑝𝑜𝑠 = 7
0 < 8 𝑎𝑛𝑑 ′𝐿′ ≠ ′𝐿′𝑎𝑛𝑑 ′𝐿′ ≠ ′𝑅′
𝑉 𝑎𝑛𝑑 𝑉 𝑎𝑛𝑑 𝑉 = 𝑉 ⟶ 𝑖𝑛𝑐𝑟𝑒𝑚𝑒𝑛𝑡𝑎 𝑖
Tabela Hashing
• Sexta operação:
• Inserção do número 39 na tabela
Situação Chave
39
num
8
tam
3
i
7
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 39%8
𝑝𝑜𝑠 = 7
𝑉 𝑎𝑛𝑑 𝑉 𝑎𝑛𝑑 𝑉 = 𝑉 ⟶ 𝑖𝑛𝑐𝑟𝑒𝑚𝑒𝑛𝑡𝑎 𝑖
Tabela Hashing
• Sexta operação:
• Inserção do número 39 na tabela
Situação Chave
39
num
8
tam
3
i
7
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 39%8
𝑝𝑜𝑠 = 7
𝑖 < 𝑡𝑎𝑚 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7 + 3 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7 + 3 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 10%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 10%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 2 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 2 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 ′𝐿′ ≠ ′𝐿′𝑎𝑛𝑑 ′𝐿′ ≠ ′𝑅′
Tabela Hashing
• Sexta operação:
• Inserção do número 39 na tabela
Situação Chave
39
num
8
tam
3
i
7
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 39%8
𝑝𝑜𝑠 = 7
0 < 8 𝑎𝑛𝑑 ′𝐿′ ≠ ′𝐿′𝑎𝑛𝑑 ′𝐿′ ≠ ′𝑅′
𝑉 𝑎𝑛𝑑 𝑉 𝑎𝑛𝑑 𝑉 = 𝑉 ⟶ 𝑖𝑛𝑐𝑟𝑒𝑚𝑒𝑛𝑡𝑎 𝑖
Tabela Hashing
• Sexta operação:
• Inserção do número 39 na tabela
Situação Chave
39
num
8
tam
4
i
7
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 39%8
𝑝𝑜𝑠 = 7
𝑉 𝑎𝑛𝑑 𝑉 𝑎𝑛𝑑 𝑉 = 𝑉 ⟶ 𝑖𝑛𝑐𝑟𝑒𝑚𝑒𝑛𝑡𝑎 𝑖
Tabela Hashing
• Sexta operação:
• Inserção do número 39 na tabela
Situação Chave
39
num
8
tam
4
i
7
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 39%8
𝑝𝑜𝑠 = 7
𝑖 < 𝑡𝑎𝑚 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7 + 4 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7 + 4 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 11%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 11%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 3 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 3 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 ′𝐿′ ≠ ′𝐿′𝑎𝑛𝑑 ′𝐿′ ≠ ′𝑅′
Tabela Hashing
• Sexta operação:
• Inserção do número 39 na tabela
Situação Chave
39
num
8
tam
4
i
7
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 39%8
𝑝𝑜𝑠 = 7
𝑉 𝑎𝑛𝑑 𝐹 𝑎𝑛𝑑 𝑉 ⟶ 𝑣𝑒𝑟𝑖𝑓𝑖𝑐𝑎 𝑠𝑒 𝑎 𝑝𝑜𝑠𝑖çã𝑜 𝑒𝑛𝑐𝑜𝑛𝑡𝑟𝑎𝑑𝑎, 𝑖 é 𝑣á𝑙𝑖𝑑𝑎 𝑝𝑎𝑟𝑎 𝑖𝑛𝑠𝑒𝑟çã𝑜
0 < 8 𝑎𝑛𝑑 ′𝐿′ ≠ ′𝐿′𝑎𝑛𝑑 ′𝐿′ ≠ ′𝑅′
Tabela Hashing
• Sexta operação:
• Número 39 inserido na tabela
Situação Chave
39
num
8
tam
4
i
7
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 39%8
𝑝𝑜𝑠 = 7
𝑉 𝑎𝑛𝑑 𝐹 𝑎𝑛𝑑 𝑉 ⟶ 𝑣𝑒𝑟𝑖𝑓𝑖𝑐𝑎 𝑠𝑒 𝑎 𝑝𝑜𝑠𝑖çã𝑜 𝑒𝑛𝑐𝑜𝑛𝑡𝑟𝑎𝑑𝑎, 𝑖 é 𝑣á𝑙𝑖𝑑𝑎 𝑝𝑎𝑟𝑎 𝑖𝑛𝑠𝑒𝑟çã𝑜
0 < 𝑡𝑎𝑚
0 < 8
𝑉 ⟶ 𝑖𝑛𝑠𝑒𝑟𝑒 𝑜 39 𝑛𝑎 𝑝𝑜𝑠𝑖çã𝑜 3 𝑒 𝑎𝑙𝑡𝑒𝑟𝑎 𝑡𝑎𝑏𝑒𝑙𝑎 3 . 𝑙𝑖𝑣𝑟𝑒 𝑝𝑎𝑟𝑎 ′𝑂′
Tabela Hashing
• Sétima operação:
• Remoção do número 23 na tabela
Situação Chave
23
num
8
tam
0
i
7
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 23%8
𝑝𝑜𝑠 = 7
Toda nova inserção i = 0
Tabela Hashing
• Sétima operação:
• Remoção do número 23 na tabela
Situação Chave
23
num
8
tam
0
i
7
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 23%8
𝑝𝑜𝑠 = 7
𝑖 < 𝑡𝑎𝑚 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7 + 0 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7 + 0 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
0 < 8 𝑎𝑛𝑑 ′𝐿′ ≠ ′𝐿′𝑎𝑛𝑑 ′𝐿′ ≠ ′𝑅′
𝑉 𝑎𝑛𝑑 𝑉 𝑎𝑛𝑑 𝐹 = 𝐹 ⟶ 𝑣𝑒𝑟𝑖𝑓𝑖𝑐𝑎 𝑠𝑒 𝑎 𝑝𝑜𝑠𝑖çã𝑜 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 𝑒𝑠𝑡á 𝑎 𝑐ℎ𝑎𝑣𝑒 𝑒 𝑠𝑒 𝑒𝑠𝑡𝑎 𝑗á 𝑓𝑜𝑖 𝑟𝑒𝑚𝑜𝑣𝑖𝑑𝑎
Tabela Hashing
• Sétima operação:
• Remoção do número 23 na tabela
Situação Chave
23
num
8
tam
0
i
7
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 23%8
𝑝𝑜𝑠 = 7
𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑐ℎ𝑎𝑣𝑒 = 𝑛𝑢𝑚 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
𝑡𝑎𝑏𝑒𝑙𝑎 7 + 0 %8 . 𝑐ℎ𝑎𝑣𝑒 = 𝑛𝑢𝑚 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7 + 0 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
𝑡𝑎𝑏𝑒𝑙𝑎 7 . 𝑐ℎ𝑎𝑣𝑒 = 𝑛𝑢𝑚 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 7 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
23 = 23 𝑎𝑛𝑑 ′𝑂′ ≠ ′𝑅′
𝑉 𝑎𝑛𝑑 𝑉 = 𝑉 ⟶ 𝑟𝑒𝑚𝑜𝑣𝑒 𝑜 23 𝑑𝑎 𝑝𝑜𝑠𝑖çã𝑜 7 𝑎𝑙𝑡𝑒𝑟𝑎𝑛𝑑𝑜 𝑡𝑎𝑏𝑒𝑙𝑎 7 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 𝑝𝑎𝑟𝑎 ′𝑅′
Tabela Hashing
• Sétima operação:
• Número 23 removida da tabela
Situação Chave
23
num
8
tam
0
i
7
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 23%8
𝑝𝑜𝑠 = 7
Tabela Hashing
• Sétima operação:
• Remoção do número 25 na tabela
Situação Chave
25
num
8
tam
0
i
1
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 25%8
𝑝𝑜𝑠 = 1
Tabela Hashing
• Sétima operação:
• Remoção do número 25 na tabela
Situação Chave
25
num
8
tam
0
i
1
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 25%8
𝑝𝑜𝑠 = 1
𝑖 < 𝑡𝑎𝑚 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑐ℎ𝑎𝑣𝑒 ≠ 𝑛𝑢𝑚
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1 + 0 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1 + 0 %8 . 𝑐ℎ𝑎𝑣𝑒 ≠ 𝑛𝑢𝑚
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1%8 . 𝑐ℎ𝑎𝑣𝑒 ≠ 𝑛𝑢𝑚
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1 . 𝑐ℎ𝑎𝑣𝑒 ≠ 25
0 < 8 𝑎𝑛𝑑 ′𝑂′ ≠ ′𝐿′𝑎𝑛𝑑 41 ≠25
𝑉 𝑎𝑛𝑑 𝑉 𝑎𝑛𝑑 𝑉 = 𝑖𝑛𝑐𝑟𝑒𝑚𝑒𝑛𝑡𝑎 𝑖
Tabela Hashing
• Sétima operação:
• Remoção do número 25 na tabela
SituaçãoChave
25
num
8
tam
1
i
1
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 25%8
𝑝𝑜𝑠 = 1
𝑖 < 𝑡𝑎𝑚 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑐ℎ𝑎𝑣𝑒 ≠ 𝑛𝑢𝑚
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1 + 1 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1 + 1 %8 . 𝑐ℎ𝑎𝑣𝑒 ≠ 𝑛𝑢𝑚
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 2%8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 2%8 . 𝑐ℎ𝑎𝑣𝑒 ≠ 𝑛𝑢𝑚
0 < 8 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 2 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝐿′𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 2 . 𝑐ℎ𝑎𝑣𝑒 ≠ 25
0 < 8 𝑎𝑛𝑑 ′𝑂′ ≠ ′𝐿′𝑎𝑛𝑑 25 ≠25
𝑉 𝑎𝑛𝑑 𝑉 𝑎𝑛𝑑 𝐹 = 𝑣𝑒𝑟𝑖𝑓𝑖𝑐𝑎 𝑠𝑒 𝑎 𝑝𝑜𝑠𝑖çã𝑜 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 𝑒𝑠𝑡á 𝑎 𝑐ℎ𝑎𝑣𝑒 𝑒 𝑠𝑒 𝑒𝑠𝑡𝑎 𝑗𝑎 𝑓𝑜𝑖 𝑟𝑒𝑚𝑜𝑣𝑖𝑑𝑎
Tabela Hashing
• Sétima operação:
• Número 25 removida da tabela
Situação Chave
25
num
8
tam
1
i
1
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 25%8
𝑝𝑜𝑠 = 1
𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑐ℎ𝑎𝑣𝑒 = 𝑛𝑢𝑚 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 𝑝𝑜𝑠 + 𝑖 %𝑡𝑎𝑚 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
𝑡𝑎𝑏𝑒𝑙𝑎 1 + 1 %8 . 𝑐ℎ𝑎𝑣𝑒 = 𝑛𝑢𝑚 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 1 + 1 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
𝑡𝑎𝑏𝑒𝑙𝑎 2 . 𝑐ℎ𝑎𝑣𝑒 = 𝑛𝑢𝑚 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 2 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
25 = 25 𝑎𝑛𝑑 ′𝑂′ ≠ ′𝑅′
𝑉 𝑎𝑛𝑑 𝑉 = 𝑉 ⟶ 𝑟𝑒𝑚𝑜𝑣𝑒 𝑜 25 𝑑𝑎 𝑝𝑜𝑠𝑖çã𝑜 2 𝑎𝑙𝑡𝑒𝑟𝑎𝑛𝑑𝑜 𝑡𝑎𝑏𝑒𝑙𝑎 2 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 𝑝𝑎𝑟𝑎 ′𝑅′
𝑡𝑎𝑏𝑒𝑙𝑎 2 %8 . 𝑐ℎ𝑎𝑣𝑒 = 𝑛𝑢𝑚 𝑎𝑛𝑑 𝑡𝑎𝑏𝑒𝑙𝑎 2 %8 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 ≠ ′𝑅′
Tabela Hashing
• Sétima operação:
• Número 25 removida da tabela
Situação Chave
25
num
8
tam
1
i
1
pos 𝑝𝑜𝑠 = 𝑛𝑢𝑚%𝑡𝑎𝑚
𝑝𝑜𝑠 = 25%8
𝑝𝑜𝑠 = 1
𝑉 𝑎𝑛𝑑 𝑉 = 𝑉 ⟶ 𝑟𝑒𝑚𝑜𝑣𝑒 𝑜 25 𝑑𝑎 𝑝𝑜𝑠𝑖çã𝑜 2 𝑎𝑙𝑡𝑒𝑟𝑎𝑛𝑑𝑜 𝑡𝑎𝑏𝑒𝑙𝑎 2 . 𝑠𝑖𝑡𝑢𝑎𝑐𝑎𝑜 𝑝𝑎𝑟𝑎 ′𝑅′
Tabela Hashing Tentativa Quadrática
• Na tentativa linear, as chaves que colidem geram os chamados 
agrupamentos primários, o que aumenta o tempo de busca.
• Temos, também, a tentativa quadrática (material na rota de estudo).
• Por fim, temos a tabela hashing implementada com lista.
• Neste tipo de implementação, a tabela hashing é um vetor com 𝑚 posições, 
sendo que cada posição possui um ponteiro para uma lista encadeada, onde 
estarão contidos todos os elementos que possuem o mesmo endereço 
mapeado.
Tabela Hashing com Lista
• Por fim, temos a tabela hashing implementada com lista.
• Neste tipo de implementação, a tabela hashing é um vetor com 𝑚 posições, 
sendo que cada posição possui um ponteiro para uma lista encadeada onde 
estarão contidos todos os elementos que possuem o mesmo endereço 
mapeado.
Tabela Hashing com Lista
• Por fim, temos a tabela hashing implementada com lista.
• Neste tipo de implementação, a tabela hashing é um vetor com 𝑚 posições, 
sendo que cada posição possui um ponteiro para uma lista encadeada onde 
estarão contidos todos os elementos que possuem o mesmo endereço 
mapeado.
REFERÊNCIAS
1. Estruturas de Dados, Algoritmos, análise da complexidade e 
implementações em JAVA e C/C++; Ana Fernanda Gomes Ascencio e 
Graziela Santos de Araújo; Person Prentice Hall, 2010; ISBN: 978-85-7605-
881-6.
2. Lógica de Programação e Estrutura de Dados, com aplicação em Java; 2ª 
Edição; Sandra Puga e Gerson Rissetti; Person Prentice Hall, 2008.
Bom Estudo!