c# - tablas - tipos de funciones hash

Mejor algoritmo hash en términos de colisiones hash y rendimiento para cadenas

Question

¿Cuál sería el mejor algoritmo hash si tuviéramos las siguientes prioridades (en ese orden):

1. Colisiones de hash mínimas
2. Actuación

No tiene que ser seguro. Básicamente, estoy tratando de crear un índice basado en una combinación de propiedades de algunos objetos. Todas las propiedades son cadenas .

Cualquier referencia a las implementaciones de c # sería apreciada.

Answer 1

"Murmurhash" es bastante bueno tanto en rendimiento como en colisiones.

El hilo mencionado en "softwareengineering.stackexchange" tiene algunas pruebas y Murmur gana.

Escribí mi propio puerto C # de MurmurHash 2 en .NET y lo probé en una lista de 466k palabras en inglés, obtuve 22 colisiones.

Los resultados y la implementación están aquí: https://github.com/jitbit/MurmurHash.net (descargo de responsabilidad, ¡estoy involucrado con este proyecto de código abierto!)

Answer 2

¡Amo ! La lectura de esta pregunta me hizo analizar las funciones hash un poco más y encontré el Cuckoo Hash .

Del artículo:

La búsqueda requiere la inspección de solo dos ubicaciones en la tabla hash, lo que lleva tiempo constante en el peor de los casos (consulte la notación Big O). Esto está en contraste con muchos otros algoritmos de tabla hash, que pueden no tener un peor caso constante enlazado en el momento de hacer una búsqueda.

Creo que eso encaja en su criterio de colisión y rendimiento. Parece que la compensación es que este tipo de tabla hash solo puede obtener el 49% de su capacidad.

Answer 3

Aquí hay una forma directa de implementarlo usted mismo: http://www.devcodenote.com/2015/04/collision-free-string-hashing.html

Aquí hay un fragmento de la publicación:

si digamos que tenemos un conjunto de caracteres de letras inglesas capitales, entonces la longitud del juego de caracteres es 26, donde A podría representarse por el número 0, B por el número 1, C por el número 2 y así sucesivamente hasta Z por el número 25. Ahora, cada vez que queremos asignar una cadena de este conjunto de caracteres a un número único, llevamos a cabo la misma conversión que hicimos en el caso del formato binario

Answer 4

Como indicó Nigel Campbell , no existe la "mejor" función hash, ya que depende de las características de los datos de lo que está procesando, así como de si necesita o no hashes de calidad criptográfica.

Dicho eso, he aquí algunos consejos:

• Dado que los elementos que está utilizando como entrada para el hash son solo un conjunto de cadenas, puede simplemente combinar los códigos hash para cada una de esas cadenas individuales. He visto el siguiente pseudocódigo sugerido para hacer esto, pero no conozco ningún análisis particular de él:

  int hashCode = 0;
  
  foreach (string s in propertiesToHash) {
      hashCode = 31*hashCode + s.GetHashCode();
  }

  Según este artículo , System.Web tiene un método interno que combina hashcodes usando

  combinedHash = ((combinedHash << 5) + combinedHash) ^ nextObj.GetHashCode();

  También he visto código que simplemente combina los códigos hash, pero me parece una mala idea (aunque de nuevo no tengo ningún análisis para respaldar esto). Si nada más, terminas con una colisión si las mismas cadenas son hash en un orden diferente.

• He usado FNV con buenos resultados: http://www.isthe.com/chongo/tech/comp/fnv/

• Paul Hsieh tiene un artículo decente: http://www.azillionmonkeys.com/qed/hash.html

• Otro buen artículo de Bob Jenkins que se publicó originalmente en 1997 en Doctor Dobb''s Journal (el artículo vinculado tiene actualizaciones): http://burtleburtle.net/bob/hash/doobs.html

Answer 5

El hashCode simple utilizado por la clase String de Java podría mostrar un algoritmo adecuado.

A continuación se muestra la implementación de "Classpath GNU". (Licencia: GPL)

  /**
   * Computes the hashcode for this String. This is done with int arithmetic,
   * where ** represents exponentiation, by this formula:<br>
   * <code>s[0]*31**(n-1) + s[1]*31**(n-2) + ... + s[n-1]</code>.
   *
   * @return hashcode value of this String
   */
  public int hashCode()
  {
    if (cachedHashCode != 0)
      return cachedHashCode;

    // Compute the hash code using a local variable to be reentrant.
    int hashCode = 0;
    int limit = count + offset;
    for (int i = offset; i < limit; i++)
      hashCode = hashCode * 31 + value[i];
    return cachedHashCode = hashCode;
  }

Answer 6

No hay un solo algoritmo de hash óptimo. Si tiene un dominio de entrada conocido, puede usar un generador de hash perfecto como gperf para generar un algoritmo hash que obtenga una tasa del 100% en ese conjunto de entrada en particular. De lo contrario, no hay una respuesta "correcta" a esta pregunta.

