Estructura de Datos : Hash Tables ( Tablas Mutiladas )


Definiciones

Hash Table

Dada una colección de elementos, existe la necesidad de encontrar uno de los elementos rapidamente.Una solución a este requerimiento es implementar una Hash Table. En el caso de una Hash Table se busca a través de computar una función aritmética. Otra solución bien conocida, es implementar un Arbol de Búsqueda. En el caso de un Arbol de Búsqueda se busca a través de una secuencia de comparaciones.
La estructura de datos Hash Table sera referenciada como Hash Table = HT.

Las ventajas de las HTs son :

Las desventajas de las HTs son : Desde el punto de vista computacional, una Hash Table es un espacio de memoria contigua subdividida en buckets. Hash puede traducirse como revolver, picar y mutilar. Si bien mostraremos ejemplos de implementaciones de HTs con arreglos, normalmente se implementan con un arreglo y listas enlazadas.

Identificadores

Los Identificadores es por lo que se busca en una HT. Asumamos que existen n Identificadores concretos, en un momento, en la HT. Dichos Identificadores seran referenciados como Identificadores = I = I1, I2, I3, ......., Ii,....... In

Hash Code

La HT computa un entero, llamado hash code, por cada I. La computacion del hash code es rapida y solo depende del I en cuestion, y para nada del resto de los Is. Los hash codes seran referenciados como Hash Codes = HC = HC1, HC2, HC3, ......, HCi, ......, HCn.

Número de Identificadores en Uso

La cantidad de elementos, y por lo tanto, la cantidad de Is, que tiene una HT en un determinado momento es variable. Se aceptan que ingresen nuevos elementos, de la misma forma que se acepta se elimen elementos existentes en la HT. En este caso estamos pensando en los Is que ocupan un lugar en la Hash Table en un determinado momento. Los Is presentes en un momento en una HT seran referenciados como Número de Identificadores en Uso = NIU.

Número Total de Posibles Identificadores

En este caso estamos pensando en todos lo posibles y potenciales Is que en algún momento pueden incorporarse a la HT. Este numero no varia durante la vida de la HT, siendo una constante de la estructura de datos. Seran referenciados como Número Total de Posibles Identificadores = NTPI

Densidad de Identificadores

Generalmente NTPI es mucho mayor que NIU e interesa definir la densidad actual de identificadores con respecto del potencial. Dicho factor sera referenciado como Densidad de Identificadores = DI = NIU / NTPI

Buckets

Bucket significa cubo o balde. En una HT hay b Buckets. Cuando se crea una HT se crea con una cantidad determinada de Buckets. Pero durante la vida de la HT puede crecer, según se necesite, la cantidad de Buckets. Los Buckets seran referenciados como Buckets = b = HT(0), HT(1), ........, HT(b-1)

Capacidades

Capacidad es el numero de bs en la HT.

Slots

Un b tiene s Slots, y usualmente s vale 1. Un b lleno es un b que tiene todos sus Slots ocupados. Los Slots seran referenciados como Slots = s = s(1), s(2), ........, s(s) En cada s hay un I. Las entidades que se acomenten en la busqueda de un elemento son : HT -----> b -----> s -----> Registro.

Densidad de Carga

La densidad de Carga también se la conoce como factor de carga (load factor) y define el espacio disponible contra el necesario para almacenar los Is. La Densidad de Carga sera referenciada como Densidad de Carga = DC = NIU / ( s x b )

Hashing Function

La mejor Hash Function es aquella que es facil de computar y no produce colisiones. Este último requerimiento es imposible si DI es menor que 1. La Hashing Function sera referenciada como Hashing Function = HF = f ( Ii ) Es mejor pensar que la HF es buena si minimiza las Colisiones. Una Hashing Function transforma un Identificador en una dirección de un Bucket de una HT. Una Hashing Funtion es de Distribucion Uniforme si la probabilidad de que f ( Ii ) = i sea 1 / b para todo los Buckets i.

Sinónimos

La aplicación de la HF sobre dos Is distintos puede dar el mismo resultado. Si ello ocurre estamos en presencia de Is sinónimos respecto de la HF, y ocurre una Colisión. Sinónimos = f ( I1 ) = f ( I2 )

Colisiones

Cada vez que dos Is distintos son " hashed " en el mismo b estamos en presencia de una Colisión. En el caso de Colisiones un b almacena multiples Is.

