Qual o conteúdo da tabela de hash resultante da inserção das seguintes chaves (na ordem dada) em uma tabela inicialmente vazia de tamanho M=16 usando sondagem linear. Use a função hash H(k)=11 * k % M para transformar cada letra do alfabeto em um índice da tabela: U N I V E R S I D A D E

Passo 1

Estamos com uma tabela de hash de tamanho M = 16 e queremos inserir as chaves (letras) U, N, I, V, E, R, S, I, D, A, D, E usando sondagem linear. O conteúdo é endereçamento aberto com sondagem linear e a função de hash é H(k) = 11·k % 16, onde atribuiremos A=1, B=2, …, Z=26.

Passo 2

Cada letra vira um número k e calculamos H(k):
U (21): H(U)=11·21 % 16 = 7, N (14): H(N)=11·14 % 16 = 10, I (9): H(I)=11·9 % 16 = 3, V (22): H(V)=11·22 % 16 = 2,
E (5): H(E)=11·5 % 16 = 7, R (18): H®=11·18 % 16 = 6, S (19): H(S)=11·19 % 16 = 1,
D (4): H(D)=11·4 % 16 = 12, A (1): H(A)=11·1 % 16 = 11. D e E repetem esses mesmos valores.

Passo 3

Inserimos U, N, I e V:
  • U → posição 7 livre → insere em 7
  • N → posição 10 livre → insere em 10
  • I → posição 3 livre → insere em 3
  • V → posição 2 livre → insere em 2
    Tabela parcial ocupada em {2:V, 3:I, 7:U, 10:N}.

Passo 4

Inserimos E, R, S e I:
  • E → H=7 ocupado (U) → sondagem → 8 livre → insere em 8
  • R → H=6 livre → insere em 6
  • S → H=1 livre → insere em 1
  • I → H=3 ocupado (I) → sondagem → 4 livre → insere em 4
    Tabela parcial agora tem também {1:S, 4:I, 6:R, 8:E}.

Passo 5

Inserimos D, A, D e E:
  • D → H=12 livre → insere em 12
  • A → H=11 livre → insere em 11
  • D → H=12 ocupado → sondagem → 13 livre → insere em 13
  • E → H=7 ocupado → sondagem 8 (ocupado) → sondagem 9 livre → insere em 9
    Após todas as inserções chegamos à tabela final abaixo.

Resposta

Índice 0: vazio
Índice 1: S
Índice 2: V
Índice 3: I
Índice 4: I
Índice 5: vazio
Índice 6: R
Índice 7: U
Índice 8: E
Índice 9: E
Índice 10: N
Índice 11: A
Índice 12: D
Índice 13: D
Índice 14: vazio
Índice 15: vazio

Exercícios relacionados