Mapas, Diccionarios Y Tablas Hash.

Parte II. Tema 4: Mapas, diccionarios y tablas hash.

1. Introducción.
Este breve documento resume el plan de trabajo correspondiente a la séptima y octava
semana del curso, en las que revisamos un tipo estructuras de datos donde cada
elemento o entrada de la estructura, se compone de un par: (clave, valor). En particular,
se estudian las estructuras de datos Mapa y Diccionario,según un enfoque de TAD.
Ambos TADs se pueden implementar de manera eficiente mediante el uso de una tabla
hash. Se revisan los conceptos principales este tipo de estructuras, las operaciones de
los TADs correspondientes y su implementación como tabla hash. También
profundizaremos en las posibles realizaciones de estas tablas, en las funciones de
hashing, el manejo de las colisiones, etc.A lo largo de la presentación, se plantean
algunos ejemplos de uso de dichas estructuras en problemas de programación. Se
comentará qué elementos proporcionan las Java Collections para los TAD Mapa y
Diccionario. Además, se pone a vuestra disposición algunos de los códigos en Java de
las net.datastructures (ligeramente adaptados) para los mapas, diccionarios y tablas
hash.
Paracomplementar lo explicado, es interesante que el alumno lea el capítulo 9 sobre
“Maps and Dictionaries” de nuestro libro de referencia [Goodrich11]. También, se
deben estudiar “en paralelo” el contenido de las transparencias entregado sobre
“estructuras arborescentes básicas” y analizar los códigos Java contenidos en el archivo
comprimido srcHashTableMap.zip que implementa la interfaz Mapcomo una tabla hash
con direccionamiento abierto.
Los objetivos para estas dos semanas son:
1) Estudiar TAD Mapa (Map), su implementación más común (tabla hash) y la
forma de usarlo en problemas de programación tanto desde las Java Collections
como desde las net.datastructures.
2) Estudiar el TAD Diccionario (Dictionary), su implementación más común (tabla
hash) y la forma de usarlo enproblemas de programación tanto desde las Java
Collections como desde las net.datastructures.
3) Conocer la estructura de datos y el correspondiente TAD ColaPrioridades
(Prority Queue).
Para ello, en la Sección 2 de este documento se describen de forma resumida los
aspectos mencionados. Con el fin de completar la información de este resumen, se
añaden a lo largo del mismo variasreferencias bibliográficas a otros documentos y/o
enlaces de páginas web. La Sección 3 propone algunos ejercicios sobre los temas
tratados. Una breve bibliografía aparece en la última sección de este documento. 2. Descripción de contenidos.
2.1. Mapas.
Un mapa (map) es una colección elementos llamados entradas (entries), donde cada
elemento está formado por un par: (clave, valor), quepueden ser de cualquier tipo.
Existe una asociación o “mapeo” entre la clave y el valor de forma que la clave se
utiliza para localizar en la estructura de datos la información asociada (es decir, el
valor). En un mapa no existen elementos con claves repetidas y la búsqueda de un valor
asociado a una clave es muy eficiente. En las transparencias entregadas se encuentra
detallada toda laterminología usada para la estructura mapa y también aparecen algunos
ejemplos. Este tipo de estructuras nos permiten representar, por ejemplo, la información
de cada alumno de una universidad usando como clave su DNI o su número de
matrícula, y siendo el valor el resto de la información almacenada por cada alumno (por
ejemplo, sus datos personales, las asignaturas que tiene cursadas, lasasignaturas en las
que está matriculado, etc). En las transparencias también se presenta una posible
interfaz con las operaciones del TAD Mapa. Algunos de sus métodos más comunes son:
- put (key, value): Inserta en el mapa un valor asociado a la clave
- get (key): Devuelve el valor asociado a la clave
- keySet ( ): Devuelve el conjunto de las claves contenidas en el mapa
- values ( ):...