Classificação da função hash

9

Na internet, me deparei com esta pergunta:

Classifique as funções de hash com base nos vários métodos pelos quais o valor da chave é encontrado.

com respostas como

  • Método direto
  • Método de subtração
  • Método de divisão de módulos
  • Método de extração de dígitos
  • Método do meio do quadrado
  • Método de dobramento
  • Método pseudo-aleatório

o que acho estranho. Eu acho que sei muito sobre hash, mas isso é algo sem sentido para mim, alguém poderia explicar?

maaartinus
fonte

Respostas:

4

São métodos de transformar um código hash em um índice da matriz que contém os valores. Digamos que você tenha um código de hash 0x12345678. Um número muito grande e é improvável que você tenha uma matriz desse tamanho. Se você pode apenas fazer

Value = array[0x12345678];

E ser feito (método direto).

Caso contrário, você tem uma maneira de transformar esse valor em um que se ajuste ao tamanho da matriz enquanto tenta evitar muitas colisões. Os termos usados ​​provavelmente também são conhecidos por outros nomes, mas, por exemplo, você pode apenas mascarar os bits mais altos do código de hash

Value = array[hashcode & 0xffff];

Ou modifique o hashcode contra o tamanho da matriz

Value = array[hashcode % array.size()]; // modulo division

Etc etc

Editar: este link pode ajudar

James
fonte
Obrigado, é isso - o link parece ser a fonte desse ***. Ainda não faz sentido, pois eles misturam muitas coisas: 1. computando o hashCode a partir de uma chave (por exemplo, dobre e adicione), 2. aprimorando (= manchando) o hash (por exemplo, meio do quadrado), 3. mapeando o hash no índice (por exemplo, módulo "&").
Maaartinus 31/12/12