Tabla Hash en Java – Part 1

La clase Hashtable implementa una tabla hash, que asigna claves a valores. Cualquier objeto no nulo se puede utilizar como clave o como valor. Para almacenar y recuperar con éxito objetos de una tabla hash, los objetos utilizados como claves deben implementar el método hashCode y el método equals.  

Características de la tabla hash

• Es similar a HashMap, pero está sincronizado.
• Hashtable almacena el par clave/valor en la tabla hash.
• En Hashtable especificamos un objeto que se usa como clave y el valor que queremos asociar a esa clave. A continuación, se aplica un hash a la clave y el código hash resultante se utiliza como índice en el que se almacena el valor dentro de la tabla.
• La capacidad predeterminada inicial de la clase Hashtable es 11, mientras que loadFactor es 0,75.
• HashMap no proporciona ninguna enumeración, mientras que Hashtable no proporciona una enumeración rápida.

Declaración:

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

Parámetros de tipo:

• K : el tipo de claves que mantiene este mapa
• V – el tipo de valores mapeados

La jerarquía de Hashtable

Hashtable implementa las interfaces Serializable , Cloneable , Map<K,V> y amplía Dictionary<K,V> . Las subclases directas son Propiedades , UIDefaults .
 

Constructores:

Para crear una tabla Hash, debemos importarla desde java.util.Hashtable . Hay varias formas en las que podemos crear un Hashtable.

1. Hashtable(): Esto crea una tabla hash vacía con el factor de carga predeterminado de 0,75 y una capacidad inicial de 11. 

Hashtable<K, V> ht = new Hashtable<K, V>();

// Java program to demonstrate
// adding elements to Hashtable
  
import java.io.*;
import java.util.*;
  
class AddElementsToHashtable {
    public static void main(String args[])
    {
        // No need to mention the
        // Generic type twice
        Hashtable<Integer, String> ht1 = new Hashtable<>();
  
        // Initialization of a Hashtable
        // using Generics
        Hashtable<Integer, String> ht2
            = new Hashtable<Integer, String>();
  
        // Inserting the Elements
        // using put() method
        ht1.put(1, "one");
        ht1.put(2, "two");
        ht1.put(3, "three");
  
        ht2.put(4, "four");
        ht2.put(5, "five");
        ht2.put(6, "six");
  
        // Print mappings to the console
        System.out.println("Mappings of ht1 : " + ht1);
        System.out.println("Mappings of ht2 : " + ht2);
    }
}

Mappings of ht1 : {3=three, 2=two, 1=one}
Mappings of ht2 : {6=six, 5=five, 4=four}

2. Hashtable(int initialCapacity): esto crea una tabla hash que tiene un tamaño inicial especificado por initialCapacity y el factor de carga predeterminado es 0,75.

Hashtable<K, V> ht = new Hashtable<K, V>(int initialCapacity);

// Java program to demonstrate
// adding elements to Hashtable
  
import java.io.*;
import java.util.*;
  
class AddElementsToHashtable {
    public static void main(String args[])
    {
        // No need to mention the
        // Generic type twice
        Hashtable<Integer, String> ht1 = new Hashtable<>(4);
  
        // Initialization of a Hashtable
        // using Generics
        Hashtable<Integer, String> ht2
            = new Hashtable<Integer, String>(2);
  
        // Inserting the Elements
        // using put() method
        ht1.put(1, "one");
        ht1.put(2, "two");
        ht1.put(3, "three");
  
        ht2.put(4, "four");
        ht2.put(5, "five");
        ht2.put(6, "six");
  
        // Print mappings to the console
        System.out.println("Mappings of ht1 : " + ht1);
        System.out.println("Mappings of ht2 : " + ht2);
    }
}

Mappings of ht1 : {3=three, 2=two, 1=one}
Mappings of ht2 : {4=four, 6=six, 5=five}

3. Hashtable(int size, float fillRatio): esta versión crea una tabla hash que tiene un tamaño inicial especificado por el tamaño y la proporción de relleno especificada por fillRatio. proporción de relleno: Básicamente, determina qué tan completa puede estar una tabla hash antes de que se redimensione hacia arriba y su valor se encuentre entre 0.0 y 1.0.

Hashtable<K, V> ht = new Hashtable<K, V>(int size, float fillRatio);

// Java program to demonstrate
// adding elements to Hashtable
  
import java.io.*;
import java.util.*;
  
class AddElementsToHashtable {
    public static void main(String args[])
    {
        // No need to mention the
        // Generic type twice
        Hashtable<Integer, String> ht1
            = new Hashtable<>(4, 0.75f);
  
        // Initialization of a Hashtable
        // using Generics
        Hashtable<Integer, String> ht2
            = new Hashtable<Integer, String>(3, 0.5f);
  
        // Inserting the Elements
        // using put() method
        ht1.put(1, "one");
        ht1.put(2, "two");
        ht1.put(3, "three");
  
        ht2.put(4, "four");
        ht2.put(5, "five");
        ht2.put(6, "six");
  
        // Print mappings to the console
        System.out.println("Mappings of ht1 : " + ht1);
        System.out.println("Mappings of ht2 : " + ht2);
    }
}

Mappings of ht1 : {3=three, 2=two, 1=one}
Mappings of ht2 : {6=six, 5=five, 4=four}

4. Hashtable(Map<? extends K,? extends V> m): Esto crea una tabla hash que se inicializa con los elementos en m.

Hashtable<K, V> ht = new Hashtable<K, V>(Mapa m);

// Java program to demonstrate
// adding elements to Hashtable
  
import java.io.*;
import java.util.*;
  
class AddElementsToHashtable {
    public static void main(String args[])
    {
        // No need to mention the
        // Generic type twice
        Map<Integer, String> hm = new HashMap<>();
  
        // Inserting the Elements
        // using put() method
        hm.put(1, "one");
        hm.put(2, "two");
        hm.put(3, "three");
  
        // Initialization of a Hashtable
        // using Generics
        Hashtable<Integer, String> ht2
            = new Hashtable<Integer, String>(hm);
  
        // Print mappings to the console
  
        System.out.println("Mappings of ht2 : " + ht2);
    }
}

Mappings of ht2 : {3=three, 2=two, 1=one}

Ejemplo:

// Java program to illustrate
// Java.util.Hashtable
  
import java.util.*;
  
public class GFG {
    public static void main(String[] args)
    {
        // Create an empty Hashtable
        Hashtable<String, Integer> ht = new Hashtable<>();
  
        // Add elements to the hashtable
        ht.put("vishal", 10);
        ht.put("sachin", 30);
        ht.put("vaibhav", 20);
  
        // Print size and content
        System.out.println("Size of map is:- " + ht.size());
        System.out.println(ht);
  
        // Check if a key is present and if
        // present, print value
        if (ht.containsKey("vishal")) {
            Integer a = ht.get("vishal");
            System.out.println("value for key"
                               + " \"vishal\" is:- " + a);
        }
    }
}

Size of map is:- 3
{vaibhav=20, vishal=10, sachin=30}
value for key "vishal" is:- 10

Realización de varias operaciones en Hashtable                  

1. Agregar elementos: para agregar un elemento a la tabla hash, podemos usar el método put() . Sin embargo, el orden de inserción no se conserva en la tabla hash. Internamente, para cada elemento, se genera un hash separado y los elementos se indexan en función de este hash para que sea más eficiente.                      

// Java program to demonstrate
// adding elements to Hashtable
  
import java.io.*;
import java.util.*;
  
class AddElementsToHashtable {
    public static void main(String args[])
    {
        // No need to mention the
        // Generic type twice
        Hashtable<Integer, String> ht1 = new Hashtable<>();
  
        // Initialization of a Hashtable
        // using Generics
        Hashtable<Integer, String> ht2
            = new Hashtable<Integer, String>();
  
        // Inserting the Elements
          // using put() method
        ht1.put(1, "Geeks");
        ht1.put(2, "For");
        ht1.put(3, "Geeks");
  
        ht2.put(1, "Geeks");
        ht2.put(2, "For");
        ht2.put(3, "Geeks");
          
          // Print mappings to the console
        System.out.println("Mappings of ht1 : " + ht1);
        System.out.println("Mappings of ht2 : " + ht2);
    }
}

