¿En qué situación no debemos usar la tabla Hash?

Comenzaré cuando use una tabla hash y luego intentaré señalar por qué no la usaría a medida que avanzo.

Mis tres usos principales de una tabla hash son diccionarios / mapas, conjuntos y declaraciones de cambio. Algunos lenguajes generan una tabla hash para una instrucción switch y otros crean una cadena if … else … if.

La fortaleza de una tabla hash es que reduce los tiempos de búsqueda hasta la complejidad temporal de O (1). Esto es genial cuando se trata de una mayor cantidad de valores.

Diccionario / Mapa:

Como dije, la complejidad del tiempo O (1) es excelente para manejar una gran cantidad de valores. Sin embargo, no es tan bueno cuando se trata de una pequeña cantidad de valores. Esta es parte de la razón por la cual C # tiene una clase llamada HybridDictionary. HybridDictionary utiliza una lista vinculada cuando el número de entradas es pequeño, pero cambia a una tabla hash cuando el recuento de entradas supera un cierto punto. El tiempo de búsqueda en esa lista vinculada tiene una complejidad temporal de O (n) con n el número de elementos en la lista vinculada en el momento de la búsqueda.

¿Por qué sería mejor una lista vinculada para tratar con un número menor de valores? Porque una búsqueda de lista vinculada tiene una complejidad temporal de O (n). Sí, una lista vinculada tarda más a medida que aumenta el número de elementos en la lista, pero eso también significa que lleva menos tiempo a medida que disminuye el número de elementos. Obtener el tiempo de búsqueda de una tabla hash para que funcione independientemente de la cantidad de elementos requiere un recargo de los cálculos, y este recargo ocupa el tiempo suficiente para que la búsqueda de la tabla hash sea más lenta que solo mirar cada elemento en el contenedor cuando hay una pequeña cantidad de artículos para mirar.

Conjuntos

A veces, cuando estoy tratando con conjuntos matemáticos, necesito hacer operaciones en esos conjuntos. Cuando se usa una operación en el Conjunto A y el Conjunto B, muchas de esas operaciones tienen una complejidad temporal de O ([matemática] | Conjunto A | * | Conjunto B | [/ matemática]), para ser claros, eso es O (tamaño de Establecer A veces el tamaño del Conjunto B). El uso de un conjunto hash puede reducir esto a O ([matemática] | Conjunto A | [/ matemática]) u O ([matemática] | Conjunto B | [/ matemática]) u O ([matemática] | Conjunto A | + | Establecer B | [/ matemáticas]); Es un truco muy útil. La complejidad de tiempo O (a + b) es lo que obtengo cuando necesito convertir uno de los conjuntos a un HashSet. Solo necesito usar la tabla hash para el conjunto más grande mientras itero sobre el conjunto más pequeño. De hecho, tener una tabla hash para el Set más pequeño podría ser malo; pero ¿por qué es bueno para el conjunto más grande? Porque estoy haciendo búsquedas en el conjunto más grande. Si mi gran conjunto no está usando una tabla hash como back-end para empezar, entonces (la mayoría de las veces) solo necesito convertir el mayor de los dos conjuntos para que este truco funcione. Sin embargo, ¿qué pasa si el conjunto es demasiado grande?

La cuestión n. ° 1 era el recargo de cálculo; El problema n. ° 2 es el espacio de memoria adicional que ocupa una tabla hash. Uno de mis profesores me dijo que una buena regla general para un tamaño de matriz de tabla hash era el doble del número de entradas actuales en la tabla.

¿Por qué querríamos que la matriz sea al menos dos veces mayor que la cantidad de entradas dentro de ella? Hash colisiones. Hay dos formas de Hash Collisions para tratar. Elementos con la misma clave hash y claves hashed que se asignan al mismo índice de matriz. Esta regla general reduce el número de claves hash que se asignan a la misma ubicación.

