¿Hay una diferencia de velocidad de colisión entre un hash de 32 bits frente a dos hash de 16 bits?

Question

Estoy trabajando en un sistema donde las colisiones hash serían un problema. Básicamente, hay un sistema que hace referencia a los elementos en una estructura hash-table + tree. Sin embargo, el sistema en cuestión primero compila los archivos de texto que contienen rutas en la estructura en un archivo binario que contiene los valores hash en su lugar. Esto se hace por motivos de rendimiento. Sin embargo, debido a esto, las colisiones son muy malas ya que la estructura no puede almacenar 2 elementos con el mismo valor hash; la parte que solicita un artículo no tendría suficiente información para saber cuál necesita.

Mi idea inicial es que 2 hashes, ya sea usando 2 algoritmos diferentes, o el mismo algoritmo dos veces, con 2 sales serían más resistentes a las colisiones. Dos ítems que tengan el mismo hash para diferentes algoritmos hash serían muy poco probables.

Esperaba mantener el valor hash de 32 bits por razones de espacio, así que pensé que podría cambiar a usar dos algoritmos de 16 bits en lugar de un algoritmo de 32 bits. Pero eso no aumentaría el rango de posibles valores hash ...

Sé que cambiar a dos hashes de 32 bits sería más resistente a las colisiones, pero me pregunto si al cambiar a 2 hashes de 16 bits tiene al menos algunos ganar más de un solo hash de 32 bits? No soy la persona más inclinación matemática, así que no sé ni cómo empezar la comprobación de una respuesta que no sea a la fuerza soplo que ...

Algunos antecedentes sobre el sistema:

nombres

Los productos que se dan por humanos, no son cadenas aleatorias, y típicamente estarán hechas de palabras, letras y números sin espacio en blanco. Es una estructura hash anidada, así que si tuvieras algo como {a => {b => {c => 'blah'}}} obtendrías el valor 'blah' obteniendo el valor de a/b/c, solicitud compilada sería 3 valores hash en secuencia inmediata, los valores hashe de a, b, y luego c.

Solo hay un problema cuando hay una colisión en un nivel determinado. Una colisión entre un elemento en el nivel superior y un nivel inferior está bien. Puedes tener {a => {a => {...}}}, casi garantizando colisiones que están en diferentes niveles (no es un problema).

En la práctica, cualquier nivel dado probablemente tendrá menos de 100 valores para el hash, y ninguno será duplicado en el mismo nivel.

Para probar el algoritmo de hash que adopté (olvidé cuál, pero no lo inventé) descargué toda la lista de módulos de CPAN Perl, dividí todos los espacios de nombres/módulos en palabras únicas y finalmente crucifiqué cada uno buscando colisiones , Encontré 0 colisiones. Eso significa que el algoritmo tiene un valor de hash diferente para cada palabra única en la lista de espacio de nombres de CPAN (o que lo hice mal). A mí me parece lo suficientemente bueno, pero todavía molesta mi cerebro.

Answer 1

Si tiene 2 hashes de 16 bits, que están produciendo valores no correlacionados, entonces acaba de escribir un algoritmo hash de 32 bits. Eso no será mejor ni peor que cualquier otro algoritmo hash de 32 bits.

Si le preocupan las colisiones, asegúrese de estar utilizando un algoritmo hash que hace un buen trabajo de hash de sus datos (algunos están escritos simplemente para ser rápidos de calcular, esto no es lo que desea) y aumentar el tamaño de tu hash hasta que te sientas cómodo.

Esto plantea la cuestión de la probabilidad de colisiones. Resulta que si tiene n elementos en su colección, hay n * (n-1)/2 pares de cosas que podrían colisionar. Si está utilizando un hash de k, las probabilidades de que un solo par colisionen son 2-k. Si tiene muchas cosas, entonces las probabilidades de que diferentes pares colisionen casi no están correlacionadas.Esta es exactamente la situación que describe el Poisson distribution.

Por lo tanto, el número de colisiones que verá deberá seguir aproximadamente la distribución de Poisson con λ = n * (n-1) * 2-k-1. A partir de eso, la probabilidad de que no haya colisiones hash es aproximadamente e-λ. Con 32 bits y 100 elementos, las probabilidades de una colisión en un nivel son de aproximadamente 1.1525 en un millón. Si haces esto suficientes veces, con suficientes conjuntos de datos diferentes, eventualmente esas un millón de posibilidades se sumarán.

Pero tenga en cuenta que tiene muchos niveles de tamaño normal y algunos grandes, los más grandes tendrán un impacto desproporcionado en el riesgo de colisión. Esto se debe a que cada cosa que agrega a una colección puede colisionar con cualquiera de las cosas anteriores: más cosas equivalen a un mayor riesgo de colisión. Entonces, por ejemplo, un solo nivel con 1000 elementos de datos tiene aproximadamente 1 posibilidad en 10,000 de fallar, que es aproximadamente el mismo riesgo que 100 niveles con 100 elementos de datos.

Si el algoritmo hashing no está haciendo su trabajo correctamente, su riesgo de colisión aumentará rápidamente. Qué tan rápido depende mucho de la naturaleza del fracaso.

Usando esos hechos y sus proyecciones sobre el uso de su aplicación, debería poder decidir si se siente cómodo con el riesgo de hashes de 32 bits, o si debe pasar a algo más grande.