Suponha uma tabela de hash de tamanho
com endereçamento aberto para armazenar chaves no intervalo [1, 999]. Insira as seguintes chaves nessa tabela: 371,
, nessa ordem, considerando diferentes métodos de resolução de colisões:
(b) Sondagem quadrática, função hash:
(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:
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
. A posição 1 está livre, então colocamos 371 em 1.
Passo 4
Para inserir 121: com i=0 temos
, mas 1 já está ocupada. Tentamos i=1:
. A posição 2 está livre, então colocamos 121 em 2.
Passo 5
Para inserir 173: com i=0 temos
. A posição 3 está livre, então colocamos 173 em 3.
Passo 6
Para inserir 203: com i=0 temos
, colisão em 3. Com i=1:
. A posição 4 está livre, então colocamos 203 em 4.
Passo 7
Para inserir 11: com i=0 temos
, colisão; com i=1:
, colisão; com i=2:
. A posição 5 está livre, então colocamos 11 em 5.
Passo 8
Para inserir 24: com i=0 temos
, colisão; com i=1:
, colisão; com i=2:
. A posição 8 está livre, então colocamos 24 em 8.
Resposta
Índices de 0 a 9: [–, 371, 121, 173, 203, 11, –, –, 24, –]