Función de hash en Java - Aplicaciones de la función hash

Tabla de contenido:

Anonim

Introducción a la función de hash en Java

Como sabemos que Java es un lenguaje orientado a objetos, por lo tanto, debe haber un mecanismo para describir el estado de un objeto, sin importar cuán grande sea un objeto. Hashing Function en Java surgió para cumplir con este requisito.

¿Qué es una función de hash?

Una función hash se puede definir como una función que devuelve un valor entero correspondiente a un objeto. La función hash siempre devuelve el mismo valor entero para el mismo objeto. El valor entero devuelto por la función hash se llama Hash Value. Los siguientes son los puntos importantes con respecto a la función Hash:

  • Siempre devuelve un entero (4 bytes) para un objeto.
  • No podemos calcular el estado del objeto a partir del valor hash, es decir, las funciones hash son de naturaleza irreversible.
  • Dos objetos iguales tendrán el mismo valor hash.
  • Dos objetos desiguales no siempre tienen valores Hash diferentes.

Aplicaciones de la función hash

Estas son las aplicaciones comunes de las funciones hash:

1. Estructuras de datos

Casi todos los lenguajes de programación contienen estructuras de datos basadas en hash. Por ejemplo, Java contiene estructuras de datos de tabla de hash, mapa de hash, conjunto de hash, conjunto de árbol que se basan en la función de hash. La base de estas estructuras de datos es el diseño clave-valor donde cada clave es única, mientras que puede existir el mismo valor para varias claves.

2. Resumen del mensaje

Este algoritmo se utiliza en una verificación de integridad de datos. Este algoritmo toma un mensaje de cualquier longitud como entrada y produce datos de longitud fija (128 bits) como salida. Los ejemplos de los algoritmos de resumen de mensajes incluyen MD2, MD4, MD5 y MD6.

3. Algoritmo de hash seguro

Este algoritmo se usa para la seguridad de los datos y se usa en aplicaciones y protocolos como Secure Socket Layer (SSL). SHA-0, SHA-1, SHA-2 y SHA-3 son categorías comunes del algoritmo de hash seguro.

4. Verificación de contraseña y almacenamiento

Consideremos un escenario de inicio de sesión en el que cuando se ingresa una contraseña para autenticar a un usuario, se calcula un valor hash de la contraseña ingresada y se envía a través de la red al servidor donde se almacena el hash del original. Esto se hace para garantizar que no se detecte cuando se envía una contraseña del cliente al servidor.

5. Operación del compilador

Dado que se utilizan diferentes palabras clave en un lenguaje de programación, para diferenciar entre estas palabras clave e identificadores, el compilador utiliza un conjunto de hash que se implementa utilizando una tabla hash para almacenar todas estas palabras clave e identificadores.

6. Algoritmo Rabin- Karp

Es un algoritmo de búsqueda que utiliza el hash para buscar uno o más patrones en una cadena dada. Es uno de los algoritmos más utilizados.

7. Interfaces comparables y comparadores

Estas interfaces contienen funciones que se utilizan para comparar dos objetos a la vez. El valor de retorno de estas funciones puede ser negativo, cero o positivo en función de si un objeto dado es menor, igual o mayor que el objeto con el que estamos comparando. Internamente, el comparador y las interfaces comparables utilizan una función hash para comparar objetos entre sí.

8. Cola prioritaria

La cola de prioridad es diferente a la cola normal que sigue el orden FIFO (Primero en entrar, primero en salir). En la cola de prioridad, los elementos se organizan en un orden personalizado en función de su prioridad, que se implementa internamente utilizando comparables y comparadores cuyos pasantes se basan en funciones de hash.

Diseño de funciones hash

Estos son algunos principios generales de diseño para crear funciones hash:

  • Una función hash debe evaluarse de manera eficiente.
  • Los valores hash calculados a partir de funciones hash deben distribuirse uniformemente, esto ayuda a evitar colisiones.
  • El lenguaje de programación Java proporciona una función hash general con el método hashCode () en la superclase Object.

public int hashCode ()(
//Logic goes here
)

Hash Collision en Java

Se produce una colisión hash cuando dos o más objetos devuelven el mismo valor hash. Tomemos un ejemplo de un mapa de hash de Java que almacena datos en pares clave-valor. Cuando colocamos un objeto en un mapa hash, se calcula el valor hash de la clave y se encuentra en función de esta ubicación del depósito de valores hash para almacenar el objeto de valor. Los objetos que tienen diferentes valores hash deben ir en diferentes depósitos. Cuando dos o más objetos tienen el mismo valor hash, se almacenan en la misma ubicación del depósito utilizando una estructura de datos adicional llamada lista vinculada. Todos los objetos que tienen el mismo valor hash se encadenan mediante una lista vinculada. Este mecanismo se llama encadenamiento. Las siguientes son las formas de manejar las colisiones es una función hash:

  • Encadenamiento: como ya se mencionó, la idea detrás del encadenamiento es crear una lista vinculada de objetos que tengan el mismo valor hash. El encadenamiento es una técnica simple pero requiere una sobrecarga de memoria adicional.
  • Direccionamiento abierto: en esta técnica, todos los elementos se almacenan en una tabla hash en la que cada entrada contiene un registro o NULL. Cuando se busca un elemento, se busca en cada entrada de la tabla hash el registro deseado hasta que se encuentre el registro requerido o se concluya que el registro no existe en la tabla.

Ventajas de Hashing

Las siguientes son las ventajas del hash:

  1. Compare el contenido de dos archivos de manera fácil y eficiente, sin abrirlos.
  2. Las funciones de hash se utilizan para verificar la integridad de un archivo.
  3. Con la ayuda del hash, la operación de búsqueda en las estructuras de datos se ha vuelto más rápida.
  4. Las funciones de hash desempeñan un papel vital en la seguridad de los datos, ya que la mayoría de los algoritmos y protocolos de seguridad utilizan hash.
  5. El hash convierte los datos en un valor o clave de longitud fija más corta que representa la cadena original que se puede enviar a través de la red.

Desventajas de Hashing

Además de las ventajas, también hay algunas limitaciones de hashing:

  1. Hashing no se puede implementar para ordenar datos.
  2. La colisión de hash no se puede evitar prácticamente, lo que a su vez conduce a la ineficiencia.

Artículos recomendados

Esta es una guía para la función Hashing en Java. Aquí discutimos las aplicaciones de la función hash junto con las ventajas y desventajas. También puede consultar los siguientes artículos para obtener más información:

  1. Declaración e inicialización de VB.Net
  2. Programa Java que muestra HashMap y TreeMap
  3. Tipos de hashing en DBMS
  4. Técnicas de esteganografía.
  5. Matrices en programación Java
  6. Hashmap en Java