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.
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
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.
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.
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
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
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)
Capacidad es el numero de bs en la HT.
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.
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 )
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.
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 )
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.
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.
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.
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.
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
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.
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.
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;
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.
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.
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.
Returns a hash code value for the object.
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.
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,
.......
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.
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.
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.
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.
La Estructura de Datos Hash Table es la madre de Estructuras de Datos
más específicas.
Constructor Summary
Constructor Summary
Constructor Summary
Constructor Summary
Constructor Summary
Constructor Summary
Constructor Summary
An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.
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.
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.
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 )
Truncation ( Truncado )
Division ( División )
Folding ( Plegado )
Reverse Folding ( Plegado Invertido )
Digit Analysis ( Analisis )
Objects Address ( Dirección de Objetos )
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 )
Returns the hash code value for this map entry.
The hash code of a map entry e is defined to be:
(e.getKey()==null ? 0 : e.getKey().hashCode()) ^
(e.getValue()==null ? 0 : e.getValue().hashCode())
This ensures that e1.equals(e2)
implies that e1.hashCode()==e2.hashCode()
for any two Entries e1 and e2,
as required by the general contract of Object.hashCode.
Returns the hash code value for this map.
The hash code of a map is defined to be the sum of the hashCodes
of each entry in the map's entrySet view.
This ensures that t1.equals(t2) implies
that t1.hashCode()==t2.hashCode() for any two maps t1 and t2,
as required by the general contract of Object.hashCode.
Overflow Handling ( Manejo de Colisiones )
Linear Probing ( Prueba Lineal )
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 )
Rehashing Probing ( Reconstruccion Tabla )
Identificator-Dependent Increments Probing ( )
Ramdom Probing ( )
Link Probing ( Prueba Enlazada )
|
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 terminologia usada es la siguiente :
Es una colección de elementos sin duplicados. Para encontrar un elemento
se debe tener una copia exacta del elemento que se desea buscar.
Es una colección de pares formados por una clave y un valor. La estructura
de datos encuentra el valor si se le dá la clave. La función de hashing
se aplica solamente a la clave. A los valores asociados a las claves no se aplica
la función de hashing.
Set ---------> Elements
Map ---------> Mappings ---------> ( Key, Value )
Implementaciones de Hash Tables
Implementacion 1
Dictionary
Method Summary
Sole constructor.
Returns an enumeration of the values in this dictionary.
Returns the value to which the key is mapped in this dictionary.
Tests if this dictionary maps no keys to value.
Returns an enumeration of the keys in this dictionary.
Maps the specified key to the specified value in this dictionary.
Removes the key (and its corresponding value) from this dictionary.
Returns the number of entries (dinstint keys) in this dictionary.
Hashtable
Method Summary
Constructs a new, empty hashtable with a default capacity and load factor, which is 0.75.
Constructs a new, empty hashtable with the specified initial capacity and default load factor, which is 0.75.
Constructs a new, empty hashtable with the specified initial capacity and the specified load factor.
Constructs a new hashtable with the same mappings as the given Map.
Clears this hashtable so that it contains no keys.
Creates a shallow copy of this hashtable.
Tests if some key maps into the specified value in this hashtable.
Tests if the specified object is a key in this hashtable.
Returns true if this Hashtable maps one or more keys to this value.
Returns an enumeration of the values in this hashtable.
Returns a Set view of the entries contained in this Hashtable.
Compares the specified Object with this Map for equality, as per the definition in the Map interface.
Returns the value to which the specified key is mapped in this hashtable.
Returns the hash code value for this Map as per the definition in the Map interface.
Tests if this hashtable maps no keys to values.
Returns an enumeration of the keys in this hashtable.
Returns a Set view of the keys contained in this Hashtable.
Maps the specified key to the specified value in this hashtable.
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.
Increases the capacity of and internally reorganizes this hashtable, in order to accommodate and access its entries more efficiently.
Removes the key (and its corresponding value) from this hashtable.
Returns the number of keys in this hashtable.
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).
Returns a Collection view of the values contained in this Hashtable.
Implementacion 2
AbstractCollection
Method Summary
Sole constructor.
Ensures that this collection contains the specified element (optional operation).
Adds all of the elements in the specified collection to this collection (optional operation).
Removes all of the elements from this collection (optional operation).
Returns true if this collection contains the specified element.
Returns true if this collection contains all of the elements in the specified collection.
Returns true if this collection contains no elements.
Returns an iterator over the elements contained in this collection.
Removes a single instance of the specified element from this collection, if it is present (optional operation).
Removes from this collection all of its elements that are contained in the specified collection (optional operation).
Retains only the elements in this collection that are contained in the specified collection (optional operation).
Returns the number of elements in this collection.
Returns an array containing all of the elements in this collection.
Returns an array with a runtime type is that of the specified array and that contains all of the elements in this collection.
Returns a string representation of this collection.
AbstractSet
Method Summary
Sole constructor.
Compares the specified object with this set for equality.
Returns the hash code value for this set.
Removes from this set all of its elements that are contained in the specified collection (optional operation).
HashSet
Method Summary
Constructs a new, empty set; the backing HashMap instance has default capacity and load factor, which is 0.75.
Constructs a new set containing the elements in the specified collection.
Constructs a new, empty set; the backing HashMap instance has the specified initial capacity and default load factor, which is 0.75.
Constructs a new, empty set; the backing HashMap instance has the specified initial capacity and the specified load factor.
Adds the specified element to this set if it is not already present.
Removes all of the elements from this set.
Returns a shallow copy of this HashSet instance: the elements themselves are not cloned.
Returns true if this set contains the specified element.
Returns true if this set contains no elements.
Returns an iterator over the elements in this set.
Removes the given element from this set if it is present.
Returns the number of elements in this set (its cardinality).
AbstractMap
Method Summary
Sole constructor.
Removes all mappings from this map (optional operation).
Returns true if this map contains a mapping for the specified key.
Returns true if this map maps one or more keys to this value.
Returns a set view of the mappings contained in this map.
Compares the specified object with this map for equality.
Returns the value to which this map maps the specified key.
Returns the hash code value for this map.
Returns true if this map contains no key-value mappings.
Returns a Set view of the keys contained in this map.
Associates the specified value with the specified key in this map (optional operation).
Copies all of the mappings from the specified map to this map (optional operation).
Removes the mapping for this key from this map if present (optional operation).
Returns the number of key-value mappings in this map.
Returns a string representation of this map.
Returns a collection view of the values contained in this map.
HashMap
Method Summary
Constructs a new, empty map with a default capacity and load factor, which is 0.75.
Constructs a new, empty map with the specified initial capacity and default load factor, which is 0.75.
Constructs a new, empty map with the specified initial capacity and the specified load factor.
Constructs a new map with the same mappings as the given map.
Removes all mappings from this map.
Returns a shallow copy of this HashMap instance: the keys and values themselves are not cloned.
Returns true if this map contains a mapping for the specified key.
Returns true if this map maps one or more keys to the specified value.
Returns a collection view of the mappings contained in this map.
Returns the value to which this map maps the specified key.
Returns true if this map contains no key-value mappings.
Returns a set view of the keys contained in this map.
Associates the specified value with the specified key in this map.
Copies all of the mappings from the specified map to this one.
Removes the mapping for this key from this map if present.
Returns the number of key-value mappings in this map.
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
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.
A map entry (key-value pair).
Removes all mappings from this map (optional operation).
Returns true if this map contains a mapping for the specified key.
Returns true if this map maps one or more keys to the specified value.
Returns a set view of the mappings contained in this map.
Compares the specified object with this map for equality.
Returns the value to which this map maps the specified key.
Returns the hash code value for this map.
Returns true if this map contains no key-value mappings.
Returns a set view of the keys contained in this map.
Associates the specified value with the specified key in this map (optional operation).
Copies all of the mappings from the specified map to this map (optional operation).
Removes the mapping for this key from this map if present (optional operation).
Returns the number of key-value mappings in this map.
Returns a collection view of the values contained in this map.
Map.Entry
Compares the specified object with this entry for equality.
Returns the key corresponding to this entry.
Returns the value corresponding to this entry.
Returns the hash code value for this map entry.
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 |
| | | |
| | | |
*-----------------* *-----------------*