Clasificación de la función hash

9

En Internet, me he encontrado con esta pregunta:

Clasifique las funciones de hash según los diversos métodos mediante los cuales se encuentra el valor clave.

con respuestas como

  • Método directo
  • Método de sustracción
  • Método de división en módulo
  • Método de extracción de dígitos
  • Método del cuadrado medio
  • Método de plegado
  • Método seudoaleatorio

lo cual me parece extraño. Creo que sé mucho sobre el hash, pero esto es una tontería para mí, ¿alguien podría explicarlo?

maaartinus
fuente

Respuestas:

4

Son métodos para convertir un código hash en un índice de la matriz que contiene los valores. Digamos que tiene un código hash de 0x12345678. Un número muy grande y es poco probable que tenga una matriz de este tamaño. Si lo haces puedes hacerlo

Value = array[0x12345678];

Y listo (método directo).

Si no lo hace, entonces tiene una forma de convertir este valor en uno que se ajuste al tamaño de la matriz mientras intenta evitar demasiadas colisiones. Los términos utilizados probablemente también se conocen con otros nombres, pero por ejemplo, podría enmascarar los bits más altos del código hash

Value = array[hashcode & 0xffff];

O modifique el código hash contra el tamaño de la matriz

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

Etcétera etcétera

Editar: este enlace puede ayudar

James
fuente
Gracias, eso es todo, el enlace parece ser la fuente de este ***. Todavía no tiene sentido ya que están mezclando muchas cosas: 1. calcular el código hash a partir de una clave (por ejemplo, doblar y agregar), 2. mejorar (= manchar) el hash (por ejemplo, mid-square), 3. mapeo el hash al índice (por ejemplo, módulo, "&").
maaartinus