Tabla hash de Java

La clase Java Hashtable es uno de los miembros más antiguos de Java Collection Framework. Es una implementación de la estructura de datos de la tabla hash matemática. En Java, la tabla hash contiene depósitos internos donde se almacenan los pares clave/valor. Hashtable es bastante similar a HashMap . La diferencia más significativa entre ellos: Hashtable está sincronizado mientras que HashMap no lo está.

Hashtable como estructura de datos

Hashtable es una estructura de datos donde los datos se almacenan en un formato de matriz. Cada valor de datos tiene un valor de clave único. Si se conoce la clave, el acceso a los datos necesarios es muy rápido. Por lo tanto, las operaciones de inserción y búsqueda son rápidas independientemente del tamaño de los datos. Hash Table consiste en una matriz para guardar datos y hash para generar un índice donde se debe ubicar un elemento. ¿Qué es hash? Es una regla que mapea el Objeto en un conjunto de caracteres (código). Por lo general, ese tipo de función convierte una gran cantidad de datos en un pequeño valor entero. Las funciones hash pueden ser diferentes, pero todas presentan ciertas propiedades:

• Un objeto particular tiene el código hash particular.
• Dos objetos iguales tienen los mismos códigos hash. Lo opuesto no es verdad.
• Si dos códigos hash son diferentes, los objetos definitivamente no son iguales.
• Diferentes objetos pueden tener el mismo código hash. Este evento muy raro se llama colisión. La buena función hash minimiza la probabilidad de colisiones.

El resultado de aplicar la función Hash a un objeto llama a hashCode .

Tabla Hash en Java

La clase Hashtable es la implementación de una estructura de datos de tabla hash. Esta colección se creó antes que Java Collection Framework, pero luego se incluyó en ella. Como todas las colecciones "tempranas" (desde Java 1.0), una tabla hash está sincronizada (casi todos los métodos están marcados como sincronizados). Debido a este factor, la tabla hash tiene importantes problemas de rendimiento. Por lo tanto, a partir de Java 1.2, en la mayoría de los casos se recomienda utilizar otras implementaciones de la interfaz Map debido a su falta de sincronización. Por lo general , HashMap es el reemplazo más apropiado. Entonces clase Hashtable<K,V>consta de claves y valores. Almacena claves según el principio de hashing. Los pares clave-valor se almacenan en "cubos". Los cubos juntos construyen una "tabla", una especie de matriz interna. Hashtable usa el código hash de la clave para determinar un depósito en el que debe asignarse el par clave/valor. La función hash permite obtener la ubicación del depósito a partir del código hash de Key. Esta función devuelve un número entero para un objeto. Como dijimos anteriormente, dos objetos iguales tienen el mismo código hash, mientras que dos objetos desiguales pueden no tener siempre códigos hash diferentes. Diferentes objetos, colocados en una tabla hash pueden tener el mismo código hash. Para resolver este problema (colisión), se utiliza una matriz de listas en la tabla hash. Los pares asignados a un solo depósito se almacenan en una lista y esta referencia de lista se almacena en el índice de matriz.

Constructores Java de tabla hash

• Hashtable() , el constructor predeterminado. Crea una tabla hash vacía. (Capacidad inicial predeterminada = 11, factor de carga = 0,75).
• Hashtable(int size) construye una tabla hash del tamaño especificado.
• Hashtable(int size, float fillRatio) crea una tabla hash del tamaño y proporción de relleno especificados.
• Hashtable(Map m) crea una tabla hash con las mismas asignaciones que el Mapa dado.

Declaración de tabla hash

La clase Hashtable Java implementa interfaces Map , Cloneable y Serializable . Extiende la clase Diccionario .

Hashtable.java
public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable

K es el tipo de claves mantenidas por el mapa. V es el tipo de valores asignados. Ejemplo:

Hashtable<Student, Integer> myHTable = new Hashtable<>();

Cómo importar tablas hash java

Java Hashtable está dentro del paquete java.util . Así que usa import java.util.Hashtable; en tu código. Por lo general, obtendrá una pista de su IDE sobre esto.

Operaciones principales de la tabla hash

Las operaciones principales del Hashtable son obtener, insertar en la colección y eliminar de allí. Aquí estas tres operaciones son:

• Object get (clave de objeto) devuelve el valor del objeto que tiene la clave especificada. Devuelve nulo si no se encuentra dicha clave.
• Objeto puesto (clave de objeto, valor de objeto) asigna la clave especificada al valor especificado. Ni la clave ni el valor pueden ser nulos.
Eliminar objeto (clave de objeto) elimina la entrada (clave y valor correspondiente) de la tabla hash.

Las otras operaciones importantes:

• int size() devuelve la cantidad de entradas en la tabla hash.
• boolean contains(Object value) comprueba si el valor especificado está en la tabla hash. Si es así, el método devuelve verdadero, de lo contrario, devuelve falso.
• boolean containsValue(Object value) comprueba si el valor especificado está en la tabla hash. Si es así, el método devuelve verdadero, de lo contrario, devuelve falso.
• void clear() elimina todas las entradas de la tabla hash.
• boolean containsKey (clave de objeto) devuelve verdadero si la clave especificada existe en la tabla hash; de lo contrario, devuelve falso.
• boolean isEmpty() devuelve verdadero si la tabla hash está vacía o falso si contiene al menos una clave.
• void rehash() aumenta el tamaño de la tabla hash y repite todas sus claves.

Implementación de tabla hash, código Java:

Vamos a crear una clase de estudiante :

import java.util.Date;
public class Student {
   String surname;
   String name;
   String secondName;
   Long birthday; // Long instead of long is used by Gson/Jackson json parsers and various orm databases

   public Student(String surname, String name, String secondName, Date birthday ){
       this.surname = surname;
       this.name = name;
       this.secondName = secondName;
       this.birthday = birthday == null ? 0 : birthday.getTime();
   }

   @Override
   public int hashCode(){
       //TODO: check for nulls
       return (surname + name + secondName + birthday).hashCode();
   }
   @Override
   public boolean equals(Object other_) {
       Student other = (Student)other_;
       return (surname == null || surname.equals(other.surname) )
               && (name == null || name.equals(other.name))
               && (secondName == null || secondName.equals(other.secondName))
               && (birthday == null || birthday.equals(other.birthday));
   }
}

Aquí está el ejemplo de Java Hashtable . Pongamos dos Objetos de la clase Student en la tabla hash, luego eliminemos algunos y verifiquemos algunos parámetros.

public class HashTableExample {
   public static void main(String[] args) {
 
       Hashtable<Student, Integer> myHTable = new Hashtable<>();
       Student sarah1 = new Student("Sarah","Connor", "Jane", null);
       Student john = new Student("John","Connor", "Kyle", new Date(1985, 02-1, 28)); // date not exists
       myHTable.put(john,1);
       myHTable.put(sarah1,0);
       System.out.println(myHTable.get(john));
       System.out.println(myHTable.isEmpty());
       System.out.println(myHTable.size());
       System.out.println(myHTable.contains(1));
       myHTable.remove(john);
       System.out.println(myHTable.contains(0));
       System.out.println(myHTable.contains(1));
       System.out.println(myHTable.containsKey(sarah1));
   }
}

El resultado de ejecutar el programa es:

1
false
2
true
true
false
true

HashMap frente a tabla hash

• Hashtable es similar a HashMap en Java. La diferencia más significativa es que Hashtable está sincronizado mientras que HashMap no lo está. Por lo tanto, Hashtable es más lento que HashMap debido a la sincronización.
• Excepto por problemas de sincronización, Hashtable no permite que se use nulo como valor o clave. HashMap permite una clave nula y múltiples valores nulos.
• Hashtable hereda la clase Dictionary mientras que HashMap hereda la clase AbstractMap.
• HashMap es atravesado por Iterator. Hashtable puede ser atravesado no solo por Iterator sino también por Enumerator.

Ejemplo de tabla hash de Java (Hashtable vs HashMap clave nula)

Aquí hay un código de fragmento para demostrar un valor nulo utilizado como clave y valor en HashMap y Hashtable

// Null key Java hashtable example and hashmap example  

try{
      System.out.println("Hashtable");
      Hashtable hashTable = new Hashtable();
      hashTable.put(null, new Object());
    }catch(Exception ex){
      ex.printStackTrace();
    }
    System.out.println("HashMap");
    HashMap hashMap = new HashMap();
    hashMap.put(null, new Object());
    System.out.println("as you see no exceptions with null key in HashMap");
  }

El resultado de ejecutar el programa que contiene este fragmento:

java.lang.NullPointerException
	at java.base/java.util.Hashtable.put(Hashtable.java:480)
	at Character.main(Character.java:58)
HashMap
as you see no exceptions with null key in HashMap

Conclusión

Realmente no usará Hashtable a menudo en proyectos reales, pero es fácil cumplir con esta estructura de datos en proyectos antiguos. De todos modos, es importante comprender qué estructuras de datos tiene Java y cómo funcionan, al menos para sus entrevistas. Por lo general, se usan objetos HashMap en lugar de Hashtable debido a su similitud. HashMap es más efectivo (no está sincronizado) y podría tener nulo como clave.