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.)
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:
Então, para “azul”:
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:
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 é:
E, para tratar colisões usando hash duplo: