¿Cómo podemos lograr la inserción en el hash en el peor de los casos en O (1) mediante el uso de la matriz, mientras que las matrices tienen problemas de extensión en filledup?

La respuesta es que no. Este es el problema con las tablas hash y cualquier algoritmo posible para crear. Leer. Actualizar o Eliminar. Entonces, tienes algunas opciones.

1) después de un conflicto de hash, puede buscar el siguiente hoyo. Esto lleva a problemas para garantizar que encuentre un valor, ya que si la clave no es lo que comió buscando en el hash, debe escanear toda la matriz para que no se pierda nada. Si la tabla hash se llena, debe asignar una nueva tabla y volver a hacer hash en cada entrada.

2) tener cubos en lugar de entradas individuales en cada lugar de la tabla hash. El acceso a un depósito se puede realizar de varias maneras, pero generalmente es una matriz o un árbol binario equilibrado. (Ahora tiene un árbol binario equilibrado además de la tabla hash. ¿Exactamente qué está guardando?). Esto tiene la ventaja de no volver a generar hash, pero a expensas de una mayor complejidad del código.

3) cada vez que haya un conflicto, construya una tabla más grande y repita. Esto genera el beneficio de un código simple, pero el inconveniente de que no hay garantía de que aumentar el tamaño de la matriz de la tabla hash en realidad evitará otro conflicto al insertar los valores existentes en la nueva tabla hash.

De ellos, 2 es probablemente el más útil, pero aún existe un costo mayor que el constante para el acceso CRUD a los artículos dentro de un depósito individual.

La mejor solución posible que aumenta el tamaño si la matriz de la tabla hash es O (n lg (n)) complejidad amortizada. Esto se hace duplicando el tamaño de la matriz cuando se activa ese evento.

La solución que utiliza árboles equilibrados tiene una complejidad de n lg (n)) donde n es el tamaño del cubo más grande.

La inserción de hash O (1) es un mito común de los viejos tiempos. Sin supuestos adicionales como los límites de longitud de la clave, ni siquiera puede hacer una clave en O (1) . Si tiene límites de longitud de clave como ” todas las claves tienen menos de 16 bits”, entonces la pregunta asintótica no tiene sentido, ya que solo está agregando duplicados a la tabla hash a medida que N aumenta hacia el infinito. El mejor hashing realista en el caso asintótico para N claves distintas es O (log N) por inserción de clave porque necesita registrar N bits para describir N claves distintas y la función hash debe examinar cada bit en el caso general. Tenga en cuenta que esto hace que las tablas hash y los árboles equilibrados sean equivalentes en términos de rendimiento asintótico. Incluso este modelo solo tiene un sentido teórico de la información abstracta: las computadoras uni-procesadoras físicas (no cuánticas) reales son aún más limitadas en el caso asintótico: podemos suponer que cada bit requiere una cantidad mínima de volumen V. Por lo tanto, N bits de almacenamiento requieren una raíz cúbica de N radio esférico en el empaque óptimo en tres dimensiones. La información no puede viajar más rápido que la velocidad de la luz. Esto significa que el costo real de la inserción o recuperación en nuestro universo físico para las computadoras uni-procesador clásicas termina siendo un tiempo O (N ^ (1/3)) por inserción o recuperación a medida que la tabla se agranda incluso antes de abordar los problemas prácticos de costo, consumo de energía, disipación de calor, etc.

En términos prácticos, incluso con problemas de tamaño real, las tablas hash están más cerca del tiempo O (log N) que O (1) . Vea, por ejemplo, este punto de referencia de la marca hash: esta tabla hash es más rápida que una matriz de Judy Observe cómo el tiempo de inserción aumenta gradualmente a medida que se hace más grande.

Existe un algoritmo para expandir matrices con un costo de O (1) amortizado. Por ejemplo, cuando está lleno, cree una nueva matriz que sea el doble del tamaño. Copia todos los elementos. Esto parece costoso, pero en promedio, no es tan malo. Intenta resolverlo tú mismo y has respondido tu propia pregunta. Si necesita más ayuda, le di las palabras “costo amortizado”.