ceso de hashing está diseñado para distribuir los valores en toda la tabla, por lo que se asume que se encontrará 
una celda disponible con sólo unas cuantas transformaciones de hashing.

Otro esquema utiliza un hash para localizar la primera celda candidata. Si esa celda está ocupada, se buscan 

celdas sucesivas en orden, hasta que se encuentra una disponible. El proceso de obtención funciona de la misma 
forma: se aplica hash a la clave una vez para determinar la función inicial y comprobar si contiene los datos desea-
dos. Si es así, la búsqueda termina. En caso contrario, se busca linealmente en las celdas sucesivas hasta encontrar 
los datos deseados.

La solución más popular a las colisiones en las tablas de hash es hacer que cada celda de la tabla sea una 

“cubeta” de hash que, por lo general, viene siendo una lista enlazada de todos los pares clave/valor que se asocian 
con esa celda. Ésta es la solución que implementan las clases 

Hashtable

 y 

HashMap

 (del paquete 

java.util

).

Tanto 

Hashtable

 como 

HashMap

 implementan a la interfaz 

Map

. Las principales diferencias entre ellas son que 

HashMap

 no está sincronizada (varios subprocesos no deben modifi car un objeto 

HashMap

 en forma concurrente), 

y permite claves y valores 

null

.

El 

factor de carga

 de una tabla de hash afecta al rendimiento de los esquemas de hashing. El factor de carga 

es la proporción del número de celdas ocupadas en la tabla de hash, con respecto al número total de celdas en la 
tabla de hash. Entre más se acerque esta proporción a 1.0, mayor será la probabilidad de colisiones.

Tip de rendimiento 19.7

El factor de carga en una tabla de hash es un clásico ejemplo de una concesión entre espacio de memoria y tiempo 
de ejecución: al incrementar el factor de carga, obtenemos un mejor uso de la memoria, pero el programa se ejecuta 
con más lentitud, debido al incremento en las colisiones de hashing. Al reducir el factor de carga, obtenemos más 
velocidad en la ejecución del programa, debido a la reducción en las colisiones de hashing, pero obtenemos un uso 
más pobre de la memoria, debido a que una proporción más grande de la tabla de hash permanece vacía.

Las tablas de hash son complejas de programar. Los estudiantes de ciencias computacionales estudian los 

esquemas de hashing en cursos titulados “Estructuras de datos” y “Algoritmos”. Java proporciona las clases 

Hash-

table

 y 

HashMap

 para permitir a los programadores utilizar la técnica de hashing sin tener que implementar 

los mecanismos de las tablas de hash. Este concepto es muy importante en nuestro estudio de la programación 
orientada a objetos. Como vimos en capítulos anteriores, las clases encapsulan y ocultan la complejidad (es decir, 
los detalles de implementación) y ofrecen interfaces amigables para el usuario. La fabricación apropiada de clases 
para exhibir tal comportamiento es una de las habilidades más valiosas en el campo de la programación orientada 
a objetos. En la fi gura 19.20 se utiliza un objeto 

HashMap

 para contar el número de ocurrencias de cada palabra 

en una cadena.

En la línea 17 se crea un objeto 

HashMap

 vacío con una capacidad inicial predeterminada (16 elementos) y 

un factor de carga predeterminado (0.75); estos valores predeterminados están integrados en la implementación 
de

HashMap

. Cuando el número de posiciones ocupadas en el objeto 

HashMap

 se vuelve mayor que la capacidad 

multiplicada por el factor de carga, la capacidad se duplica en forma automática. Observe que 

HashMap

 es una 

clase genérica que recibe dos argumentos de tipo. El primero especifi ca el tipo de clave (es decir, 

String

) y el 

segundo el tipo de valor (es decir, 

Integer

). Recuerde que los argumentos de tipo que se pasan a una clase gené-

 1 

// Fig. 19.20: ConteoTipoPalabras.java

2

// Programa que cuenta el número de ocurrencias de cada palabra en una cadena

3

import

 java.util.StringTokenizer;

 4 

import

 java.util.Map;

 5 

import

 java.util.HashMap;

 6 

import

 java.util.Set;

 7 

import

 java.util.TreeSet;

 8 

import

 java.util.Scanner;

 9 
 10 

public class

 ConteoTipoPalabras

 11 

{

 12  

private

 Map< String, Integer > mapa;

Figura 19.20

  |  Objetos 

Hashmap

 y 

Map

. (Parte 1 de 3).

19.10 Mapas 

827

19_MAQ_CAP_19_DEITEL.indd827

4/19/081:31:34AM