Overflow

Ocurre un Overflow cuando un I que ingresará a la HT es " hashed " en un b lleno. Si s = 1 Colisiones y Overflows ocurren simultaneamente. Como s normalmente es 1 o chico, invariablemente ocurrirán Overflows, lo que me obliga a contar con Estratégias de Overflows.

Rehashing

Existe un mecanismo llamado Rehashing que funciona de la siguiente manera. Si se conoce la cantidad de Is iniciales, normalmente, se crea la HT con una Capacidad Inicial aproximada al 150 % de los Is. Por ejemplo, si inicialmente tengo 100 Is se crea una HT con 150 b. Inicialmente el factor de carga sera 100/150 = 0,66666...66. Seguidamente la HT comienza a llenarse por la incorporacion de nuevos Is. En todo momento la HT contabiliza el factor de carga y cuando este supera, por ejemplo, el 0,75, se dispara el proceso de Rehashing, proceso que crea una nueva HT con el doble de capacidad que la actual, se mudan todos los elementos de la HT vieja a la nueva y se elimina la HT original.

Funciones Primitivas

Funciones Secundarias


Ejemplos con Nombres de Variables de un Lenguaje de Programacion

Veamos dos ejemplos con nombres de variables del Lenguaje Fortran. En el primer ejemplo limitaremos el nombre de las variables a dos caracteres. El primero debe ser una letra ( 26 caracteres ) y el segundo debe ser una letra o un numero ( 36 caracteres ). Asumamos que en un determinado momento estan presentes los siguientes Is.

Identificadores = I = ( GA, D,A, G, L, A2, A1, A3, A4, E )

NTPI = 26 * ( 26 + 10 ) = 936; NIU =10; DI = 10 / 936 = 0,01068; b = 26; s = 2; DC = 10 / ( 2 x 26 ) = 0,19230;

Hashing Function = f ( Ii ) = Numero de órden, dentro del alfabeto, de la primer letra del identificador

f(GA) =7; f(D) = 4; f(A) = 1; f(G) = 7; f(L) = 12; f(A2) = 1; ........; f(E) = 5.


 

SLOT 1

SLOT 2

1

A

A2

2

0

0

3

0

0

4

D

0

5

0

0

6

0

0

7

GA

G

...

...

...

...

...

...

...

...

...

26

0

0



En el segundo ejemplo limitaremos las variables a cinco caracteres. Las variables deben comenzar con un letra ( 26 caracteres ) y pueden tener hasta 5 caracteres. A partir de la segunda posicion pueden ser letras o numeros ( 36 caracteres ). Asumamos ademas que en este momento tengo 100 Is en la HT.

T = 26 + ( 26 x 36 ) + ( 26 x 36 x 36 ) + ( 26 x 36 x 36 x 36 ) + ( 26 x 36 x 36 x 36 x 36 ) + ( 26 x 36 x 36 x 36 x 36 x 36 ) > 1,6 x 1.000.000.000

DI = 100 / 1,6 x 1.000.000.000 = 0,000.000.062.5

En general, DI es muy bajo. Este segundo ejemplo es mas representativo de situaciones reales.


Tipos de Hashing Function ( Tipos de Funciones de Búsqueda )

Mid-Square ( Medio-Cuadrado )

Si Ii es el Identificador, hago el cuadrado de Ii y tomo r bits del medio del resultado. Por lo tanto tendre que disponer un rango de Buckets, conocido tambien como Espacio de Buckets, igual a 2 elevado a r, siendo ese el el tamano de la HT. Hay una reduccion importante entre el Bucket Space y el Indentifier Space. Por ejemplo, si tengo identificadores numericos de 6 digitos, de 0 a 999999, el espacio de indentificadores es de 1.000.000 de elementos. Si tomo 8 bits del identificador tengo un espacio de buckets de 256.

Truncation ( Truncado )

Ignorar parte del Identificador y usar el resto, directamente como la dirección del bucket. Por ejemplo, Identificador de ocho dígitos enteros. HT de 1000 buckets. Tomar 1er., 2do. y 5to. dígito desde la derecha. Ignorar el resto de los digitos. I = 62538194. Dirección del bucket = 394. La cantidad de digitos que se seleccionan determinan la capacidad de la HT. Si selecciono 3 digitos la HT es de 1000 buckets. Si selecciono 2 digitos la HT es de 100 buckets.

