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 de cores (string: azul, vermelho, etc.)

Passo 1

Então, a gente tem um exercício que pede para criar uma função de hash para armazenar até 1.000 nomes de cores, como “azul”, “vermelho” e por aí vai. A matéria aqui é sobre tabelas de hash, que são estruturas de dados usadas para armazenar e acessar dados de forma eficiente. Vamos precisar entender como construir uma boa função de hash que distribua bem esses nomes nas posições da tabela, evitando colisões.

Passo 2

Primeiro, vamos lembrar o que é uma função de hash. Basicamente, é uma função que pega uma entrada (no caso, um nome de cor) e retorna um número inteiro que serve como índice na tabela. Esse índice indica onde o dado será armazenado.

Passo 3

Como estamos lidando com strings (os nomes das cores), precisamos converter essas palavras em números. Uma maneira simples de fazer isso é somar os valores de cada letra na palavra. Por exemplo, para a palavra “azul”:
  • a = 1
  • z = 26
  • u = 21
  • l = 12
Somando: 1 + 26 + 21 + 12 = 60

Passo 4

Agora que temos um número para cada palavra, precisamos garantir que ele caiba na nossa tabela de 1.000 posições. Para isso, usamos o operador módulo. A função de hash pode ser definida como:
h(palavra) = (sum valores das <=tras) mod 1000
Então, para “azul”:
h("azul") = 60 mod 1000 = 60
Isso significa que “azul” será armazenado na posição 60 da tabela.

Passo 5

No entanto, pode acontecer de duas palavras diferentes resultarem no mesmo índice, isso é chamado de colisão. Para minimizar isso, podemos usar uma função de hash dupla. A ideia é usar uma segunda função de hash para, quando houver uma colisão, encontrar uma nova posição de forma rápida.
Uma possível segunda função de hash seria:
h2(palavra) = 1 + ((sum valores das <=tras) mod 999)
Isso garante que o passo para a próxima tentativa de posição seja sempre diferente e não nulo.

Passo 6

Então, usando hash duplo, se tivermos uma colisão na primeira tentativa, usamos a segunda função para decidir o quanto avançar na tabela para encontrar uma nova posição vazia.
Por exemplo, se “azul” e “alguma” resultarem no mesmo índice inicial, aplicamos a segunda função para “alguma” encontrar um novo lugar.

Resposta

Uma função de hash para armazenar até 1.000 nomes de cores é:
h(palavra) = (sum valores das <=tras) mod 1000
E, para tratar colisões usando hash duplo:
h2(palavra) = 1 + (sum valores das <=tras mod 999)

Exercícios relacionados