15

Na pergunta Por que o hashCode() de String em Java usa 31 como multiplicador? fala-se do uso do número 31 como multiplicador. Foi posta uma controvérsia sobre a motivação deste número. De fato ele não é considerado tão bom. Qual seria um número bom? Por quê?

Mais ainda, o que uma função de cálculo hash deve ter para ser considerada boa para uso em uma tabela de espalhamento? Eu sei que ela deve gerar poucas colisões de códigos hash, eu queria saber o que deve ser observado nela para ser considerada boa. Eu já vi muita gente alegando que sua função hash é muito boa, mas são bem diferentes umas das outras, fico pensando se isto é subjetivo, mas não deveria ser, me parece algo bem matemático.

2
  • 1
    Considerando que poucas colisões é uma coisa boa, você precisa perguntar se precisa de reprodutibilidade ou de garantia de não colisão. Se o hash não precisar de reprodutibilidade, fazê-lo em uma função com fator aleatório (que muda a cada evento arbitrário), você impede um ataque baseado em degeneração da tabela de hash. Commented 16/01/2019 às 11:42
  • Mas como garantir não colisão? Aí deixaria de ser um hash.
    – Maniero
    Commented 16/01/2019 às 20:07

1 Resposta 1

1

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:

  • AB45Z
  • AB45Y

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

3
  • 1
    O último parágrafo tem potencial, mas só o que foi postado é uma dica sobre o assunto não uma resposta que responde de fato o que foi pergunto. O resto é enrolação.
    – Maniero
    Commented 18/01/2019 às 9:22
  • Reformulei minha resposta para ser mais concreta.. Não sou nenhum perito no ramo então posso ter falado bobeira, mas espero ter ajudado. Commented 19/01/2019 às 1:34
  • 1
    Eu acho legal o esforço, mas me pareceu um compêndio de idéias esparsas, mais como "tentativas de solução" (que acabam ficando piores do que tirar o hash e por simplesmente um ID) do que realmente uma resposta para a pergunta. Mas vou reler com calma e boa vontade depois pra tentar enxergar o fundamento de cada coisa, antes de chegar numa conclusão definitiva. A parte de transformar em número realmente não me fez sentido, pq tudo "é número" no final, ou tudo é byte, dá na mesma. As representações são só para humanos.
    – Largato
    Commented 5/02/2019 às 18:25

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .