La guía sin código para las tablas hash y hash

Si ha programado antes, seguro que se ha encontrado con tablas hash y hash. Muchos desarrolladores han utilizado tablas hash de una forma u otra, y los desarrolladores principiantes deben aprender esta estructura de datos fundamental. Solo hay un problema:

Todos los tutoriales con los que se encuentre seguramente hablarán sobre el hash y las tablas hash en JavaScript, Python o algún otro lenguaje de programación.

Lo que esto significa es que puede entender un poco sobre cómo funciona el hash y cómo usar una tabla hash en [insertar idioma aquí], pero puede perder los principios de cómo funciona.

¿No sería genial si pudiéramos aprender sobre el hash sin conocer ningún idioma en particular? Si sabe cómo funciona el hash y qué es una tabla hash, el idioma no debería importar.

Ese es el enfoque sin código, y en esta publicación te enseñaré todo sobre las tablas hash y hash, independientemente del lenguaje de programación que estés usando actualmente. Ya sea que sea un desarrollador junior o senior, todos aprenderán algo de esta publicación.

Entonces, ¿qué es una función hash de todos modos?

Antes de entrar en todas las cosas elegantes, déjeme decirle qué es el hash. Para hacerlo más fácil, imaginemos que tenemos una caja negra:

Esta caja negra es especial. Se llama caja de función. Lo llamaremos un cuadro de función porque este cuadro asignará una variable independiente en la entrada a una variable dependiente en la salida (suena mathy pero tengan paciencia conmigo).

Nuestro cuadro de función funciona así: si ponemos una letra en el cuadro, obtenemos un número. Dado que nuestro cuadro es un cuadro de función, solo puede haber una salida para cada entrada en el cuadro.

Nuestro cuadro de función tomará una letra de AJ en la entrada y generará un número correspondiente del 0 al 9 en la salida. Entonces, si ingresamos C, obtendremos 2 en la salida.

Esto forma los fundamentos de lo que es una función hash. Sin embargo, la función hash va un paso más allá. Asignaremos los datos de la entrada a algún valor numérico de la salida, normalmente una secuencia hexadecimal.

Entonces, básicamente, todo lo que hace el hash es usar una función para asignar datos a un valor numérico o alfanumérico representativo. Para la función hash, independientemente del tamaño de la entrada, la salida siempre será la misma.

¿Qué pasa con las tablas hash?

Entonces, en este punto, es posible que se pregunte qué es una tabla hash. Las tablas hash utilizan hash para formar una estructura de datos.

Las tablas hash utilizan un método asociativo para almacenar datos mediante lo que se conoce como un sistema de búsqueda de valores clave. Todo lo que eso significa es que, en una tabla hash, las claves se asignan a valores únicos.

Este sistema de organización de datos da como resultado una forma muy rápida de encontrar datos de manera eficiente. Esto se debe a que, dado que cada clave se asigna a un valor único, una vez que conocemos una clave, podemos encontrar el valor asociado al instante.

Las tablas hash son extremadamente rápidas y tienen una complejidad de tiempo del orden de O (1).

¿Confuso? Eche un vistazo a este diagrama, donde tenemos varias cajas de funciones que generan valores hash.

En este escenario, cada carácter de la entrada (cada uno es una clave) tiene una función hash aplicada, y la función hash en el cuadro de función genera el valor hash. Este valor resultante luego se asigna a un índice en la lista o matriz vinculada subyacente que se usa para implementar la tabla hash.

La estructura resultante se verá así:

Colisiones de hash

Este es un buen momento para hablar sobre la colisión en funciones hash y tablas hash.

Una función en matemáticas es ideal porque un elemento de la entrada se asigna exactamente a un elemento de la salida.

En una función hash, sin embargo, no siempre es así. A veces, valores hash diferentes en la entrada pueden producir el mismo valor hash en la salida. Cuando esto ocurre, se obtiene lo que se conoce como colisión hash.

Las colisiones de hash no son muy comunes en la mayoría de los casos de uso, ya que un pequeño cambio en la entrada puede producir una salida dramáticamente diferente. Pero cuantos más datos tenga que ingresar a la función hash, más probable es que ocurra una colisión.

En el ejemplo de tabla hash que proporcionamos anteriormente, asumimos que se utilizó una matriz para implementar la tabla hash. Si bien esto es bueno para tablas hash simples, en la práctica, no son muy buenas para manejar colisiones.

Como tal, se utiliza un método conocido como encadenamiento. En el encadenamiento, si la tabla hash devuelve el mismo valor hash para varios elementos, simplemente "encadenamos" los elementos junto con los mismos valores hash en el mismo índice en la tabla hash.  

De esta manera, en lugar de implementarla como una matriz con un índice, implementamos la tabla hash utilizando una lista vinculada donde cada elemento es una lista en lugar de simplemente tener un solo valor asignado.

Pero a medida que aumenta la longitud de la cadena, la complejidad temporal de la tabla hash puede empeorar. También se utiliza un método conocido como direccionamiento abierto. En él, se encuentran ubicaciones alternativas en la estructura de datos subyacente que implementa la tabla hash. Solo tenga en cuenta que este método reducirá la eficiencia de la tabla hash y tiene una complejidad de tiempo peor.

¿El hash es lo mismo que el cifrado o la codificación?

Mucha gente tiende a asociar el hash con el cifrado o la codificación. Entonces, ¿es el cifrado hash? ¿Es lo mismo que codificar?

Verá, en el cifrado confundimos los datos para que solo alguien con la clave necesaria para descifrar los datos tenga acceso a ellos. Cuando utilizamos un cifrado de cifrado, no solo ciframos los datos, sino que también queremos descifrar los datos en algún momento. En cifrado queremos recuperar los datos originales.

El hash, por otro lado, toma datos y produce una salida con el propósito de confirmar la integridad de los datos. En el hash no tenemos la intención de recuperar los datos originales.

La codificación se diferencia del cifrado y el hash en que el objetivo de la codificación no es ocultar los datos para ningún propósito de seguridad, sino simplemente convertir los datos a un formato que pueda usar otro sistema.

¿Qué puedo hacer con el hash?

¡Hashes y tablas de hash tienen numerosos usos! Éstas incluyen:

  1. Criptosistemas
  2. Verificaciones de redundancia cíclica
  3. Los motores de búsqueda
  4. Bases de datos
  5. Compiladores

O cualquier sistema que tenga un proceso de búsqueda complejo.

Terminando

En esta publicación, hemos cubierto los conceptos básicos del hash, ¡todo sin escribir una sola línea de código! Esto fue fácil, ¿verdad? El enfoque sin código es una forma mucho más fácil de aprender sobre estos temas fundamentales.

Aprendimos que las funciones hash se pueden usar para convertir objetos en una salida alfanumérica de longitud fija. También aprendimos que las tablas hash son sistemas de búsqueda de valores clave y, aunque funcionan bien, no son perfectas y, a veces, sufren colisiones.

Al final de esta publicación, debe conocer la diferencia entre hash, cifrado y codificación, y también tener una idea de dónde se pueden usar los hash.

¿Te gustó el enfoque sin código? ¿Quieres ir más lejos?

Aprenda sobre tablas hash y otras estructuras de datos y algoritmos en el libro "Estructuras y algoritmos de datos sin código". Obtendrá una expansión de lo que se cubrió en esta publicación y aprenderá sobre muchos más temas, ¡todo sin escribir una sola línea de código!

Estructuras de datos y algoritmos sin código: aprenda DSA sin escribir una sola línea de código | Armstrong Subero | Apress Este libro le ofrece una nueva perspectiva sobre algoritmos y estructuras de datos, completamente libre de código. Aprenda sobre algoritmos de estructura de datos (DSA) sin tener que abrir su editor de código, usar un compilador o mirar un entorno de desarrollo integrado (IDE) .... Armstrong Subero Menú de búsqueda Carrito V Su carrito está actualmente vacío. Iniciar sesión Cuenta Librería Iniciar sesión Apress Access