La mejor función hash para identificadores numéricos y literales mixtos

Question

Por razones de rendimiento, tengo la necesidad de dividir un conjunto de objetos identificados por una cadena en grupos. Los objetos pueden ser o bien identifican por un número o por una cadena en forma prefijada (calificado) con los puntos de separación de partes del identificador:

12 
323 
12343 
2345233 
123123131 
ns1:my.label.one 
ns1:my.label.two 
ns1:my.label.three 
ns1:system.text.one 
ns2:edit.box.grey 
ns2:edit.box.black 
ns2:edit.box.mixed 

identificadores numéricos son de 1 a varios millones. Los identificadores de texto tienen muchas probabilidades de comenzar con el mismo prefijo de espacio de nombre (ns1 :) y con el mismo prefijo de ruta (edit.box.).

¿Cuál es la mejor función hash para este propósito? Sería bueno si puedo predecir de alguna manera el tamaño del cubo en función de las estadísticas del identificador de objeto. ¿Hay algunos buenos artículos para construir una buena función hash basada en cierta información estadística?

Hay varios millones de estos identificadores, pero el propósito es dividirlos en grupos de 1-2 miles basado en la función hash.

Answer 1

Dos buenas funciones hash pueden ambos ser mapeados en el mismo espacio de los valores, y en general no causa nuevos problemas, como resultado de la combinación de ellos.

lo tanto, su función hash puede tener este aspecto:

if it's an integer value: 
    return int_hash(integer value) 
return string_hash(string value) 

A menos que haya ninguna aglutinación de los números enteros en torno a ciertos valores de módulo N, donde N es un número posible de cubos, entonces int_hash simplemente puede devolver su entrada.

Elegir un hash de cadena no es un problema nuevo. Pruebe con "djb2" (http://www.cse.yorku.ca/~oz/hash.html) o similar, a menos que tenga requisitos de rendimiento obsceno.

No creo que tenga mucho sentido modificar la función hash para tener en cuenta los prefijos comunes. Si su función de hash es buena para empezar, entonces es poco probable que los prefijos comunes creen una agrupación de valores de hash.

Si hace esto, y el hash no funciona inesperadamente mal, y pone sus varios millones de valores de hash en unos pocos miles de cubetas, entonces las poblaciones de cubetas se distribuirán normalmente, con la media (varios millones/unos pocos mil) y varianza 1/12 (algunos miles)^2

Con un promedio de 1500 entradas por cucharón, eso hace que la desviación estándar sea alrededor de 430. El 95% de una distribución normal se encuentra dentro de 2 desviaciones estándar de la media , entonces el 95% de tus cubos contendrán 640-2360 entradas, a menos que haya hecho mis sumas incorrectamente. ¿Es eso adecuado o necesitas que los cubos sean de tamaños más similares?

Answer 2

Es probable que sea seguro ir con sha1 y truncar a cualquier tamaño que desee.

No sería extremadamente eficiente, pero tal vez la función hash no sea un cuello de botella?

Answer 3

Calculo CRC16 sería un hash razonable utilizar en estas cadenas, y los grupos no deberían ir más grande de 1-2 mil.

Esto debería hacer que la tabla hash sea de aproximadamente 1MB + sin embargo hay muchos elementos en ella * 4 bytes, así que estamos hablando de 50MB, y también tenemos todos los datos almacenados, que deberían ser muy pequeños.