¿Qué debe saber todo programador sobre tablas hash y funciones hash?

Si una tabla hash es buena depende en gran medida de
1. cuánto espacio estás dispuesto a usar en la memoria y
2. qué tan buena es su función hash para sus datos.

La situación ideal es cuando puede crear un hash perfecto, una función de hash que sabe que hará hash de manera única todos los elementos de su conjunto de datos. Entonces solo necesitas n cubos para n elementos, y todo toma O (1) tiempo. Sin embargo, eso generalmente requiere conocer de antemano una cantidad poco práctica sobre sus datos para obtener esa buena función hash de tal manera que el uso de una matriz u otra estructura de datos también podría serle útil.

Si es como la mayoría de los usuarios de una tabla hash y está tratando de llevar los datos que deberían ser hash a una distribución uniforme, entonces tendrá una compensación entre memoria y eficiencia: cuantos más cubos permita, más espacio (y para en menor grado, tiempo) necesitará inicializar la tabla hash, pero menos tiempo pasará accediendo a los elementos después porque es menos probable que choquen. Por lo general, algunas pruebas manuales pueden darle una buena idea de dónde está el punto óptimo para sus restricciones de memoria y necesidades de rendimiento.

Las tablas hash no son una panacea de programación. No resolverán todos los problemas más rápido que otra estructura de datos. Una cosa críticamente importante sobre el uso de tablas hash es que requieren iterar a través de todo su conjunto de datos. Si solo va a hacer búsquedas de O (1) después, no vale la pena crear una nueva estructura de datos para buscarla, especialmente si sus datos ya tenían una cierta cantidad de estructura de búsqueda. Piense en el tiempo amortizado de sus operaciones, incluida esa inicialización, antes de comprometerse.

Las tablas hash no escalan.

No importa cuán buena sea su función hash, no puede hacer que la tabla hash sea arbitrariamente ancha. Eso desperdiciaría la memoria. Eso implica que a medida que el problema aumenta, tus cubos de hash se vuelven más y más profundos. Y terminas en una solución O (n) / (# hash buckets).

Usa un árbol en su lugar.

Hay un blog que explica las matemáticas internas detrás de la tabla hash.

Números que los programadores deben saber sobre Hash

En resumen, el factor de carga (no. Key / no. Bucket) es muy importante en la implementación de una tabla hash. Hasta donde yo sé, un factor de carga utilizado habitualmente es 0,75. Superior a 0,75 hace que la tasa de colisión aumente muy rápidamente.

Si el factor de carga es 1 no. clave == no. bucket, la distribución de claves es la siguiente, y el 37% (1 / e) buckets están vacíos.

Y a continuación se muestra cómo cambia la tasa de colisión (rojo) a medida que aumenta el factor de carga.

Y a continuación hay un gráfico que muestra que cuando el factor de carga se convierte en 10,000, el número de llaves en cada cucharón se vuelve suficiente.

Números que los programadores deben saber sobre Hash

Tablas hash : que son un pony de un solo truco . Funcionan muy bien para búsquedas en teclas completas, pero apestan en casi todo lo demás (por ejemplo, búsquedas de prefijos).

Funciones hash: que no siempre tienen que ser perfectas o casi perfectas; para algunas aplicaciones como la detección de plagio o la huella digital acústica, realmente desea colisiones con teclas similares (para alguna definición de “similar”). Siempre observe el uso previsto antes de decidir cómo debe comportarse su función hash.

1. Las colisiones son más frecuentes de lo que piensas (ver paradoja de cumpleaños)
2. Hay formas muy simples y eficientes de lidiar con las colisiones (Cuckoo Hashing, Hopscotch hashing)
3. ¡Una función hash tiene que ser rápida! (ver FNV, Jenkins, Murmullo)
4. Siempre hay una manera de resolver el problema que tienes con tu tabla hash 🙂

Tiempo medio constante de búsqueda / inserción / eliminación – O (1). ¡Supera eso!

Pruebe mi propia versión de una tabla hash escasa (encabezado único), rápida y * extremadamente * eficiente en memoria. Descargar en greg’s sparsehash.

Para explicar la excelente respuesta que Xanda dio:

“Tabla hash” es un término bastante general, no una cosa única para todos. Puede implementar uno de diferentes maneras, optimizado para las características de su conjunto de datos. Por ejemplo, si las inserciones van a ser poco frecuentes pero las búsquedas son frecuentes, puede elegir una implementación que esté altamente optimizada para las búsquedas mientras que las inserciones son caras. O si sabe que nunca eliminará elementos, puede elegir implementaciones que sean apropiadas solo en esa situación. O si su conjunto de datos inicial es pequeño pero sabe que crecerá en dos órdenes de magnitud a través del uso continuo durante los próximos diez años, puede elegir un esquema que se adapte a eso.

Entonces, ¿qué deberías saber? Antes de comenzar a diseñar una implementación de tabla hash, asegúrese de comprender realmente las características de su conjunto de datos, tanto hoy como en el futuro. ¡Y documente bien esas características junto con los documentos de diseño y el código! Porque un día alguien querrá cambiar esas suposiciones y necesitará saber si la tabla hash debe cambiarse o volver a implementarse en consecuencia.

Un hash no está ordenado. Dado un elemento, no puede encontrar el siguiente elemento en orden.
Para los datos genéricos, el rendimiento es impredecible y podría ser tan malo como recorrer una lista vinculada.
Para claves conocidas y un tamaño de conjunto de datos conocido y no necesita orden, los hash son geniales