Division ( División )

Dividir el Identificador por el tamaño de la HT. El resto es la dirección del bucket. Por ejemplo, Identificador de ocho dígitos enteros. HT de 1000 buckets. I = 62538194. División = 62538194 / 1000. Resto = 194. Dirección del bucket = 194. Si la HT tiene b buckets el rango de buckets es de 0 a b-1;

Folding ( Plegado )

Particionar el Identificador en varias partes. Combinar las partes usando adiciones o multiplicaciones. Por ejemplo, Identificador de ocho dígitos enteros. HT de 1000 buckets. Particinar en grupos de 3, 3 y 2 dígitos. Sumar los grupos. Truncar si es necesario. I = 62538194. Grupo 1 = 625. Grupo 2 = 381. Grupo 3 = 94. Suma = 625 + 381 + 94 = 1100. Truncado = 100.

Reverse Folding ( Plegado Invertido )

Particionar el Identificador en varias partes. Algunas de las partes invertirlas. Combinar las partes usando adiciones o multiplicaciones. Por ejemplo, Identificador de ocho dígitos enteros. HT de 1000 buckets. Particinar en grupos de 3, 3 y 2 dígitos. Revierto algunas partes. Sumar los grupos. Truncar si es necesario. I = 62538194. Grupo 1 = 625. Grupo 2 = 381 Revertido = 183. Grupo 3 = 94 Revertido = 49. Suma = 625 + 183 + 49 = 857. Truncado = 857.

Digit Analysis ( Analisis )

Cuando las tablas son estaticas los identificadores se conocen de antemano y puedo seleccionar los digitos con uniformidad de valores. Los digitos no uniformes son descartados. Con los digitos con uniformidad de valores compongo el hash code. Ejemplo, siendo el identificador compuesto por seis digito, XXXXXX, y siendo el tercero y el quinto uniformes, XXUXUX, uso esos digitos para componer el hash code UU. Los digitos no uniformes no los uso, los descarto.

Objects Address ( Dirección de Objetos )

Returns a hash code value for the object.
This method is supported for the benefit of hashtables such as those provided by java.util.Hashtable.
The general contract of hashCode is:

As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)

Objects ( Objetos )


Overflow Handling ( Manejo de Colisiones )

Linear Probing ( Prueba Lineal )

Comenzar con la dirección del bucket calculado por la HF. En caso de colisión, a la dirección del bucket sumarle 1. Repetir hasta encontrar un slot libre.
Veamos el siguiente ejemplo. Identificadores = ( GA, D, A, G, L, A2, A1, A3, A4, Z, ZA, E )
GA, D, A, L y Z entran directo. G, A2, A1, A3, A4, ZA entran con prueba lineal. En particular ZA entra con prueba lineal circular.

1 A
2 A2
3 A1
4 D
5 A3
6 A4
7 GA
8 G
9 ZA
10 E
11 0
12 L
13 0
14 0
... ...
... ...
... ...
... ...
25 0
26 Z

Quadratic Probing ( Prueba Cuadrática )

Comenzar con la dirección del bucket calculado por la HF. En caso de colisión, a la dirección del bucket sumarle 1. En caso de colisión, a la dirección del bucket sumarle 4. En caso de colisión, a la dirección del bucket sumarle 8. Seguir hasta encontrar un slot libre, usando la formula " DIRECCION DEL BUCKET + i*2, para i = 1, 2, 3, .......

Rehashing Probing ( Reconstruccion Tabla )

Comenzar con la dirección del bucket calculado por la HF. En caso de colisión, aplicar una segunda HF sobre el resultado anterior. En caso de colisión, aplicar una tercera HF. Utilizar sucesivas HF hasta encontrar un slot libre.

Identificator-Dependent Increments Probing ( )

Comenzar con la dirección del bucket calculado por la HF. En caso de colisión, separar un dígito del Identificador. Incrementar la dirección del bucket con el dígito seleccionado hasta encontrar un slot libre.

Ramdom Probing ( )

Comenzar con la dirección del bucket calculado por la HF. En caso de colisión, obtener el incremento desde un generador de número al azar, tal que siempre genere la misma secuencia a partir de la condición inicial. Incrementar la dirección del bucket calculado, según el incremento obtenido desde el generador de números al azar. Repetir hasta encontrar un slot libre.

Link Probing ( Prueba Enlazada )

Comenzar con la dirección del bucket calculado por la HF. En caso de colisión, agregar un nodo a la lista enlazada que se inicia en la dirección del bucket calculado por la HF.


                  |
          Arreglo | Listas Enlazadas
                  |

            *---*    *--------*    *--------*    *--------*    *--------*    *--------*
          1 | *-|--->| A4 | *-|--->| A3 | *-|--->| A1 | *-|--->| A2 | *-|--->| A  | 0 |
            *---*    *--------*    *--------*    *--------*    *--------*    *--------*
            *---*
          2 | 0 |
            *---*
            *---*
          3 | 0 |
            *---*
            *---*    *--------*
          4 | *-|--->| D  | 0 |
            *---*    *--------*
            *---*    *--------*
          5 | *-|--->| E  | 0 |
            *---*    *--------*
            *---*
          6 | 0 |
            *---*
            *---*    *--------*    *--------*
          7 | *-|--->| G  | *-|--->| GA | 0 |
            *---*    *--------*    *--------*
            *---*
          8 | 0 |
            *---*
            *---*
          9 | 0 |
            *---*
            *---*
         10 | 0 |
            *---*
            *---*
         11 | 0 |
            *---*
            *---*    *--------*
         12 | *-|--->| L  | 0 |
            *---*    *--------*
             ...
             ...
             ...
             ...
            *---*    *--------*    *--------*
         26 | *-|--->| ZA | *-|--->| Z  | 0 |
            *---*    *--------*    *--------*


Hash Tables Específicas

La Estructura de Datos Hash Table es la madre de Estructuras de Datos más específicas.

La terminologia usada es la siguiente :

             Set ---------> Elements

             Map ---------> Mappings ---------> ( Key, Value )


Implementaciones de Hash Tables

Implementacion 1

Dictionary

Constructor Summary

Method Summary
  • abstract Enumeration elements()
    Returns an enumeration of the values in this dictionary.
  • abstract Object get(Object key)
    Returns the value to which the key is mapped in this dictionary.
  • abstract boolean isEmpty()
    Tests if this dictionary maps no keys to value.
  • abstract Enumeration keys()
    Returns an enumeration of the keys in this dictionary.
  • abstract Object put(Object key, Object value)
    Maps the specified key to the specified value in this dictionary.
  • abstract Object remove(Object key)
    Removes the key (and its corresponding value) from this dictionary.
  • abstract int size()
    Returns the number of entries (dinstint keys) in this dictionary.

Hashtable

Constructor Summary

Method Summary
  • void clear()
    Clears this hashtable so that it contains no keys.
  • Object clone()
    Creates a shallow copy of this hashtable.
  • boolean contains(Object value)
    Tests if some key maps into the specified value in this hashtable.
  • boolean containsKey(Object key)
    Tests if the specified object is a key in this hashtable.
  • boolean containsValue(Object value)
    Returns true if this Hashtable maps one or more keys to this value.
  • Enumeration elements()
    Returns an enumeration of the values in this hashtable.
  • Set entrySet()
    Returns a Set view of the entries contained in this Hashtable.
  • boolean equals(Object o)
    Compares the specified Object with this Map for equality, as per the definition in the Map interface.
  • Object get(Object key)
    Returns the value to which the specified key is mapped in this hashtable.
  • int hashCode()
    Returns the hash code value for this Map as per the definition in the Map interface.
  • boolean isEmpty()
    Tests if this hashtable maps no keys to values.
  • Enumeration keys()
    Returns an enumeration of the keys in this hashtable.
  • Set keySet()
    Returns a Set view of the keys contained in this Hashtable.
  • Object put(Object key, Object value)
    Maps the specified key to the specified value in this hashtable.
  • void putAll(Map t)
    Copies all of the mappings from the specified Map to this Hashtable These mappings will replace any mappings that this Hashtable had for any of the keys currently in the specified Map.
  • protected void rehash()
    Increases the capacity of and internally reorganizes this hashtable, in order to accommodate and access its entries more efficiently.
  • Object remove(Object key)
    Removes the key (and its corresponding value) from this hashtable.
  • int size()
    Returns the number of keys in this hashtable.
  • String toString()
    Returns a string representation of this Hashtable object in the form of a set of entries, enclosed in braces and separated by the ASCII characters ", " (comma and space).
  • Collection values()
    Returns a Collection view of the values contained in this Hashtable.

Implementacion 2

AbstractCollection

Constructor Summary

Method Summary
  • boolean add(Object o)
    Ensures that this collection contains the specified element (optional operation).
  • boolean addAll(Collection c)
    Adds all of the elements in the specified collection to this collection (optional operation).
  • void clear()
    Removes all of the elements from this collection (optional operation).
  • boolean contains(Object o)
    Returns true if this collection contains the specified element.
  • boolean containsAll(Collection c)
    Returns true if this collection contains all of the elements in the specified collection.
  • boolean isEmpty()
    Returns true if this collection contains no elements.
  • abstract Iterator iterator()
    Returns an iterator over the elements contained in this collection.
  • boolean remove(Object o)
    Removes a single instance of the specified element from this collection, if it is present (optional operation).
  • boolean removeAll(Collection c)
    Removes from this collection all of its elements that are contained in the specified collection (optional operation).
  • boolean retainAll(Collection c)
    Retains only the elements in this collection that are contained in the specified collection (optional operation).
  • abstract int size()
    Returns the number of elements in this collection.
  • Object[] toArray()
    Returns an array containing all of the elements in this collection.
  • Object[] toArray(Object[] a)
    Returns an array with a runtime type is that of the specified array and that contains all of the elements in this collection.
  • String toString()
    Returns a string representation of this collection.

AbstractSet

Constructor Summary

  • protected AbstractSet()
    Sole constructor.
Method Summary
  • boolean equals(Object o)
    Compares the specified object with this set for equality.
  • int hashCode()
    Returns the hash code value for this set.
  • boolean removeAll(Collection c)
    Removes from this set all of its elements that are contained in the specified collection (optional operation).

HashSet

Constructor Summary

  • HashSet()
    Constructs a new, empty set; the backing HashMap instance has default capacity and load factor, which is 0.75.
  • HashSet(Collection c)
    Constructs a new set containing the elements in the specified collection.
  • HashSet(int initialCapacity)
    Constructs a new, empty set; the backing HashMap instance has the specified initial capacity and default load factor, which is 0.75.
  • HashSet(int initialCapacity, float loadFactor)
    Constructs a new, empty set; the backing HashMap instance has the specified initial capacity and the specified load factor.
Method Summary
  • boolean add(Object o)
    Adds the specified element to this set if it is not already present.
  • void clear()
    Removes all of the elements from this set.
  • Object clone()
    Returns a shallow copy of this HashSet instance: the elements themselves are not cloned.
  • boolean contains(Object o)
    Returns true if this set contains the specified element.
  • boolean isEmpty()
    Returns true if this set contains no elements.
  • Iterator iterator()
    Returns an iterator over the elements in this set.
  • boolean remove(Object o)
    Removes the given element from this set if it is present.
  • int size()
    Returns the number of elements in this set (its cardinality).

AbstractMap

Constructor Summary

  • protected AbstractMap()
    Sole constructor.
Method Summary
  • void clear()
    Removes all mappings from this map (optional operation).
  • boolean containsKey(Object key)
    Returns true if this map contains a mapping for the specified key.
  • boolean containsValue(Object value)
    Returns true if this map maps one or more keys to this value.
  • abstract Set entrySet()
    Returns a set view of the mappings contained in this map.
  • boolean equals(Object o)
    Compares the specified object with this map for equality.
  • Object get(Object key)
    Returns the value to which this map maps the specified key.
  • int hashCode()
    Returns the hash code value for this map.
  • boolean isEmpty()
    Returns true if this map contains no key-value mappings.
  • Set keySet()
    Returns a Set view of the keys contained in this map.
  • Object put(Object key, Object value)
    Associates the specified value with the specified key in this map (optional operation).
  • void putAll(Map t)
    Copies all of the mappings from the specified map to this map (optional operation).
  • Object remove(Object key)
    Removes the mapping for this key from this map if present (optional operation).
  • int size()
    Returns the number of key-value mappings in this map.
  • String toString()
    Returns a string representation of this map.
  • Collection values()
    Returns a collection view of the values contained in this map.

HashMap

Constructor Summary

  • HashMap()
    Constructs a new, empty map with a default capacity and load factor, which is 0.75.
  • HashMap(int initialCapacity)
    Constructs a new, empty map with the specified initial capacity and default load factor, which is 0.75.
  • HashMap(int initialCapacity, float loadFactor)
    Constructs a new, empty map with the specified initial capacity and the specified load factor.
  • HashMap(Map t)
    Constructs a new map with the same mappings as the given map.
