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
usando sondagem linear. Use a função hash
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.
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
Í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