Programación 3: mapas y diccionarios, colecciones parametrizadas

Universidad de CuencaFacultad de Ingeniería

Tema: Mapas y Diccionarios – Colecciones Parametrizadas

Programación 3

Contenido Mapas y Diccionarios Dictionary HashTable Map HashMap TreeMap Colecciones Parametrizadas Declaración de tipo parametrizado

Mapas y Diccionarios Un diccionario agrupa elementos identificados mediante

claves únicas. Es una colección cuyos elementos son pares y están

formados por un dato y su clave, que identifica de manera unívoca al elemento.

Los diccionarios son contenedores asociativos, también denominados mapas.


dictionary La clase abstracta Dictionary es la interfaz para crear

diccionarios en las colecciones históricas (Vector, Stack, Dictionary, HashTable, Enumeration) y procesa la colección como si fuera un array asociativo al que se accede por una clave.

La llave y el valor de cada elemento son de tipo objeto.

dictionaryMétodos Descripción

boolean isEmpty () Retorna true si el diccionario está vacío, y devuelve false si contiene al menos una llave.

int size () Retorna el número de entradas en el diccionario.

Enumeration keys () Retorna una enumeración de las llaves que existen dentro del diccionario.

Enumeration elements () Retorna una enumeración de los valores contenidos en el diccionario.

Object get () Retorna el objeto que contiene el valor asociado con una llave. Si la llave no está en el diccionario, se devuelve null.

Object put (Object key, Object value)

Inserta una valle y su valor dentro del diccionario. Si la llave y su valor ya existen en el diccionario, no lo inserta y devuelve el mismo valor.

Object remove (Object key) Remueve la llave y su valor. Retorna el valor asociado con la llave. Si la llave no se encuentra en el diccionario, retorna null.


Hashtable HashTable extiende Dictionary, permitiendo que se pueda

utilizar para agrupar datos asociativos. HashTable se comporta como una tabla hash. Dispersa los

elementos según el código que devuelve el método hashCode() del objeto clave.

hashtable La clase de los objetos “clave” debe disponer del método int

hashCode(), utilizado para dispersar el elemento. También deben disponer del método equals() para poder

realizar búsquedas y comparaciones.

hashtable

El método hashCode(). Sirve para comparar objetos de una forma más rápido en

estructuras Hash, ya que solo devuelve un número entero (key).

Hashtable

Constructores Descripción

public Hashtable(); Instancia una tabla vacía, con capacidad inicial de 11 y un factor de carga de 0.75.

public Hashtable(int cap); Instancia una tabla vacía, con capacidad inicial de cap y un factor de carga de 0.75.

public Hashtable(int cap, float factorCarga); Instancia una tabla vacía, con una capacidad inicial de cap y un factor de carga de factorCarga.

public Hashtable(Map mapa); Instancia una tabla con los elementos de mapa.

HashtableFactor de carga.

f(n, N) = n / N

hashtable

Métodos Descripciónvoid putAll (Map mapa); Inserta todos los elementos de mapa dentro de la

Hashtable.

boolean containsValue (Object valor);Devuelve true si encuentra valor en el conjunto de valores de la Hashtable, devuelve false en caso contrario.

boolean containsKey (Object clave);Devuelve true si encuentra clave en el conjunto de claves de la Hashtable, devuelve false en caso contrario.

Set keySet (); Devuelve un conjunto de claves de la Hashtable.

Collection values (); Devuelve una colección con los valores de la Hashtable.

Set entrySet (); Devuelve un conjunto con los elementos de la Hashtable.

hashtable

Hashtable

hashtable


map Almacenan información formada por parejas (valor, clave). Java 2 incluye a sus librerías la interfaz Map, la cual no

deriva de Collection.

La interfaz Map establece el comportamiento común de todos las implementaciones concretas de diccionarios.

MapMétodos Descripción

int size() Retorna el número de entradas en el mapa.

boolean isEmpty() Retorna true si el mapa está vacío, y devuelve false si contiene al menos una llave.

boolean containsValue (Object valor);

Devuelve true si encuentra valor en el conjunto de valores del mapa, devuelve false en caso contrario.

boolean containsKey (Object clave);

Devuelve true si encuentra clave en el conjunto de claves del mapa, devuelve false en caso contrario.

Object get() Retorna el objeto que contiene el valor asociado con una llave. Si la llave no está en el mapa, se devuelve null.

Object put(Object key, Object value)

Inserta una clave y su valor dentro del mapa. Si la llave ya existe, reemplaza el valor antiguo y devuelve éste, en caso contrario null.

void putAll (Map mapa); Inserta todos los elementos de mapa dentro de un nuevo mapa.

Set keySet (); Devuelve un conjunto de claves del mapa.

Collection values (); Devuelve una colección con los valores del mapa.

Set entrySet (); Devuelve un conjunto con los elementos del mapa.


Hashmap Organizan los elementos en una tabla hash, a su vez

proporciona una eficiencia constante a las operaciones de búsqueda e inserción.

Sus elementos pares (clave, valor) se guardan en un array de objetos de tipo Entry: Entry [ ] tabla.

Permite que haya claves y valores null.

Hashmap


public HashMap(); Instancia un HashMap vacío, con capacidad inicial de 11 y un factor de carga de 0.75.

public HashMap(int cap); Instancia un HashMap vacío, con capacidad inicial de cap y un factor de carga de 0.75.

public HashMap(int cap, float factorCarga);

Instancia un HashMap vacío, con una capacidad inicial de cap y un factor de carga de factorCarga.

public HashMap(Map mapa); Instancia un HashMap con los elementos de mapa.

Hashmap Dispone de los métodos heredados de AbstractMap y los

definidos al implementar la interfaz Map. Se pueden buscar elementos por clave o valor con

containsKey() y containsValue().

Insertar un elemento con put(), o insertar todos los elementos de otro mapa con putAll().

Eliminar un elemento por argumento con remove(). Obtener el conjunto de claves con keySet(), una colección de

valores con values() y un conjunto de elementos con entrySet().

Obtener el valor de una clave con get().

Hashmap

Métodos Descripción

public Object getKey(); Devuelve la clave de la entrada.

public Object getValue(); Devuelve el valor de la entrada.

public Object setValue(Object nuevoVal);

Cambia el valor de la entrada por el que se recibe como parámetro nuevoVal, y devuelve el valor antiguo.

public String toString(); Devuelve una cadena de la entrada, de formato: “clave = valor”.

Hashmap

Hashmap

Hashmap


treemap Mantiene en orden sus elementos utilizando la estructura

árbol rojo-negro.

Se ordena según su campo clave. La clase Treemap implementa los métodos de la interfaz

SortedMap para la ordenación de sus claves. Al igual que HashMap, Treemap incluye la definición de la

clase static Entry.

treemap

Los Árboles Rojo-Negro: Todo nodo es rojo o es negro. El nodo raíz siempre es negro. Todas las hojas (Null) son negras. Todo nodo rojo debe tener dos nodos hijos negros. Cada camino desde un nodo dado a sus hojas

descendientes contiene el mismo número de nodos negros.

treemap


public TreeMap(); Construye un nuevo TreeMap vacío, utilizando el orden natural de las claves.

public TreeMap(Comparator c); Construye un nuevo TreeMap vacío, utilizando el orden de c.

public TreeMap(Map mapa);Construye un nuevo TreeMap con los elementos de mapa. Ordenados según el orden natural de sus claves.

public TreeMap(SortedMap mapa);

Construye un nuevo TreeMap con los elementos de mapa. Ordenados según el orden que especificado en mapa.

treemap

Métodos DescripciónSortedMap subMap(Object desde, Object hasta);

Devuelve un mapa ordenado acotado por desde y hasta.

SortedMap headMap(Object hasta);Devuelve un mapa ordenado cuyas claves son menores que hasta.

SortedMap tailMap(Object desde);Devuelve un mapa ordenado cuyas claves son mayor o igual que desde.

Object firstKey(); Devuelve la primera clave del mapa.

Object lastKey(); Devuelve la última clave del mapa.

treemap

treemap


Colecciones parametrizadas Las colecciones históricas de Java guardan internamente

elementos de tipo Object. Se consigue una máxima generalización, permitiendo que

una colección guarde elementos de cualquier tipo.

COLEcciones parametrizadas Al recuperar elementos de la lista es necesario discernir el

tipo concreto de elemento.

COLEcciones parametrizadas

Ventajas de usar Colecciones Parametrizadas:

El compilador no aceptará que se agregue ningún tipo de dato distinto al especificado en la instanciación de la clase.

No es necesario añadir los castings al recuperar los datos homogéneos de una colección Object.

Se mantiene un mayor control sobre la colección.

COLEcciones parametrizadas Java amplía la declaración de todas las clases e interfaces

relacionados con colecciones para dotarlas de la posibilidad de parametrizar el tipo que va a tener los elementos de una colección.

Declaracion de un tipo parametrizado

Al nombre de la colección le sigue el tipo de los elementos entre paréntesis angulares.

Si se parametrizan dos tipos, como ocurre en los mapas, se separan por comas.

diferencia

Null keys Null values Order Synchronized

Performance

HashTable Prohibited Prohibited No Yes Medium

HashMap Permited Permited No No High

TreeMap Prohibited Permited Yes No Low

¿Que coleccion usar?

Engineering

Programación 3: mapas y diccionarios, colecciones parametrizadas