Dê uma função de hash para os seguintes casos. Considere somente o caso de tabelas de hash simples ou duplo:
Tabela com máximo de 1.000 nomes (string com nome de pessoas)

Passo 1

Beleza, vamos lá! A questão pede para criar uma função de hash para uma tabela que pode armazenar até 1.000 nomes de pessoas. Isso envolve entender o que é uma função de hash e como ela ajuda a organizar e acessar os dados de forma eficiente. Vamos precisar conhecer os conceitos básicos de tabelas de hash simples e duplas para resolver isso.

Passo 2

Primeiro, vamos lembrar o que é uma função de hash. Basicamente, é uma função que transforma uma entrada (no nosso caso, um nome) em um número inteiro que vai servir como índice na tabela de hash. Esse índice determina onde o nome será armazenado na tabela.

Passo 3

Como nossa tabela tem um máximo de 1.000 posições, precisamos que a função de hash retorne números de 0 a 999. Uma forma simples de fazer isso é somar os valores dos caracteres do nome e usar o resto da divisão por 1.000. Isso garante que o índice fique dentro do limite da tabela.

Passo 4

Vamos detalhar essa função. Primeiro, convertemos cada caractere do nome em seu valor numérico (usando, por exemplo, o código ASCII). Depois, somamos todos esses valores. Por fim, aplicamos o operador de módulo 1.000 para obter o índice final.

Passo 5

Vamos escrever a função em termos matemáticos. Seja $ H(s) $ a função de hash para uma string $ s $:
H(s)
Onde $ s_i $ é o $ i $-ésimo caractere da string $ s $ e $ n $ é o tamanho da string.

Passo 6

Agora, vamos considerar possíveis colisões, que acontecem quando duas strings diferentes resultam no mesmo índice. Podemos resolver isso usando encadeamento simples, onde cada posição da tabela aponta para uma lista de elementos com o mesmo índice, ou usando duplo hashing, que envolve uma segunda função de hash para calcular passos de salto.

Passo 7

Optando por uma tabela de hash simples, implementamos o encadeamento onde cada índice da tabela aponta para uma lista ligada. Quando ocorre uma colisão, simplesmente adicionamos o novo nome à lista existente naquele índice.

Passo 8

Se preferirmos usar duplo hashing, precisamos de uma segunda função de hash $ H_2(s) $ que seja independente da primeira e que nos ajude a determinar o próximo índice a ser tentado em caso de colisão. Por exemplo:
H2(s)
Então, se ocorrer uma colisão, usamos:
H2(s) = 1 + ( sumi=1^n valor(si) ) mod 999 í

Resposta

Portanto, uma função de hash adequada para uma tabela com até 1.000 nomes é:
H(s) = ( sumi=1^n valor(si) ) mod 1000
Essa função soma os valores numéricos de cada caractere do nome e usa o módulo 1.000 para obter um índice entre 0 e 999, garantindo que cada nome seja mapeado para uma posição válida na tabela de hash.

Exercícios relacionados