duplicates - Algoritmo básico de Hashtable: eliminación de duplicados

Question

Acabo de recibir una entrevista esta mañana y me dieron la pregunta "Dar un algoritmo para eliminar duplicados de una lista de enteros". Esta es una pregunta bastante estándar, así que estaba bastante seguro de poder responderla.

Estoy parafraseando, pero dije algo como "Podría usar una tabla hash. Comience con el primer entero e insértelo en la tabla hash. Luego, para cada número entero sucesivo haga una búsqueda de tabla doble para verificar si el número entero ya está en la tabla hash. Si no, introdúzcalo, si ya está allí, deséchelo porque es un duplicado. Así que repita la lista de esta manera. Si la tabla hash está diseñada correctamente, las búsquedas y las inserciones deben ser de tiempo constante en promedio.

Luego, el entrevistador respondió (otra vez estoy parafraseando) "Pero las búsquedas de tabla hash no son de tiempo constante, dependen de cuántos elementos ya hay en ella. El algoritmo que describió sería O (n ^ 2)"

Luego respondí: "¿De verdad? Pensé que si diseñabas una buena función de hash, sería un tiempo constante y lo harías O (n) típicamente"

Entonces el entrevistador respondió "Entonces usted está diciendo que el tiempo de búsqueda sería el mismo para una tabla hash con muchas entradas y una tabla hash con pocas entradas"

Luego dije "Sí. Si está diseñado correctamente".

Entonces el entrevistador dijo "Esto no es verdad"

SO estoy muy confundido en este momento. Si alguien pudiera señalar dónde estoy equivocado, estaría muy agradecido

Answer 1

Si alguien pudiera señalar dónde estoy equivocado

No se equivoca en absoluto: las tablas hash diseñadas adecuadamente le dan una eficiencia de búsqueda esperada de O(1) y se inserta en O(1) amortiguado, por lo que su algoritmo es O(N) . La búsqueda en tablas hash muy cargadas es de hecho un poco más lenta debido a la posible resolución duplicada, pero el tiempo de búsqueda esperado sigue siendo O(1) . Esto puede no ser lo suficientemente bueno para sistemas en tiempo real donde "amortizado" no cuenta, pero en todas las situaciones prácticas esto es suficiente.

Por supuesto, siempre puedes usar un árbol balanceado para los elementos que has visto para el algoritmo O(N*LogN) peor de los casos, o si los números tienen límites razonables (digamos, entre 0 y 100,000) podrías usar un booleano matriz para probar la pertenencia al O(1) peor caso, y una mejora potencial sobre una tabla hash debido a un multiplicador constante más pequeño.