.net - metodo - ¿Cómo calculo un buen código hash para una lista de cadenas?

object equals java

Question

Fondo:

• Tengo una breve lista de cadenas.
• El número de cadenas no es siempre el mismo, pero casi siempre son del orden de un "puñado"
• En nuestra base de datos guardaremos estas cadenas en una 2da tabla normalizada
• Estas cadenas nunca se cambian una vez que se escriben en la base de datos.

Deseamos poder hacer coincidir estas cadenas rápidamente en una consulta sin el impacto en el rendimiento de hacer muchas combinaciones.

Así que estoy pensando en almacenar un código hash de todas estas cadenas en la tabla principal e incluirlo en nuestro índice, por lo que las uniones solo son procesadas por la base de datos cuando el código hash coincide.

Entonces, ¿cómo obtengo un buen hashcode? Yo podría:

• Xor los códigos hash de toda la cadena juntos
• Xor con multiplicar el resultado después de cada cuerda (digamos por 31)
• Cat toda la cadena juntos y luego obtener el código hash
• De alguna otra manera

Entonces, ¿qué piensa la gente?

Al final, simplemente concateno las cadenas y calculo el código de hash para la concatenación, ya que es simple y funcionó lo suficientemente bien.

(Si te importa, estamos usando .NET y SqlServer)

¡Error! ¡Error!

Citando de Pautas y reglas para GetHashCode por Eric Lippert

La documentación de System.String.GetHashCode señala específicamente que dos cadenas idénticas pueden tener diferentes códigos hash en diferentes versiones del CLR, y de hecho lo hacen. No almacene valores hash de cadena en bases de datos y espere que sean los mismos para siempre, porque no lo serán.

Así que String.GetHashcode () no debería usarse para esto.

Answer 1

Así que entiendo, ¿efectivamente tiene algún conjunto de cadenas que necesita identificar por código hash, y ese conjunto de cadenas que necesita identificar nunca cambiará?

Si ese es el caso, no importa en particular, siempre que el esquema que utiliza le dé números únicos para las diferentes cadenas / combinaciones de cadenas. Comenzaría por concatenar las cadenas y calcular el String.hashCode () y ver si terminas con números únicos. Si no lo haces, entonces podrías intentar:

• en lugar de concatenar cadenas, concatenar códigos hash de las cadenas de componentes, y probar diferentes multiplicadores (por ejemplo, si quieres identificar combinaciones de secuencias de dos cadenas, prueba con HC1 + 17 * HC2, si eso no te da números únicos, prueba HC1 + 31 * HC2, luego prueba 19, luego prueba 37 etc. - en esencia, cualquier número impar de pequeño tamaño funcionará bien).
• Si no obtiene números únicos de esta manera, o si necesita hacer frente al conjunto de posibilidades en expansión, considere un código hash más fuerte. Un código hash de 64 bits es un buen compromiso entre la facilidad de comparación y la probabilidad de que los hash sean únicos.

Un posible esquema para un código hash de 64 bits es el siguiente:

• generar una matriz de 256 números aleatorios de 64 bits utilizando un esquema bastante sólido (podría usar SecureRandom, aunque el esquema XORShift funcionaría bien)
• seleccione "m", otro número "aleatorio" de 64 bits, impar con más o menos la mitad de sus bits configurados
• para generar un código hash, pase por cada valor de byte, b, que forma la cadena, y tome el número bth de su matriz de números aleatorios; luego XOR o agregue eso con el valor hash actual, multiplicado por "m"

Entonces, una implementación basada en valores sugeridos en Recetas Numéricas sería:

  private static final long[] byteTable;
  private static final long HSTART = 0xBB40E64DA205B064L;
  private static final long HMULT = 7664345821815920749L;

  static {
    byteTable = new long[256];
    long h = 0x544B2FBACAAF1684L;
    for (int i = 0; i < 256; i++) {
      for (int j = 0; j < 31; j++) {
        h = (h >>> 7) ^ h;
        h = (h << 11) ^ h;
        h = (h >>> 10) ^ h;
      }
      byteTable[i] = h;
    }
  }

Lo anterior está inicializando nuestra matriz de números aleatorios. Usamos un generador XORShift, pero realmente podríamos usar cualquier generador de números aleatorios de buena calidad (creando un SecureRandom () con una semilla particular y luego llamar a nextLong () estaría bien). Entonces, para generar un código hash:

  public static long hashCode(String cs) {
    if (cs == null) return 1L;
    long h = HSTART;
    final long hmult = HMULT;
    final long[] ht = byteTable;
    for (int i = cs.length()-1; i >= 0; i--) {
      char ch = cs.charAt(i);
      h = (h * hmult) ^ ht[ch & 0xff];
      h = (h * hmult) ^ ht[(ch >>> 8) & 0xff];
    }
    return h;
  }

Una guía a tener en cuenta es que, dado un código hash de n bits, en promedio esperaría tener que generar hashes del orden de 2 ^ (n / 2) cadenas antes de que se produzca una colisión. O dicho de otro modo, con un hash de 64 bits, esperaría una colisión después de alrededor de 4 mil millones de cadenas (por lo que si se trata de hasta, digamos, un par de millones de cadenas, las posibilidades de una colisión son bastante insignificantes )

