Bom você precisa saber com que valores está trabalhando primeiro, meu hash vai receber uma palavra ou um numero?.
Digamos que seu hash receba uma palavra.
Você precisa transformar está palavra em um numero.
Para fazer isso você precisa calcular o valor de cada caractere.
Alguns exemplos:
- Calcular valores usando a tabela ASCII;
- Calular valores usando uma pré tabela similar customizada tipo um override da ASCII;
- Calcular valores usando hex da UTF-8;
- Calular valores usando Base64;
Algumas coisas que você pode fazer enquanto retorna os valores de cada carectere:
Imagine que na função lercaractere(char c) retorna um inteiro.
- Operações comuns (Dividir, Multiplicar, Subtrair ou Somar por k)
- Operações avançadas como Potencia, Fatoração de um Numero Inteiro.
- Operação de conversão de base ex: x10 para x16.
- Você tambem pode elevar a n e pegar um pedaço do resultado.
Importante gravar a posição de cada caracter de uma palavra.
Imagine o seguinte caso:
Se você pegar o valor de cada caracter usando por exemplo ASCII e apenas somar eles.
- el = 8 + 10 = 18
- le = 10 + 8 = 18
| le | el | => terão o mesmo resultado.
uma solução pode ser :
- calc = (c1)2 * (c1 / c2) * k;
- k = algum numero primeiro como 27,31..7243 (no exemplo uso 31);
- c1 = character posição 1;
- c2 = character posiçao 2
- le = (10)2 * (10 / 8) * k = 3875
- el = (8)2 * (8 / 10) * k = 1587
Valores Inteiros Gerando os Indices
Bom nesse momento sua string deve retornar um resultado no exemplo acima:
Imagine que estamos trabalhando com a palvra el cujo valor é 1587, então agora vamos enviar este valor para nossa função hash.
Podemos utilizar alguns metodos:
Resto da Divisão -> (( el Bitwise AND 0x7FFFF) % Tamanho_da_tabela));
Multplicação -> ( (el * Random(1)) * Tamanho_da_tabela));
Expontencial
Fatoração de Inteiros
Aqui você pode trocar a base dos Numeros mais uma vez talvez. XD
Tratamento de Colisão
Para tratar colisões você pode rodar um função que reserva um pedaço do hash evitando a colisão... exemplo:
Esses dois hash não colidiram por uma casa, nesse caso a disperção do algoritmo é ruim pois os hash gerados são muito parecidos, mas e se tivesse como reservar um pedaço do hash imagine o no mesmo exemplo que reservamos AB4.
Antes de gerar o hash então faremos um leitura verificando espaços reservados e se todos fossem ocupados poderiamos por exemplo dobrar o tamanho da tabela isso nos daria outro valor e possivelmente outro hash.
O java faz algo parecido no hash map porém ele dobra quando todas as casas da tabela forem preenchidas.
Tratamento de Colisão 2.
Uma outra maneira de evitar colisão é usar mais parametros na hora de gerar o hash exemplo:
- Data e Hora atual com nano segundos.
- Algum Dado como nome do usuario + senha.
- Pi, E, ou PHI * Random(1);
Observaçoes :
- Random(1) = numero randomico entre 0 e 1;
- 0x7FFFF = ao binario 1111111111111111111
- Bitwise AND = função para retornar um novo valor atravez de dois valores.
Legal dar uma olha em:
- Princípio da casa dos pombos.
- Congruência Linear.
- Teorema chinês do resto
- Pseudoaleatoriedade