tablas hash
historia
La idea de tablas hashing se presento de forma independiente en diferentes lugares.
En Enero de 1953, Hans Peter Luhn escribió un memorando interno en IBM en el cual
explicaba que había utilizado hashing con encadenamiento
para que sirven
funcion de dispersion
Formas de Resolver las Colisiones
Resolución Mediante Exploración
Trata de buscar otra posición libre en la tabla
Exploración Lineal.
Visita la siguiente casilla.
Exploración Cuadrática
Visita la casilla i2 posiciones más allá de la que causó la
colisión.
Resolución Mediante Encadenamiento Enlazado
En cada posición de la tabla se mantiene una Lista Enlazada en la que se
van insertando los elementos cuyo valor de hash les asigna la misma
posición.
convierte un Objeto en un Entero (valor Hash)adecuado para indexar la Tabla en la que se guardará el Objeto
Java dispone de mecanismos estándar para obtener valores hash a partir de
cualquier Objeto
En la clase Object está definido el método: public int hashCode()
Dado que el método está implementado en la raíz de la jerarquía de herencia,
cualquier clase dispone de una implementación por defecto
Hashing Enlazado
funciones
colisiones
Se puede dar el caso de que una información a insertar en la tabla presente el mismo
valor hash, por ende habrán dos valores queriendo entrar a la misma posición de la
tabla.
Factor de carga
El factor de carga es igual a la cantidad de elementos a insertar en la tabla dividida en la
capacidad de esta misma
Hashing
El hashing cerrado
es una implementación en la cual se tiene un
array que en cada posición se apunta a una lista enlazada en la cual se almacenan las
informaciones que contienen la misma clave
El hashing abierto o encadenamiento,
es una implementación en la cual se tiene un array en el cual se
almacena la información en cada slot según lo indique la clave
Inserción
En hashing abierto, consiste en aplicar la función hash al dato a insertar. El resultado de esta operación genera la clave que va a indicar la posición del array en la cual se
almacenará el dato y en esta posición del array se añadirá al inicio de la lista enlazada.
eliminacion
La eliminación tiene el mismo costo que la búsqueda, ya que con la función hash se
encuentra la posición del elemento y posteriormente se elimina.
El Hashing Enlazado usa un vector de Listas Enlazadas: Aquellos objetos que reciban
un determinado valor de Hash, se insertarán en la lista enlazada correspondiente.
En una tabla hash con encadenamiento, las entradas de la tabla
Los objetos con claves colisionadas se insertan el la misma lista.
La inserción, la búsqueda y la eliminación se convierten en procesos de 2 pasos
Utilizar la función hash para seleccionar el slot adecuado.
Realizar la operación necesaria en la lista enlazada a la que se hace referencia en
dicho slot
Una tabla hash o mapa hash es una estructura de datos que asocia llaves o claves con
valores. Colección de elementos, cada uno de los cuales tiene una clave y una
información asociada.
operaciones basicas
insertar llave
buscar llave
eliminar llave