Las tablas hash proporcionan una forma útil de optimizar el rendimiento de las aplicaciones.
Las tablas hash no son un concepto nuevo en el campo de la informática. Fueron diseñados para acelerar el procesamiento informático, que es muy lento según los estándares actuales, y le permiten encontrar rápidamente una entrada particular al consultar muchas entradas de datos. Aunque las máquinas modernas son miles de veces más rápidas, las tablas hash siguen siendo una herramienta útil para obtener el mejor rendimiento de sus aplicaciones.
Imagine que tiene un archivo de datos que contiene alrededor de mil registros (por ejemplo, registros de clientes de una pequeña empresa) y un programa que lee los registros en la memoria para procesarlos. Cada registro contiene un número de identificación de cliente único de cinco dígitos, nombre del cliente, dirección, saldo de cuenta, etc. Supongamos que los registros no están ordenados por número de identificación de cliente. Por lo tanto, si el programa desea utilizar el número de cliente como "clave" para encontrar un registro de cliente en particular, la única forma de encontrarlo es buscar cada registro consecutivamente. A veces, encontrará el registro que necesita rápidamente, pero a veces, antes de que el programa encuentre el registro que necesita, casi ha buscado el último registro. Si desea buscar entre 1000 registros, encontrar cualquier registro requiere que el programa verifique un promedio de 500,5 ((1000 + 1)/2) registros. Si necesita buscar datos con frecuencia, es posible que necesite una forma más rápida de encontrar un registro.
Una forma de acelerar la búsqueda es dividir los registros en partes para que, en lugar de buscar en una lista grande, busque en varias listas cortas. Para nuestros números de identificación de cliente numéricos, puede crear 10 listas: una lista para números de identificación que comienzan con 0, una lista para números de identificación que comienzan con 1, y así sucesivamente. Entonces, para encontrar el número de identificación de cliente 38016, solo necesita buscar en la lista que comienza con 3. Si hay 1000 registros y la longitud promedio de cada lista es 100 (1000 registros divididos en 10 listas), entonces el número promedio de comparaciones para buscar un registro cae a aproximadamente 50 (consulte la Figura 1).
Por supuesto, si aproximadamente uno de cada diez clientes comienza con un 0, otro décimo comienza con un 1, y así sucesivamente, entonces este enfoque funcionaría bien. Si el 90% de los números de clientes comenzaran con 0, entonces esa lista tendría 900 registros, lo que requeriría un promedio de 450 comparaciones por búsqueda. Además, el 90% de las búsquedas que debe realizar el programa son de números que empiezan por 0. Por lo tanto, el número de comparación promedio está mucho más allá del alcance de operaciones matemáticas simples.
Sería mejor si pudiéramos distribuir los registros en nuestras listas de tal manera que cada lista tenga aproximadamente las mismas entradas, independientemente de la distribución de números en los valores clave. Necesitamos una manera de combinar el número de clientes y distribuir mejor los resultados. Por ejemplo, podríamos tomar cada dígito del número, multiplicarlo por algún número grande (que varía dependiendo de la posición del dígito), sumar los resultados para producir un total, dividir este número por 10 y dar el resto como índice. valor (índice). Cuando se lee un registro, el programa ejecuta esta función hash en el número de cliente para determinar a qué lista pertenece el registro. Cuando el usuario necesita realizar una consulta, la misma función hash se utiliza como "clave" para el número de cliente, de modo que se pueda buscar en la lista correcta. Una estructura de datos como esta se llama tabla hash.
Tablas hash en Java
Java contiene dos clases, java.util.Hashtable y java.util.HashMap , que proporcionan un mecanismo de tabla hash multipropósito. Las dos clases son muy similares y generalmente proporcionan la misma interfaz pública. Pero tienen algunas diferencias importantes, de las que hablaré más adelante.
Los objetos Hashtable y HashMap le permiten combinar una clave y un valor e ingresar el par clave/valor en la tabla usando el método put (). Luego puede obtener el valor llamando al método get() y pasando la clave como parámetro. La clave y el valor pueden ser cualquier objeto siempre que cumplan dos requisitos básicos. Tenga en cuenta que debido a que las claves y los valores deben ser objetos, los tipos primitivos deben convertirse en objetos utilizando métodos como Integer (int).
Para utilizar un objeto de una clase específica como clave, la clase debe proporcionar dos métodos, equals() y hashCode(). Estos dos métodos están en java.lang.Object , por lo que todas las clases pueden heredar estos dos métodos; sin embargo, la implementación de estos dos métodos en la clase Object generalmente es inútil, por lo que generalmente necesita sobrecargar estos dos métodos usted mismo.
El método Equals () compara su objeto con otro objeto y devuelve verdadero si los dos objetos representan la misma información. Este método también busca asegurarse de que ambos objetos pertenezcan a la misma clase. Object.equals() devuelve verdadero si los dos objetos de referencia son objetos idénticos, lo que explica por qué este método generalmente no encaja bien. En la mayoría de los casos, necesita una forma de comparar campo por campo, por lo que consideramos que diferentes objetos que representan los mismos datos son iguales.
El método HashCode() genera un valor int realizando una función hash utilizando el contenido del objeto. Hashtable y HashMap usan este valor para determinar en qué depósito (o lista) se encuentra un par clave/valor.
Como ejemplo, podemos mirar la clase String, ya que tiene sus propios métodos que implementan estos dos métodos. String.equals() compara dos objetos String carácter por carácter y devuelve verdadero si las cadenas son iguales:
Copie el código de código de la siguiente manera:
Cadena miNombre = "Einstein";
// La siguiente prueba es
// siempre es cierto
si ( miNombre.equals("Einstein") )
{...
String.hashCode() ejecuta una función hash en una cadena. El código numérico de cada carácter de la cadena se multiplica por 31 y el resultado depende de la posición del carácter en la cadena. Luego se suman los resultados de estos cálculos para obtener un total. Este proceso puede parecer complicado, pero garantiza una mejor distribución de los valores. También demuestra hasta dónde puede llegar al desarrollar su propio método hashCode(), con la confianza de que el resultado es único.
Por ejemplo, supongamos que quiero usar una tabla hash para implementar un catálogo de libros y usar el número ISBN del libro como clave de búsqueda para buscar. Puedo usar la clase String para llevar los detalles y tener listos los métodos equals() y hashCode() (ver Listado 1). Podemos agregar pares clave/valor a la tabla hash usando el método put () (ver Listado 2).
El método Put () acepta dos parámetros, ambos de tipo Objeto. El primer parámetro es clave; el segundo parámetro es valor. El método Put () llama al método hashCode() de la clave y divide el resultado por el número de listas en la tabla. Utilice el resto como valor de índice para determinar a qué lista se agrega el registro. Tenga en cuenta que la clave es única en la tabla; si llama a put () con una clave existente, la entrada coincidente se modifica para que haga referencia a un nuevo valor y se devuelve el valor anterior (cuando la clave no existe en la tabla); , put () devuelve un valor nulo).
Para leer un valor de la tabla, usamos la clave de búsqueda con el método get(). Devuelve una referencia de Objeto convertida al tipo correcto:
Copie el código de código de la siguiente manera:
LibroRegistro br =
(BookRecord)isbnTable.get(
"0-345-40946-9");
System.out.println(
"Autor: " + br.autor
+ " Título: " + br.título);
Otro método útil es remove(), que se usa casi igual que get(). Elimina la entrada de la tabla y la devuelve al programa que realiza la llamada.
tu propia clase
Si desea utilizar un tipo primitivo como clave, debe crear un objeto del mismo tipo. Por ejemplo, si desea utilizar una clave de número entero, debe utilizar el constructor Integer(int) para generar un objeto a partir de un número entero. Todas las clases contenedoras, como Integer, Float y Boolean, tratan los valores primitivos como objetos y sobrecargan los métodos equals() y hashCode(), por lo que pueden usarse como claves. Muchas otras clases proporcionadas en el JDK son así (incluso las clases Hashtable y HashMap implementan sus propios métodos equals() y hashCode()), pero debes consultar la documentación antes de usar objetos de cualquier clase como claves de tabla hash. También es necesario verificar el código fuente de la clase para ver cómo se implementan equals() y hashCode(). Por ejemplo, Byte, Carácter, Corto y Entero devuelven el valor entero representado como un código hash. Esto puede satisfacer o no sus necesidades.
Usando tablas hash en Java
Si desea crear una tabla hash que utilice objetos de una clase que usted define como claves, entonces debe asegurarse de que los métodos equals() y hashCode() de esa clase proporcionen valores útiles. Primero mire la clase que amplía para determinar si su implementación satisface sus necesidades. Si no, deberías sobrecargar el método.
La restricción de diseño básica de cualquier método equals() es que debe devolver verdadero si el objeto que se le pasa pertenece a la misma clase y sus campos de datos están configurados en valores que representan los mismos datos. También debes asegurarte de que si pasas un argumento vacío al método, tu código devuelve
Copie el código de código de la siguiente manera:
falso: booleano público es igual (Objeto o)
{
si ((o == nulo)
|| !(o instancia de miClase))
{
devolver falso;
}
// Ahora compara los campos de datos...
Además, existen algunas reglas que debes tener en cuenta al diseñar un método hashCode(). Primero, el método debe devolver el mismo valor para un objeto en particular, independientemente de cuántas veces se llame al método (por supuesto, siempre que el contenido del objeto no cambie entre llamadas. Cuando se utiliza un objeto como clave de tabla hash, esto debería evitarse). En segundo lugar, si dos objetos definidos por su método equals() son iguales, también deben generar el mismo código hash. En tercer lugar, y esto es más una guía que un principio, debe intentar diseñar su método de modo que produzca resultados diferentes para diferentes contenidos de objetos. No importa si ocasionalmente diferentes objetos generan el mismo código hash. Sin embargo, si el método solo puede devolver valores en el rango de 1 a 10, entonces solo se pueden usar 10 listas, independientemente de cuántas listas haya en la tabla hash.
Otro factor a tener en cuenta al diseñar equals() y hashCode() es el rendimiento. Cada llamada a put () o get() implica llamar a hashCode() para encontrar la lista correcta. Cuando get() escanea la lista para encontrar la clave, llama a equals() para cada elemento de la lista. Implemente estos métodos para que se ejecuten lo más rápido y eficientemente posible, especialmente si planea hacer que su clase esté disponible públicamente, porque es posible que otros usuarios quieran usar su clase en una aplicación de alto rendimiento donde la velocidad de ejecución es importante.
Rendimiento de la tabla hash
El principal factor que afecta la eficiencia de la tabla hash es la longitud promedio de las listas en la tabla, porque el tiempo promedio de búsqueda está directamente relacionado con esta longitud promedio. Obviamente, para reducir la longitud promedio, debe aumentar la cantidad de listas en la tabla hash; obtendrá la mejor eficiencia de búsqueda si la cantidad de listas es tan grande que la mayoría o todas las listas contienen solo un registro; Sin embargo, esto puede ser ir demasiado lejos. Si su tabla hash tiene muchas más listas que entradas de datos, entonces no es necesario que incurra en ese costo de memoria y, en algunos casos, es imposible que las personas acepten este enfoque.
En nuestro ejemplo anterior, sabíamos de antemano cuántos registros teníamos, 1000. Sabiendo esto, podemos decidir cuántas listas debe contener nuestra tabla hash para lograr el mejor compromiso entre la velocidad de búsqueda y la eficiencia del uso de la memoria. Sin embargo, en muchos casos, no se sabe de antemano cuántos registros procesará; el archivo del que se leen los datos puede crecer continuamente o el número de registros puede cambiar significativamente de un día para otro.
Las clases Hashtable y HashMap manejan este problema extendiendo dinámicamente la tabla a medida que se agregan entradas. Ambas clases tienen constructores que aceptan el número inicial de listas en la tabla y un factor de carga como parámetro:
tabla hash pública (
int capacidad inicial,
factor de carga flotante)
HashMap público (
int capacidad inicial,
factor de carga flotante)
Multiplique estos dos números para calcular un valor crítico. Cada vez que se agrega una nueva entrada a la tabla hash, el recuento se actualiza y cuando el recuento excede un valor crítico, la tabla se restablece (refrito). (El tamaño de la lista aumenta al doble del tamaño anterior más 1, y todas las entradas se mueven a la lista correcta). El constructor predeterminado establece la capacidad inicial en 11 y el factor de carga en 0,75, por lo que el valor crítico es 8. Cuando se agrega el noveno registro a la tabla, la tabla hash se reescala para que tenga 23 listas y el nuevo valor crítico será 17 (la parte entera de 23*0,75). Puede ver que el factor de carga es un límite superior en el número promedio de listas en una tabla hash, lo que significa que, de forma predeterminada, una tabla hash rara vez tiene muchas listas que contienen más de un registro. Compare nuestro ejemplo original, donde teníamos 1000 registros distribuidos en 10 listas. Si utilizamos los valores predeterminados, esta tabla se expandirá para contener más de 1500 listas. Pero puedes controlar esto. Si el número de listas multiplicado por el factor de carga es mayor que el número de entradas que estás procesando, la tabla nunca se rehará, por lo que podemos seguir el siguiente ejemplo:
Copie el código de código de la siguiente manera:
// La tabla no se repetirá hasta que
// tiene 1100 entradas (10*110):
Tabla Hash miHashTable =
nueva tabla hash (10, 110.0F);
Probablemente no desee hacer esto a menos que no desee ahorrar memoria para listas vacías y no le importe el tiempo de búsqueda adicional, lo que puede ser el caso en sistemas integrados. Sin embargo, este enfoque puede ser útil porque el restablecimiento es computacionalmente costoso y garantiza que el restablecimiento nunca se produzca.
Tenga en cuenta que aunque llamar a put () puede hacer que la tabla crezca (aumentar el número de listas), llamar a remove() no tendrá el efecto contrario. Por lo tanto, si tiene una tabla grande y elimina la mayoría de las entradas, terminará con una tabla grande pero en su mayoría vacía.
Hashtable y HashMap
Hay tres diferencias importantes entre las clases Hashtable y HashMap. La primera diferencia se debe principalmente a razones históricas. Hashtable se basa en la antigua clase Diccionario y HashMap es una implementación de la interfaz Map introducida en Java 1.2.
Quizás la diferencia más importante es que los métodos de Hashtable son sincrónicos, mientras que los métodos de HashMap no lo son. Esto significa que, aunque puedes usar un Hashtable en una aplicación multiproceso sin realizar ninguna acción especial, de manera similar debes proporcionar sincronización externa para un HashMap. Un método conveniente es utilizar el método estático sincronizadoMap() de la clase Colecciones, que crea un objeto Map seguro para subprocesos y lo devuelve como un objeto encapsulado. Los métodos de este objeto le permiten acceder al HashMap subyacente de forma sincrónica. El resultado de esto es que no puede interrumpir la sincronización en Hashtable cuando no la necesita (como en una aplicación de un solo subproceso), y la sincronización agrega mucha sobrecarga de procesamiento.
La tercera diferencia es que solo HashMap le permite usar valores nulos como clave o valor de una entrada de tabla. Solo un registro en un HashMap puede ser una clave vacía, pero cualquier cantidad de entradas puede ser un valor vacío. Esto significa que si la clave de búsqueda no se encuentra en la tabla, o si se encuentra la clave de búsqueda pero es un valor nulo, get() devolverá nulo. Si es necesario, utilice el método contieneKey() para distinguir entre las dos situaciones.
Alguna información sugiere que cuando se requiera sincronización, use Hashtable; de lo contrario, use HashMap. Sin embargo, debido a que HashMap se puede sincronizar cuando sea necesario, HashMap tiene más funciones que Hashtable y no se basa en una clase antigua, algunas personas piensan que se prefiere HashMap a Hashtable en diversas situaciones.
Acerca de las propiedades
A veces, es posible que desee utilizar una tabla hash para asignar cadenas de claves a cadenas de valores. Hay algunos ejemplos de cadenas de entorno en DOS, Windows y Unix. Por ejemplo, la cadena de clave PATH se asigna a la cadena de valor C:/WINDOWS;C:/WINDOWS/SYSTEM. Las tablas hash son una forma sencilla de representarlos, pero Java proporciona otra forma.
La clase Java .util.Properties es una subclase de Hashtable diseñada para usarse con claves y valores de cadena. El uso del objeto Propiedades es similar al uso de Hashtable, pero la clase agrega dos métodos para ahorrar tiempo que usted debe conocer.
El método Store() guarda el contenido de un objeto Propiedades en un archivo en un formato legible. El método Load() es todo lo contrario, se utiliza para leer el archivo y configurar el objeto Propiedades para que contenga claves y valores.
Tenga en cuenta que debido a que Propiedades extiende Hashtable, puede usar el método put () de la superclase para agregar claves y valores que no son objetos String. Esto no es aconsejable. Además, si usa store() con un objeto Properties que no contiene un objeto String, store() fallará. Como alternativa a put () y get(), debes usar setProperty() y getProperty(), que toman parámetros String.
Bien, espero que ahora sepas cómo usar tablas hash para acelerar tu procesamiento.