Method Summary
  • void clear()
    Removes all mappings from this map.
  • Object clone()
    Returns a shallow copy of this HashMap instance: the keys and values themselves are not cloned.
  • boolean containsKey(Object key)
    Returns true if this map contains a mapping for the specified key.
  • boolean containsValue(Object value)
    Returns true if this map maps one or more keys to the specified value.
  • Set entrySet()
    Returns a collection view of the mappings contained in this map.
  • Object get(Object key)
    Returns the value to which this map maps the specified key.
  • boolean isEmpty()
    Returns true if this map contains no key-value mappings.
  • Set keySet()
    Returns a set view of the keys contained in this map.
  • Object put(Object key, Object value)
    Associates the specified value with the specified key in this map.
  • void putAll(Map t)
    Copies all of the mappings from the specified map to this one.
  • Object remove(Object key)
    Removes the mapping for this key from this map if present.
  • int size()
    Returns the number of key-value mappings in this map.
  • Collection values()
    Returns a collection view of the values contained in this map.


Interfases


                         *-----------------*                          *-----------------*             *-----------------*
                         |                 |                          |                 |             |                 |
                         |                 |                          |                 |             |                 |
                         |    Collection   |                          |       Map       |             |    Iterator     |
                         |                 |                          |                 |             |                 |
                         |                 |                          |                 |             |                 |
                         *-----------------*                          *-----------------*             *-----------------*
                             A         A                                       A                               A
                             |         |                                       |                               |
                             |         |                                       |                               |
                     +-------+         +-------+                               |                               |
                     |                         |                               |                               |
                     |                         |                               |                               |
                     |                         |                               |                               |
            *-----------------*       *-----------------*             *-----------------*             *-----------------*
            |                 |       |                 |             |                 |             |                 |
            |                 |       |                 |             |                 |             |                 |
            |      List       |       |       Set       |             |    SortedMap    |             |  ListIterator   |
            |                 |       |                 |             |                 |             |                 |
            |                 |       |                 |             |                 |             |                 |
            *-----------------*       *-----------------*             *-----------------*             *-----------------*
                                               A
                                               |
                                               |
                                               |
                                               |
                                               |
                                               |
                                      *-----------------*
                                      |                 |
                                      |                 |
                                      |    SortedSet    |
                                      |                 |
                                      |                 |
                                      *-----------------*

Map

An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.
This interface takes the place of the Dictionary class, which was a totally abstract class rather than an interface.
The Map interface provides three collection views, which allow a map's contents to be viewed as a set of keys, collection of values, or set of key-value mappings. The order of a map is defined as the order in which the iterators on the map's collection vi ews return their elements. Some map implementations, like the TreeMap class, make specific guarantees as to their order; others, like the HashMap class, do not.
Note: great care must be exercised if mutable objects are used as map keys. The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map. A special case of thi s prohibition is that it is not permissible for a map to contain itself as a key. While it is permissible for a map to contain itself as a value, extreme caution is advised: the equals and hashCode methods are no longer well defined on a such a map.
All general-purpose map implementation classes should provide two "standard" constructors: a void (no arguments) constructor which creates an empty map, and a constructor with a single argument of type Map, which creates a new map with the same key-value mappings as its argument. In effect, the latter constructor allows the user to copy any map, producing an equivalent map of the desired class. There is no way to enforce this recommendation (as interfaces cannot contain constructors) but all of the genera l-purpose map implementations in the SDK comply.

  • Inner Class Summary
    • static interface Map.Entry
      A map entry (key-value pair).
  • Method Summary
    • void clear()
      Removes all mappings from this map (optional operation).
    • boolean containsKey(Object key)
      Returns true if this map contains a mapping for the specified key.
    • boolean containsValue(Object value)
      Returns true if this map maps one or more keys to the specified value.
    • Set entrySet()
      Returns a set view of the mappings contained in this map.
    • boolean equals(Object o)
      Compares the specified object with this map for equality.
    • Object get(Object key)
      Returns the value to which this map maps the specified key.
    • int hashCode()
      Returns the hash code value for this map.
    • boolean isEmpty()
      Returns true if this map contains no key-value mappings.
    • Set keySet()
      Returns a set view of the keys contained in this map.
    • Object put(Object key, Object value)
      Associates the specified value with the specified key in this map (optional operation).
    • void putAll(Map t)
      Copies all of the mappings from the specified map to this map (optional operation).
    • Object remove(Object key)
      Removes the mapping for this key from this map if present (optional operation).
    • int size()
      Returns the number of key-value mappings in this map.
    • Collection values()
      Returns a collection view of the values contained in this map.

