Download Tabla hash completa

Tablas hash
Juan Ramón Pérez Pérez
1
Prácticas EDI - © Juan Ramón Pérez
¿Cómo funciona la implementación
Java para las tablas hash?
Paquete java.util
Jerarquía de clases
HashMap
Importancia de los métodos hashCode() y equals()




2
Prácticas EDI - © Juan Ramón Pérez
Jerarquía de clases de la API de
Java (fragmento)
Collection
Map
<<interface>>
<<interface>>
List
Set
AbstractMap
<<interface>>
<<interface>>
<<abstracta>>
ArrayList
LinkedList
AbstractSet
<<abstracta>>
HashMap
HashTable
HashSet
Paquete java.util
3
Prácticas EDI - © Juan Ramón Pérez
java.util.HashMap
java.util.HashMap
Insertar
Buscar
Borrar
4
HashMap(int initialCapacity,
float loadFactor)
put(Object key, Object value): Object
get(Object key): Object
remove(Object key): Object
containsKey(Object key): boolean
containsValue(Object value): boolean
size(): int
[...]
Prácticas EDI - © Juan Ramón Pérez
Uso de HashMap
HashMap hm= new HashMap();
Mercancia m1= new Mercancia();
hm.put(m1.getCodigo(),m1);
Mercancia m= hm.get(m1.getCodigo());
5
Prácticas EDI - © Juan Ramón Pérez
… Y si utilizamos una clave no
String


Imaginemos que queremos asociar cada mercancía
con un objeto repartidor.
Y para buscar los objetos mercancía utilizamos el
repartidor.
HashMap hm= new HashMap();
Repartidor rep1= new Repartidor(“Pepe”);
Mercancia m1= new Mercancia(“Paquete fragil”);
hm.put(rep1,m1);
Repartidor rep= new Repartidor(“Pepe”);
Mercancia m= hm.get();
6
Prácticas EDI - © Juan Ramón Pérez
Para que funcione el ejemplo
anterior
java.lang.Object

hashCode(): int
equals(Object): boolean

Repartidor
hashCode(): int
equals(Object): boolean
7

Para insertar HashMap
necesita un código hash
del objeto que actúa como
clave (Repartidor).
No podemos utilizar
directamente el de Object.
Para buscar HashMap
necesita el código hash y
además poder comparar
objetos Repartidor.
Prácticas EDI - © Juan Ramón Pérez
La búsqueda de objetos cuando
hay colisiones
hashCode()%B54
Fran
HashMap hm= new HashMap();
Repartidor rep1= new
Repartidor(“Pepe”);
Mercancia m1= new
Mercancia(“Paquete
fragil”);
Repartidor rep2= new
Repartidor(“Fran”);
Mercancia m5= new
Mercancia(“Sobre
documentos”);
hm.put(rep1,m1);
hm.put(rep2,m5);
Repartidor rep= new
Repartidor(“Fran”);
Mercancia m= hm.get(rep);
8
hashCode()%B54
54
Pepe
Paquete frágil
hashCode()%B54
97
Prácticas EDI - © Juan Ramón Pérez
Fran
Sobre docum.
Implementación de nuestra tabla
hash
Crear una tabla hash abierta genérica.





9
Tamaño de la tabla debe de ser un número primo.
Función de dispersión basada en las poténcias de 32 y
optimizada con la regla de Horner  incluida en el método
hashCode() de los elementos que insertamos.
Gestión de colisiones mediante listas de elementos.
Que permita borrar los elementos.
Prácticas EDI - © Juan Ramón Pérez
Tabla hash final
En cada posición
de la tabla hay
una lista con
todos los
elementos que
colisionaron
Pasamos ya
como
parámetros
separados la
clave y el
elemento
10
TablaHash
Utiliza el
hashcode() de
la clave del
elemento que
insertamos y le
aplica el
módulo de B
tabla[]: Lista;
B: entero
Contenedor
-calcularDispersion(Object
clave): int
elemento: Object
create(entero tam)
clave:
String
insertar(String clave, Object
obj);
buscar(String clave): Object;
create()
borrar(String clave): boolean;
Clase
toString(): String
contenedor,
además del
[...]
Prácticas EDI - © Juan Ramón Pérez
elemento
guardamos la
clave
Tareas

Mejorar los métodos insertar y buscar para gestionar
colisiones:



Función de dispersión basada en hashCode() análoga a Java.
Tabla hash abierta
Añadir el método de borrar elementos
11
Prácticas EDI - © Juan Ramón Pérez