Mappings of ht1 : {3=Geeks, 2=For, 1=Geeks}
Mappings of ht2 : {3=Geeks, 2=For, 1=Geeks}

2. Cambio de elementos: después de agregar los elementos, si deseamos cambiar el elemento, se puede hacer agregando nuevamente el elemento con el método put() . Dado que los elementos en la tabla hash están indexados usando las claves, el valor de la clave se puede cambiar simplemente insertando el valor actualizado de la clave que deseamos cambiar.

// Java program to demonstrate
// updating Hashtable
  
import java.io.*;
import java.util.*;
class UpdatesOnHashtable {
    public static void main(String args[])
    {
  
        // Initialization of a Hashtable
        Hashtable<Integer, String> ht
            = new Hashtable<Integer, String>();
  
        // Inserting the Elements
          // using put method
        ht.put(1, "Geeks");
        ht.put(2, "Geeks");
        ht.put(3, "Geeks");
          
          // print initial map to the console
        System.out.println("Initial Map " + ht);
          
          // Update the value at key 2
        ht.put(2, "For");
          
          // print the updated map
        System.out.println("Updated Map " + ht);
    }
}

Initial Map {3=Geeks, 2=Geeks, 1=Geeks}
Updated Map {3=Geeks, 2=For, 1=Geeks}

3. Eliminar Elemento: Para eliminar un elemento del Mapa, podemos usar el método remove() . Este método toma el valor de la clave y elimina la asignación de una clave de este mapa si está presente en el mapa.

// Java program to demonstrate
// the removing mappings from Hashtable
  
import java.io.*;
import java.util.*;
class RemovingMappingsFromHashtable {
  
    public static void main(String args[])
    {
        // Initialization of a Hashtable
        Map<Integer, String> ht
            = new Hashtable<Integer, String>();
  
        // Inserting the Elements
          // using put method
        ht.put(1, "Geeks");
        ht.put(2, "For");
        ht.put(3, "Geeks");
        ht.put(4, "For");
  
        // Initial HashMap
        System.out.println("Initial map : " + ht);
  
          // Remove the map entry with key 4
        ht.remove(4);
  
        // Final Hashtable
        System.out.println("Updated map : " + ht);
    }
}

Initial map : {4=For, 3=Geeks, 2=For, 1=Geeks}
Updated map : {3=Geeks, 2=For, 1=Geeks}

4. Recorrido de una tabla hash: para iterar la tabla, podemos hacer uso de un bucle for avanzado . A continuación se muestra el ejemplo de iteración de una tabla hash.

// Java program to illustrate
// traversal of Hashtable
  
import java.util.Hashtable;
import java.util.Map;
  
public class IteratingHashtable {
    public static void main(String[] args)
    {
          // Create an instance of Hashtable
        Hashtable<String, Integer> ht = new Hashtable<>();
  
          // Adding elements using put method
        ht.put("vishal", 10);
        ht.put("sachin", 30);
        ht.put("vaibhav", 20);
      
          // Iterating using enhanced for loop
        for (Map.Entry<String, Integer> e : ht.entrySet())
            System.out.println(e.getKey() + " "
                               + e.getValue());
    }
}

vaibhav 20
vishal 10
sachin 30

 Funcionamiento interno de Hashtable

La estructura de datos de la tabla hash es una array de cubos que almacena los pares clave/valor en ellos. Hace uso del método hashCode() para determinar qué cubo debe mapear el par clave/valor.
La función hash ayuda a determinar la ubicación de una clave dada en la lista de deseos. Generalmente, el código hash es un número entero no negativo que es igual para objetos iguales y puede o no ser igual para objetos desiguales. Para determinar si dos objetos son iguales o no, hashtable utiliza el método equals().

Es posible que dos Objetos desiguales tengan el mismo código hash. Esto se llama colisión . Para resolver colisiones, hashtable usa una array de listas. Los pares asignados a un solo cubo (índice de array) se almacenan en una lista y la referencia de la lista se almacena en el índice de array.

Métodos de tabla hash

• K – El tipo de claves en el mapa.
• V – El tipo de valores mapeados en el mapa.

Métodos declarados en la interfaz java.util.Map

Debe leer:

• Diferencias entre HashMap y HashTable en Java

Referencia: https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Hashtable.html