¿Qué significa esto para nosotros? Que a medida que aumenta el número de elementos en la tabla hash, corremos el riesgo de quedarnos sin espacio de memoria para nuestra tabla hash. Este es un problema que los sistemas de bases de datos a gran escala tienen que enfrentar. Según tengo entendido, una forma común en que el trato con esto es a través de algunos de B-Tree. Necesitaría investigar un poco para contarte más sobre cómo lidian con esto, pero lo más probable es que haya alguien en Quora que estaría más que feliz de explicarme cómo solucionar este problema.

Declaraciones de cambio:

Como dije antes, algunos idiomas usan una tabla hash como back-end de sus declaraciones de cambio. Lo bueno de esto es que la tabla hash generalmente se crea en tiempo de compilación. Lo malo de esto es que la declaración de cambio se limita a elementos con una conversión de clave hash consistente. ¿Qué significa esto? Que esta forma de declaración de cambio solo funciona en casos cuantitativos, pero no funcionará en rangos de casos. Podemos hacer que los casos cuantitativos se parezcan un poco a los rangos de casos haciendo una caída, pero eso solo funciona para los casos que establecemos específicamente. No podemos algo como:

si (8 <= x <= 25) ...

Podemos hacer:

interruptor (x):
caso 8:
caso 9:
…
caso 24:
caso 25:
…
descanso;

Sin embargo, ¿qué pasa si el valor de x es 9.5? Como dije antes, solo funciona para casos cuantitativos. Entonces, si no tiene un caso cuantitativo, Hash Tables no funcionará para usted.

Ahora, he señalado los usos de Hash Tables y algunas de las debilidades de esos casos de uso. ¿Qué pasa con los casos en que Hash Table simplemente no es una buena idea?

• Las tablas de hash no clasifican / ordenan elementos, esto es para lo que sirven muchas otras cosas
• Las tablas de hash no hacen FIFO, para eso están las colas
• Las tablas de hash no hacen FILO, para eso están las pilas
• Mapeo / transformación basada en ecuaciones de baja computación, podemos escribir una función / método convertidor para eso
• Cosas mencionadas en las otras respuestas

1. Cuando te importa el orden de los artículos. Específicamente, si necesita enumerar los elementos en el orden de las teclas más de una vez cuando haya terminado con la asignación de clave-> valor, probablemente sería mejor usar un árbol de búsqueda binario para representar la asignación.
2. Cuando sería mejor usar una matriz, es decir, sus claves son enteros densamente empaquetados o fáciles de convertir en enteros densamente empaquetados.
3. Cuando realmente no necesita la tecla O (1), busque cualquier cosa. Las operaciones en tablas hash son eficientes pero no son gratuitas. No los use porque sí, por ejemplo, sus objetos tienen una identificación. Si nunca necesita buscar nada por ID o probar la existencia por ID, use una lista o una matriz.
4. Cuando necesita poder acceder al enésimo elemento de manera eficiente. Por ejemplo, si desea poder elegir un miembro aleatorio de la colección de manera eficiente.

Aquí hay una lista incompleta:

• Cuando no se requiere la capacidad de buscar ninguna clave, a menudo es más apropiada otra estructura de datos, como una lista vinculada o un montón. Otra opción que a veces es superior es usar una matriz ordenada junto con la búsqueda binaria.
• Cuando las claves son enteras en un rango pequeño, una matriz puede ser más eficiente. Además, cuando los valores son booleanos, un vector de bits es a veces la solución correcta.
• Si la tabla hash se llena, es necesario cambiar su tamaño para usar memoria temporal y una cantidad considerable de tiempo. Para aplicaciones en tiempo real, esto a veces se puede resolver mediante hashes que cambian de tamaño gradualmente, pero aún así, usar BST equilibrados puede ser más simple o más conveniente.
• Los BST permiten un recorrido rápido en orden de las claves, las tablas hash no
• Las tablas hash requieren que se defina una buena función hash para las claves; proponer funciones hash rápidas y robustas no es trivial. Los BST solo requieren una operación de comparación, que es mucho más difícil de estropear
• Las tablas hash no son estructuras de datos particularmente eficientes para usar en algunas operaciones de conjuntos, como tomar la intersección de dos conjuntos.
• Si un pequeño grado de falsos positivos es aceptable, un filtro Bloom es una forma más eficiente de memoria para representar un conjunto