¿Cómo funciona internamente HashTable en Java?

Hashtable es una especie de mapa Hash pero está sincronizado. El mapa hash no está sincronizado, permite una clave nula y múltiples valores nulos, no es seguro para subprocesos, es decir, no puede compartirse entre muchos subprocesos sin una sincronización adecuada, los pares clave/valores se almacenan en Hashtable. La tabla Hash no permite valores/claves nulos. Al usar esto, especifica un objeto que se usa como clave y el valor que desea asociar con la clave. Es una array de un índice. Cada índice se conoce como cubo/ranura. Restringe los valores en función de las claves y el lugar del cubo reconocido llamando al método Hash code(). La tabla Hash de Java contiene una clase que tiene elementos únicos.

Trabajo de Hashtable

La tabla hash contiene intrínsecamente una ranura/cubo en el que se almacena el par de clave y valor. Utiliza el código hash de la clave para descubrir qué cubo debe mapear la clave/valor de un conjunto. Para encontrar un elemento en una lista, haga el primer enfoque, es decir, la búsqueda lineal implica verificar cada elemento, llevará más tiempo. Suponga que ha recuperado un valor y su número de índice de una array, luego buscará un valor muy rápidamente. De hecho, tomará menos tiempo si sabe que el número de índice es independiente del tamaño y la posición de la array. Pero, ¿cómo sabe qué elemento de la array contiene el valor que está buscando? La respuesta es al calcular el valor en sí mismo, el número de índice está algo relacionado con los datos.

Proliferemos la array, tomemos un nombre y encontremos su código ASCII, por ejemplo, tomaremos un nombre, digamos Mia, busquemos el código ASCII para cada letra, agreguemos el código ASCII y dividamos el número ASCII combinado con el tamaño de un elemento en este. es 5, tomaremos un recordatorio del elemento que es 4 y allí pondremos el nombre Mia, es decir, en 4th Slot/ Bucket.

Ejemplo:

 Nombre = Mía 

 M 77

 yo 105 

un 97

Suma = 279 

Módulo = 279 % 5 = 4

                           

Y ahora podemos agregar más nombres al Cubo como se muestra a continuación:

Mia ⇾ M (77) + i(105) + a(97) = 279 % 5 = 4

Tim ⇾ T (84) + i(105) + m(77) = 298 % 5 = 3

Leo ⇾ L(76) + e(101) + n(110) = 287 % 5 = 2

Suma ⇾ S(83) + o(111) + m(77) = 271 % 5 = 1      

Beb ⇾ B(66) + e(101) + b(98) = 265 % 5 0

Número de índice = suma de códigos ASCII % Tamaño de array

Recuperemos un elemento, digamos Ada, realizamos el mismo cálculo,

     Encuentra ASCII para Ada = (65+100+97) = 262

                      262 % 11 = 9

                    MisDatos = Array (9)

Esta es una búsqueda de array rápida. En lugar de almacenar elementos individuales o tablas hash de datos, se utilizan para almacenar los pares clave-valor. Por ejemplo, Ada sería la clave para la que desea calcular el índice y la fecha de nacimiento del valor correspondiente, por esta razón, una tabla hash de par clave-valor a veces se denomina mapa hash, de hecho, si un enfoque orientado a objetos se toma a cada persona en una instancia de una clase y la clave sería de muchas propiedades, al completar una array con objetos, almacenará de manera efectiva muchos datos relacionados que desee para cada depósito

Un algoritmo hash también se conoce como función Hash. La función hash es una función que genera una tabla cuando se le da una clave. Esta es una función para obtener una ubicación de depósito a partir del código hash de Key. Cada vez que devuelve un dígito para un objeto. Cálculo aplicado a una llave para transformarla en una dirección.

Para claves numéricas, divida la clave por el número de direcciones disponibles, n, y tome el resto

 Dirección = clave Mod n

Para claves alfanuméricas, divida la suma de los códigos ASCII en una clave por el número de direcciones disponibles y tome el resto.

• El método de plegado divide la llave en partes iguales y luego suma las partes
• El número de teléfono 018767242947 se convierte en 01+87+67+24+29+47= 255
• Dependiendo del tamaño de una tabla, se puede dividir por alguna constante y tomar el resto.
• Hay muchas funciones Hash, algunas apropiadas para otras dependiendo de la naturaleza.

Colisiones en una tabla Hash

