Suponha uma tabela de hash de tamanho M=10 com endereçamento aberto para armazenar chaves no intervalo [1, 999]. Insira as seguintes chaves nessa tabela: 371, 121,173,203,11,24, nessa ordem, considerando diferentes métodos de resolução de colisões:
(b) Sondagem quadrática, função hash:

Passo 1

O enunciado pede para inserir as chaves 371, 121, 173, 203, 11 e 24 em uma tabela de hash de tamanho M=10 usando endereçamento aberto com sondagem quadrática. O conteúdo é inserção em tabela de hash e vamos usar a função de sondagem quadrática.

Passo 2

A função de sondagem quadrática é dada por:
h(k,i) = (k + i^2) bmod 10
onde k é a chave e i é o número de tentativas de sondagem (começando em 0).

Passo 3

Para inserir 371: com i=0 temos h(371,0) = (371 + 0^2) bmod 10 = 371 bmod 10 = 1. A posição 1 está livre, então colocamos 371 em 1.

Passo 4

Para inserir 121: com i=0 temos h(121,0) = 121 bmod 10 = 1, mas 1 já está ocupada. Tentamos i=1: h(121,1) = (121 + 1^2) bmod 10 = 122 bmod 10 = 2. A posição 2 está livre, então colocamos 121 em 2.

Passo 5

Para inserir 173: com i=0 temos h(173,0) = 173 bmod 10 = 3. A posição 3 está livre, então colocamos 173 em 3.

Passo 6

Para inserir 203: com i=0 temos h(203,0) = 203 bmod 10 = 3, colisão em 3. Com i=1: h(203,1) = (203 + 1^2) bmod 10 = 204 bmod 10 = 4. A posição 4 está livre, então colocamos 203 em 4.

Passo 7

Para inserir 11: com i=0 temos h(11,0) = 11 bmod 10 = 1, colisão; com i=1: h(11,1) = 12 bmod 10 = 2, colisão; com i=2: h(11,2) = (11 + 4) bmod 10 = 15 bmod 10 = 5. A posição 5 está livre, então colocamos 11 em 5.

Passo 8

Para inserir 24: com i=0 temos h(24,0) = 24 bmod 10 = 4, colisão; com i=1: h(24,1) = 25 bmod 10 = 5, colisão; com i=2: h(24,2) = (24 + 4) bmod 10 = 28 bmod 10 = 8. A posição 8 está livre, então colocamos 24 em 8.

Resposta

Índices de 0 a 9: [–, 371, 121, 173, 203, 11, –, –, 24, –]

Exercícios relacionados