Otra opción sería MD5, que es un hash muy fuerte (prácticamente seguro), pero es un hash de 128 bits, por lo que tiene la ligera desventaja de tener que lidiar con los valores de 128 bits. Yo diría que MD5 es excesivo para estos propósitos. Como digo, con un hash de 64 bits, puede tratar con bastante seguridad en el orden de unos pocos millones de cadenas.

(Lo siento, debería aclarar: MD5 fue diseñado como un hash seguro, es solo que se ha descubierto que no es seguro. Un hash "seguro" es aquel en el que se le da un hash en particular y no es factible construirlo de forma deliberada que lo lleve a ese hash. En algunas circunstancias, pero no como yo entiendo en el suyo, necesitaría esta propiedad. Puede necesitarla, por otro lado, si las cadenas están tratando con datos de entrada del usuario, es decir, El usuario malintencionado podría intentar confundir deliberadamente tu sistema. También podrías estar interesado en lo siguiente que escribí en el pasado:

• guía para códigos hash
• códigos hash seguros en Java (incluye algunas medidas de rendimiento)

Answer 2

El uso de GetHashCode() no es ideal para combinar valores múltiples. El problema es que para las cadenas, el código de hash es solo una suma de comprobación. Esto deja poca entropía para valores similares. por ejemplo, agregar códigos hash para ("abc", "bbc") será el mismo que ("abd", "abc"), causando una colisión.

En los casos en que necesite estar absolutamente seguro, usaría un algoritmo de hash real, como SHA1, MD5, etc. El único problema es que son funciones de bloqueo, lo cual es difícil de comparar rápidamente hashes para la igualdad. En cambio, prueba con un hash CRC o FNV1 . FNV1 de 32 bits es súper simple:

public static class Fnv1 {
    public const uint OffsetBasis32 = 2166136261;
    public const uint FnvPrime32 = 16777619;

    public static int ComputeHash32(byte[] buffer) {
        uint hash = OffsetBasis32;

        foreach (byte b in buffer) {
            hash *= FnvPrime32;
            hash ^= b;
        }

        return (int)hash;
    }
}

Answer 3

Espero que esto no sea necesario, pero ya que no mencionas nada que suene como que solo estás usando códigos hash para un primer control y luego verificas que las cadenas son realmente iguales, siento la necesidad de advertirte:

Hashcode igualdad! = Valor igualdad

Habrá muchos conjuntos de cadenas que producen el código hash idéntico, pero no siempre serán iguales.

Answer 4

La práctica estándar de Java es simplemente escribir

final int prime = 31;
int result = 1;
for( String s : strings )
{
    result = result * prime + s.hashCode();
}
// result is the hashcode.

Answer 5

No veo ninguna razón para no concatenar las cadenas y calcular el código hash para la concatenación.

Como una analogía, digamos que quería calcular una suma de comprobación MD5 para un bloque de memoria, no dividiría el bloque en partes más pequeñas y calcularía las sumas de comprobación MD5 individuales para ellos y luego los combinaría con algún método ad hoc.

Answer 6

Otra forma que aparece en mi cabeza, cadenas xors con hashes giradas basadas en el índice:

int shift = 0;
int result = 1;
for(String s : strings)
{
    result ^= (s.hashCode() << shift) | (s.hashCode() >> (32-shift)) & (1 << shift - 1);
    shift = (shift+1)%32;
}

editar: leyendo la explicación dada en java efectivo, creo que el código de geoff sería mucho más eficiente.

Answer 7

Puede usar el siguiente método para agregar códigos hash: http://docs.oracle.com/javase/7/docs/api/java/util/Objects.html#hash(java.lang.Object...)

Answer 8

Su primera opción tiene el único inconveniente de que (String1, String2) produce el mismo hashcode de (String2, String1) . Si eso no es un problema (por ejemplo, porque tiene un pedido de reparación) está bien.

" Cat todo el hilo juntos y luego obtener el hashcode " me parece más natural y seguro.

Actualización : como señala un comentario, esto tiene el inconveniente de que la lista ("x", "yz") y ("xy", "z") daría el mismo hash. Para evitar esto, puede unir las cadenas con un delimitador de cadena que no puede aparecer dentro de las cadenas.

Si las cadenas son grandes, es posible que prefiera hash cada una, cat the hashcodes y vuelva a generar el resultado. Más CPU, menos memoria.

Answer 9

Una solución basada en SQL podría basarse en las funciones checksum y checksum_agg. Si lo sigo bien, tienes algo como:

MyTable
  MyTableId
  HashCode

MyChildTable
  MyTableId  (foreign key into MyTable)
  String

con las diversas cadenas para un elemento determinado (MyTableId) almacenadas en MyChildTable. Para calcular y almacenar una suma de comprobación que refleje estas cadenas (que nunca se deben cambiar), algo como esto debería funcionar:

UPDATE MyTable
 set HashCode = checksum_agg(checksum(string))
 from MyTable mt
  inner join MyChildTable ct
   on ct.MyTableId = mt.MyTableId
 where mt.MyTableId = @OnlyForThisOne

Creo que esto es independiente de orden, por lo que las cadenas "El marrón rápido" produciría la misma suma de comprobación que "marrón rápido".

Answer 10

Vamos a resolver tu problema de raíz.

No use un código hash. Solo agrega una clave primaria entera para cada cadena