Hasta ahora ha visto, hay muchas tablas hash con datos que causan cualquier problema de manera muy conveniente, digamos que a veces no es realista si aplica una función hash en dos casos diferentes, genera el mismo número de índice para ambos pero ambos elementos pueden No vas en el mismo lugar esto se llama Colisión. Dos objetos idénticos siempre tienen los mismos dígitos, mientras que dos objetos desiguales no siempre tienen dígitos diferentes. Al colocar un objeto en la tabla hash, existe la posibilidad de que objetos diferentes puedan tener un código hash igual llamado Colisión. Para rectificar esta array de listas se utiliza una tabla hash. El conjunto asignado al índice de array/cubo único y se mantiene en un índice y la referencia de índice se almacena en el índice de array.

Carguemos la array nuevamente esta vez con un conjunto diferente de datos. Como se muestra a continuación, si Mia ocupa la posición 4 y Leo la posición 2 y si los otros nombres también tienen la misma entrada en la posición 2, automáticamente el siguiente cubo se llenará con esa entrada para evitar la colisión, como se muestra a continuación.

Encuentra Rae 280 Mod 11 = 5

misDatos = Array(5)

Como el recordatorio para un código ASCII de Rae es 5, pero se coloca en la ranura 8 porque, debido a la colisión, los 2 elementos se dan cuenta de que están en la misma ranura, pero para evitar esto, Rae se desplaza a otra ranura y la otra ranura vuelve a estar. ocupado por lo que se desplaza a la octava posición.

Resolver una colisión colocando el artículo en otro lugar luego de su dirección calculada se llama DIRECCIÓN ABIERTA porque cada ubicación está abierta para un artículo. Esto puede usar una variedad de técnicas para decidir dónde colocar un elemento. Esta técnica de direccionamiento en particular se llama SONDAJE LINEAL. Si la dirección calculada está ocupada, entonces la búsqueda lineal se usa para encontrar el siguiente cubo disponible. Si el sondeo lineal llega a su fin y todavía no puede encontrar una posición, podría recorrer el comienzo de la array y continuar buscando desde allí. Cuantos más elementos haya en una tabla hash, más posibilidades de colisión.

Factor de carga = Número total de elementos almacenados / Tamaño de la array

Otra forma de hacer con las colisiones se conoce como strings, a veces denominadas DIRECCIONAMIENTO CERRADO. En esto, la ranura puede formar una string agregando varios artículos en un cubo.

El objetivo de una función hash

• Minimice las colisiones
• Distribución uniforme de valores hash
• Fácil de calcular
• Resolver cualquier colisión

Métodos como hashCode() & equal() para encontrar coincidencias exactas de elementos

equal(): la clase de objeto define equal() como un lenguaje dado de Java. En el cual los objetos indican si pocos objetos pasan como argumento que es “igual a” la presente instancia. Los objetos diferentes o dos pueden ser similares solo si se colocan en una dirección de memoria igual.

Sintaxis: 

public boolean equals  (Object obj)

// This method checks if some other Object
// passed to it as an argument is equal to 
// the Object on which it is invoked.

Debe seguir los siguientes principios:

• Reflexivo: para un solo objeto, diga a , a.equal(a) devuelve verdadero.
• Simétrico: para dos objetos diferentes, a.equal(y) devuelve verdadero si y solo si y.equal(a) devuelve verdadero.
• Transitiva: para varios objetos a, b, c, si a.equal(b) devuelve verdadero y b.equals(c) devuelve verdadero, entonces a.equals(c) debería devolver verdadero.
• Si las propiedades del objeto son medios modificados utilizados en la implementación del método equal(), esto dará como resultado un resultado diferente y múltiplo de a.equal(b).
• La clase de objeto equal() devolverá verdadero solo cuando dos referencias marquen objetos similares.

Nota:

hashCode(): En este objeto devuelve una representación entera de la dirección de memoria de un objeto. Al usar este método, se devolverá un número entero aleatorio que es único para una instancia en particular. Esto devolverá datos de código hash entero o valor de ese objeto.  

Sintaxis :  

public int hashCode()

// This method returns the hash code value 
// for the object on which this method is invoked.

Ejemplo:

import java.util.*;
 
public class HashCodeExample {
    public static void main(String[] args)
    {
        // develop integer object
        Integer i = new Integer("144");
 
        // Returned hash code value
        int hashValue = i.hashCode();
 
        System.out.println("Value of Hashcode : "
                           + hashValue);
    }
}

