Hace casi dos semanas que empece una nueva etapa como desarrollador. A día de escribir este post, estoy como backend en una empresa que se basa en blockchain, como core del negocio.
Esto me ha motivado para empezar hablar tanto de blockchain, como de Golang, el lenguaje que más estoy usando en esta increíble etapa. Pero ahora escribo este post, para hablar de la base de todo, el hash y su finalidad.
Qué es un hash ?
Si me permitís la comparación, podemos comparar un hash, con nuestro DNI.
- Identifica de manera inequívoca un objeto/persona
- Es una sucesión de caracteres finitos
Qué es una función hash ?
Una función hash, es una función de entrada y salida, la cual recibe un elemento o elementos que son «transformados» en una cadena de texto finita. Siguiendo con el ejemplo/comparación del DNI:
Persona -> HashFunction -> Hash (DNI)
Objetivo de la función hash ?
Aunque la explicación es un poco «pillada por los pelos«, es un símil bastante aproximado de su finalidad.
El objetivo de la función hash, es generar un identificador único para cada elemento de entrada. Como podéis deducir, esta función es tan buena como la capacidad de la función, de no generar colisiones en los identificadores.
Qué quiero decir ? que cualquier función hash que para dos elementos diferentes genere el mismo identificador, es una función condenada a no ser segura.
Entonces tenemos que:
- Generar identificadores únicos
- Function unidireccional. Un elemento puede generar un identificador, pero un identificador no puede generar un elemento
- La función hash de un elemento, siempre devolverá el mismo identificador.
- Representar cualquier elemento de cualquier longitud en una cadena de longitud finita
Obviamente son objetivos muy ambiciosos con una clara obsolescencia. La capacidad de generar identificadores de una función hash de 256 bytes es 2^256
Qué es una colisión ?
Pongamos que tenemos una función hash, que se basa en sumar los pesos que tienen las letras en una palabra
La función es bastante obvia para el ejemplo. Como podéis observar: entrada y generar, devuelven el mismo valor, entonces podemos decir que el resultado de la función de hash colisiona con generar y entrada.
Conclusiones
El objetivo es identificar todos los elementos, potencialmente, infinitos con una id finita y no colisionable. Por eso personalmente la característica de identificador único esta asociada al tiempo que tardemos en generar todos los elementos posibles para este hash
Qué es una hash table ?
Una vez sabemos cuál es el objetivo de una función hash, podemos hablar de las hash table. Pero antes de continuar tenemos que pensar, qué generar valores hash de una longitud de 256, tiene un coste, no asumible para determinadas aplicaciones que usan este enfoque.
Podemos usar hash de 256, para contraseñas y otros elementos que se calculan una sola vez.
Hash table
Un hash table es simplemente una estructura de datos para generar una tabla clave/valor. Esta tabla es muy eficiente en la búsqueda de elementos, pero tiene algún que otro problema, el cual la búsqueda que debería ser O(1), sera O(n).
Cuando hablo de clave, hablo de un valor que ponemos nosotros y es el valor de entrada a la función que generara el indice para nuestro vector. Pero qué, co…., mejor un ejemplo
Llegados a este punto ya sabemos que es una función hash y cómo funciona a bajo nivel una hash table. Pero como todo en la programación hay trade off que debemos tener en cuenta si queremos «picar a mano» nuestra propia hash table.
Hablaremos de como solucionar las colisiones en una hash table, diferentes enfoques, ventajas e inconvenientes en futuros post