Answer 7

Olvídate del término "mejor". No importa qué algoritmo hash se le ocurra a alguien, a menos que tenga un conjunto de datos muy limitado que necesita ser hash, cada algoritmo que se desempeña muy bien en promedio puede volverse completamente inútil si solo se alimenta con el derecho (o desde su perspectiva "información incorrecta.

En lugar de perder demasiado tiempo pensando en cómo hacer que el hash sea más libre de colisiones sin utilizar demasiado tiempo de CPU, prefiero empezar a pensar en "Cómo hacer que las colisiones sean menos problemáticas". Por ejemplo, si cada cubo de hash es de hecho una tabla y todas las cadenas de esta tabla (que tuvieron una colisión) se ordenan alfabéticamente, puede buscar dentro de una tabla de bloque utilizando búsqueda binaria (que es solo O (log n)) y eso significa incluso cuando cada segundo cubo de hash tiene 4 colisiones, su código seguirá teniendo un rendimiento decente (será un poco más lento en comparación con una tabla libre de colisiones, pero no tanto). Una gran ventaja aquí es que si su tabla es lo suficientemente grande y su hash no es demasiado simple, dos cadenas que resulten en el mismo valor de hash se verán completamente diferentes (por lo tanto, la búsqueda binaria puede parar cadenas después de tal vez uno o dos caracteres en promedio haciendo que cada comparación sea muy rápida).

En realidad, yo mismo tuve una situación en la que la búsqueda directa dentro de una tabla ordenada con búsqueda binaria resultó ser más rápida que el hash. A pesar de que mi algoritmo hash era simple, me llevó bastante tiempo ajustar los valores. Las pruebas de rendimiento mostraron que solo si obtengo más de 700-800 entradas, el hashing es más rápido que la búsqueda binaria. Sin embargo, como la tabla nunca podría crecer más de 256 entradas de todos modos y como la tabla promedio estaba por debajo de 10 entradas, la evaluación comparativa mostró claramente que en cada sistema, cada CPU, la búsqueda binaria era más rápida. Aquí, el hecho de que normalmente ya se haya comparado el primer byte de los datos fue suficiente para llevar a la siguiente iteración de bsearch (ya que los datos solían ser muy diferentes en el primer byte de dos bytes) como una gran ventaja.

Así que para resumir: tomaría un algoritmo hash decente, que no provoca demasiadas colisiones en promedio y es bastante rápido (¡incluso aceptaría algunas colisiones más, si es muy rápido!) Y optimizo mi código cómo para obtener la penalización de rendimiento más pequeña una vez que ocurren las colisiones (¡y lo harán!) a menos que tu espacio de hash sea al menos igual o mayor que tu espacio de datos y puedas asignar un valor hash exclusivo a cada conjunto posible de datos).

Answer 8

Puede obtener ambos usando la función hash Knuth que se describe aquí .

Es extremadamente rápido, suponiendo un tamaño de tabla hash de potencia de 2, solo una multiplicación, un turno y un bit, y. Lo más importante (para usted) es excelente para minimizar las colisiones (consulte este análisis ).

Algunos otros buenos algoritmos se describen here .

Answer 9

Voy a ser cojo aquí y dar una respuesta más teórica en lugar de una respuesta pin-pointing, pero por favor tome el valor en él.

Primero hay dos problemas distintos:

a. Probabilidad de colisión b. Rendimiento de hash (es decir, tiempo, cpu-ciclos, etc.)

Los dos problemas son levemente corellados. No están perfectamente correlacionados.

El problema a trata con la diferencia entre el hashee y los espacios hash resultantes. Cuando hash un archivo de 1 KB (1024 bytes) y el hash tiene 32 bytes, habrá:

1,0907481356194159294629842447338e + 2466 (es decir, un número con 2466 ceros) posibles combinaciones de archivos de entrada

y el espacio de hash tendrá

1,1579208923731619542357098500869e + 77 (es decir, un número con 77 ceros)

La diferencia ES ENORME. hay 2389 diferencias de ceros entre ellos. HABRÁ COLISIONES (una colisión es un caso especial cuando dos archivos de entrada DIFERENTES tendrán el mismo hash exacto) ya que estamos reduciendo 10 ^ 2466 casos a 10 ^ 77 casos.

La única manera de minimizar el riesgo de colisión es ampliar el espacio de hash y, por lo tanto, hacer que los hahs sean más largos. Idealmente, el hash tendrá la longitud del archivo, pero esto es de alguna manera idiota.

El segundo problema es el rendimiento. Esto solo trata con el algoritmo del hash. Por supuesto que un hash más largo probablemente requerirá más ciclos de CPU, pero un algoritmo más inteligente podría no hacerlo. No tengo una respuesta de caso clara para esta pregunta. Es demasiado duro.

Sin embargo, puede comparar / medir diferentes implementaciones hash y sacar pre-conclusiones de esto.

Buena suerte ;)