Producción

144

Pasos

• Una clase base tiene atributos para objetos definidos por el usuario.
• Al usar @override, se puede predefinir la función override hashCode().
• De manera similar, la función override equal() se puede predefinir.
• Declare un objeto de la clase base y use el código hash y la función es igual para que los objetos sean iguales en la función principal.

Contrato de código hash() e igual()

• Durante la ejecución de la aplicación, si se invoca hashCode() más de una vez en el mismo objeto, debe devolver de forma constante el mismo valor entero, siempre que no se modifique la información utilizada en la comparación de iguales (objeto) en el objeto. No es necesario que este valor Integer permanezca igual de una ejecución de la aplicación a otra ejecución de la misma aplicación.
• Si dos objetos son iguales, de acuerdo con el método equals(Object) , entonces el método hashCode() debe producir el mismo Integer en cada uno de los dos Objetos.
• Si dos Objetos no son iguales, según el método equals(Object) , no es necesario que el valor Integer producido por el método hashCode() en cada uno de los dos Objetos sea distinto. Puede ser lo mismo, pero producir el entero distinto en cada uno de los dos objetos es mejor para mejorar el rendimiento de las colecciones basadas en hashing como HashMap , HashTable, etc.

Nota: Los objetos iguales deben producir el mismo código hash siempre que sean iguales, sin embargo, los objetos desiguales no necesitan producir códigos hash distintos.

Usos

Es una estructura de datos que ejecuta un tipo de datos trascendente de array asociativa, una estructura que puede asignar claves a valores. Aquí usamos el algoritmo hash para determinar una lista llamada código hash en una array de ranuras de las que se pueden obtener los valores deseados. La tabla hash se usa para implementar una tabla en memoria, en un lenguaje de programación como python, PHP, etc., en la verificación de errores. Una array asociativa, indexación de bases de datos, cachés, conjuntos, representación de objetos, representación de datos únicos, tabla de transposición, etc.

Ejemplo 1:

import java.util.*;
 
public class HashtableExample {
    public static void main(String[] args)
    {
        // Create Hashtable
        Hashtable<Integer, String> hashtable
            = new Hashtable<>();
 
        // Add mappings to hashtable
        hashtable.put(1, "X");
        hashtable.put(2, "Y");
        hashtable.put(3, "Z");
        System.out.println(hashtable);
 
        // Get a mapping by key
        String value = hashtable.get(1);
 
        System.out.println(value);
 
        //  Remove a mapping
        hashtable.remove(3);
 
        // Iterate overmapping
        Iterator<Integer> itr
            = hashtable.keySet().iterator();
 
        while(itr.hasNext())
        {
            Integer key = itr.next();
            String mapped_value = hashtable.get(key);
            System.out.println(
                "key: " + key + " value : " + mapped_value);
        }
    }
}

{3=Z, 2=Y, 1=X}
X
key: 2 value : Y
key: 1 value : X

Ejemplo 2:

import java.util.Hashtable;
import java.util.Enumeration;
public class HashtableExample {
 
    public static void main(String[] args)
    {
 
        Enumeration names;
        String key;
 
        // Developing a Hashtable
        Hashtable<String, String> hashtable
            = new Hashtable<String, String>();
 
        // Attaching Key and Value sets to Hashtable
        hashtable.put("Key1", "Madhu");
        hashtable.put("Key2", "Girja");
        hashtable.put("Key3", "Durgesh");
        hashtable.put("Key4", "Richa");
        hashtable.put("Key5", "Manisha");
 
        names = hashtable.keys();
        while (names.hasMoreElements()) {
            key = (String)names.nextElement();
            System.out.println("Key: " + key + " & Value: "
                               + hashtable.get(key));
        }
    }
}

Key: Key4 & Value: Richa
Key: Key3 & Value: Durgesh
Key: Key2 & Value: Girja
Key: Key1 & Value: Madhu
Key: Key5 & Value: Manisha

Conclusión

• Utilizado en el índice de grandes cantidades de datos
• Dirección de cada clave calculada usando la propia clave
• Colisiones resueltas con direccionamiento abierto o cerrado
• Hashing se usa ampliamente en la indexación de bases de datos, compiladores, almacenamiento en caché, autenticación de contraseñas y más
• La inserción, eliminación y recuperación ocurren en tiempo constante.