Map.Entry

A map entry (key-value pair). The Map.entrySet method returns a collection-view of the map, whose elements are of this class. The only way to obtain a reference to a map entry is from the iterator of this collection-view. These Map.Entry objects are valid only for the duration of the iteration; more formally, the behavior of a map entry is undefined if the backing map has been modified after the entry was returned by the iterator, except through the iterator's own remove operation, or through the setValue operation on a map entry returned by the iterator.

  • Method Summary
    • boolean equals(Object o)
      Compares the specified object with this entry for equality.
    • Object getKey()
      Returns the key corresponding to this entry.
    • Object getValue()
      Returns the value corresponding to this entry.
    • int hashCode()
      Returns the hash code value for this map entry.
    • Object setValue(Object value)
      Replaces the value corresponding to this entry with the specified value (optional operation).


Clases


                                        *-----------------*                                                                    *-----------------*
                                        |                 |                                                                    |                 |
                                        |    Abstract     |                                                                    |    Abstract     |
                                        |                 |                                                                    |                 |
                                        |   Collection    |                                                                    |       Map       |
                                        |                 |                                                                    |                 |
                                        *-----------------*                                                                    *-----------------*
                                            A         A                                                                            A         A
                                            |         |                                                                            |         |
                                            |         |                                                                            |         |
                      +---------------------+         +---------------------+                                              +-------+         +-------+
                      |                                                     |                                              |                         |
                      |                                                     |                                              |                         |
                      |                                                     |                                              |                         |
             *-----------------*                                   *-----------------*                            *-----------------*       *-----------------*
             |                 |                                   |                 |                            |                 |       |                 |
             |    Abstract     |                                   |    Abstract     |                            |                 |       |                 |
             |                 |                                   |                 |                            |     HashMap     |       |     TreeMap     |
             |      List       |                                   |       Set       |                            |                 |       |                 |
             |                 |                                   |                 |                            |                 |       |                 |
             *-----------------*                                   *-----------------*                            *-----------------*       *-----------------*
                 A         A                                           A         A
                 |         |                                           |         |
                 |         |                                           |         |
         +-------+         +-------+                           +-------+         +-------+
         |                         |                           |                         |
         |                         |                           |                         |
         |                         |                           |                         |
*-----------------*       *-----------------*         *-----------------*       *-----------------*
|                 |       |                 |         |                 |       |                 |
|    Abstract     |       |                 |         |                 |       |                 |
|                 |       |    ArrayList    |         |     HashSet     |       |     TreeSet     |
| SequentialList  |       |                 |         |                 |       |                 |
|                 |       |                 |         |                 |       |                 |
*-----------------*       *-----------------*         *-----------------*       *-----------------*
         A
         |
         |
         |
         |
         |
         |
*-----------------*
|                 |
|                 |
|   LinkedList    |
|                 |
|                 |
*-----------------*





*-----------------*                                   *-----------------*
|                 |                                   |                 |
|    Abstract     |                                   |                 |
|                 |                                   |   Dictionary    |
|      List       |                                   |                 |
|                 |                                   |                 |
*-----------------*                                   *-----------------*
         A                                                     A
         |                                                     |
         |                                                     |
         |                                                     |
         |                                                     |
         |                                                     |
         |                                                     |
*-----------------*                                   *-----------------*
|                 |                                   |                 |
|                 |                                   |                 |
|      Vector     |                                   |    HashTable    |
|                 |                                   |                 |
|                 |                                   |                 |
*-----------------*                                   *-----------------*
         A                                                     A
         |                                                     |
         |                                                     |
         |                                                     |
         |                                                     |
         |                                                     |
         |                                                     |
*-----------------*                                   *-----------------*
|                 |                                   |                 |
|                 |                                   |                 |
|      Stack      |                                   |   Properties    |
|                 |                                   |                 |
|                 |                                   |                 |
*-----------------*                                   *-----------------*