Implementación de Hashtable

Question

Me preguntaron recientemente '¿cómo implementaría una batería hastable'? Sé que el algoritmo de hashing es crítico ya que mientras menos colisiones, mejor será el rendimiento de WRT, pero ¿qué estructura de algoritmo/datos se debe emplear para entregar tiempo constante amortizado {O (1)} para insertar/eliminar/buscar?

Answer 1

Las tablas hash tienen dos posibilidades principales:

1. direccionamiento abierto, que es una matriz simple [matriz dinámica podía comprender si puede dejar que su mesa de crecer sobre la marcha]. Una vez que se ha encontrado un conflicto, debe usar una segunda función hash para encontrar el siguiente plato al que se asignará el elemento. Tenga en cuenta que esta solución tiene algunos problemas [que se pueden resolver] cuando su tabla hash también permite eliminaciones. [Marca especial para los entrantes "borrados"]
2. Encadenamiento - en esta solución, cada plato en el gama es una lista vinculada - containig todos los elementos hash a este plato. Aquí, todos los elementos asignados a un cierto valor están en la lista.

La parte importante de las tablas hash [en] ambas soluciones con el fin de permitir que armotorized O (1) insertar/del/mirar hacia arriba - es la asignación de una mesa grande y refrito de una vez alcanzado un pre definido load factor.

EDIT: complejidad análsis:
asumir un factor de carga del p por alguna p < 1.

1. La probabilidad de la "colisión" en cada acceso es p lo tanto la media de la matriz accede es: Sigma(i * p^(i-1) * (1-p)) for each i in [1,n] Esto le da: Sigma(i * p^(i-1) * (1-p)) = (1-p) * Sigma(i * p^(i-1)) <= (1-p) * 1/(p-1)^2 = 1-p = CONST. [eche un vistazo a la corrección de Sigma(i * p^(i-1)) < 1/(p-1)^2 in wolfram alpha]. Por lo tanto, resulta en promedio una cantidad constante de accesos a la matriz. Además: Es posible que deba volver a configurar todos los elementos después de que se haya alcanzado el factor de carga, lo que da como resultado O(n) accesos a la matriz. Esto da como resultado n * O(1) ops [agregando n elementos] y 1 * O(n) op [refrentado], por lo que obtiene: (n * O(1) + 1 * O(n))/n = O(1) tiempo motorizado.
2. Muy similar a (1), pero el análisis se realiza en accesos de lista. Cada operación requiere exactamente un acceso a la matriz y una cantidad variada de accesos a la lista, con el mismo análisis que antes.