Funcionamiento de las Tablas Hash.
¿ Muchas
aplicaciones requieren un conjunto dinámico que soporte las operaciones de un diccionario: Insert, Search, Delete. Por ejemplo el compilador cuando guarda los identificadores de un programa.
¿ Es posible hacer uso de una lista enlazada con un tiempo O(n); sin embargo, este tiempo se puede reducir notablemente a orden O(1) en la mayoría de los casos usando una tabla hash.
¿ La idea surge de los arreglos que nos permiten acceso a sus elementos en orden O(1).
¿ Una opción sería usar un arreglo tan grande como el rango de posibles claves. La desventaja es el espacio de memoria requerido en tal estrategia.
¿ Otra opción es usar un arreglo menor, al cual podemos mapear las claves en uso. Esta función de mapeo es la función hash. La tabla así organizada es la tabla hash.
¿ Como es posible que
dos claves conduzcan al mismo mapeo (lo cual se conoce como una colisión), es necesario buscar formas para resolver esta situación.
¿ Una forma, conocida como hashing abierto (hay otros términos dependiendo del texto), crear una lista asociada a cada entrada del arreglo.
¿ Otra forma, conocida como hashing cerrado (el término depende del libro), almacena las claves en las mismas entradas del arreglo o tabla hash.
