von juan manuel sanchez pareja Vor 6 Jahren
882
Mehr dazu
operaciones basicas
eliminar llave
buscar llave
insertar llave
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.
La inserción, la búsqueda y la eliminación se convierten en procesos de 2 pasos
Realizar la operación necesaria en la lista enlazada a la que se hace referencia en dicho slot
Utilizar la función hash para seleccionar el slot adecuado.
Los objetos con claves colisionadas se insertan el la misma lista.
En una tabla hash con encadenamiento, las entradas de la tabla
funciones
Inserción
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.
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.
Hashing
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
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
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
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.
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
Formas de Resolver las Colisiones
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.
Resolución Mediante Exploración
Visita la casilla i2 posiciones más allá de la que causó la colisión.
Exploración Cuadrática
Visita la siguiente casilla.
Exploración Lineal.
Trata de buscar otra posición libre en la tabla
