Hashing Flashcards
Defina funcion de hashing.
En su más básica definición una función de hashing debe ser capaz de recibir como input un cierto dato cualquiera y devolver un número acotado a un cierto intervalo. Al conjunto de claves posibles (input) lo denominaremos ”espacio de claves” y al conjunto de números que la función de hashing puede devolver lo llamaremos ”espacio de direcciones”.
Explique mecanismos de resolucion de colisiones.
i) Búsqueda lineal (direccionamiento abierto o hashing cerrado)
La búsqueda lineal es una solución muy sencilla al problema de las colisiones. Cuando queremos almacenar un dato pero su posición está ocupada buscamos linealmente y de forma cı́clica hasta encontrar un lugar libre o bien hasta volver al lugar original en cuyo caso la tabla está llena. Cuando queremos recuperar un dato tenemos que tener en cuenta que si en la posición indicada por la función de hashing encontramos otro dato entonces el dato que buscamos podrı́a estar en otra posición por lo que tenemos que buscar linealmente hasta encontrar el dato o bien un lugar vacı́o. Notemos que si se permiten bajas no podemos detenernos al encontrar una posición dada de baja.
La búsqueda lineal es sencilla pero a medida que aumenta la cantidad de datos en la tabla degrada muy rápidamente y se parece mucho a una simple búsqueda lineal que es O(n) en lugar de O(1).
ii) Encadenamiento de Sinónimos (direccionamiento cerrado o hashing abierto)
En este método vamos a generar una lista enlazada en cada posición de nuestra tabla de hash para almacenar allı́ las claves que colisionen. Nuestra estructura es entonces un vector de listas. Cuando queremos almacenar un dato simplemente lo agregamos a la lista que está en la posición indicada por la función de hashing. Cuando queremos buscar un dato accedemos a la lista indicada por la función de hashing y buscamos en la lista.
Este método es muy sencillo y es un poco mas eficiente que la búsqueda lineal pero cuando existen muchas colisiones las listas pueden volverse bastante largas por lo que las búsquedas pueden tender a O(n) en lugar de O(1). No obstante es un método muy usado y que debemos tener en cuenta ya que tiene varias aplicaciones interesantes.
Que se quiere garantizar con Hopscotch hashing?
Queremos garantizar O(1) para las búsquedas y queremos que la zona en la cual tenemos que buscar el dato sea igual o muy cercana a la indicada por la función de hashing para favorecer el uso de datos en memoria cache.
Explique hopscotch hashing.
En Hopscotch partimos de un vector de ”m” elementos que es nuestra tabla de hash, vamos a usar además un número ”k” que indica que tan lejos podemos guardar un dato respecto de la posición indicada por la función de hashing. Si k=3 podemos guardar el dato en h(x), h(x)+1 o h(x)+2. Es decir que cada dato tiene k posiciones en las cuales puede almacenarse. Es importante mencionar que esto no quiere decir que si esas k posiciones están ocupadas el dato no pueda almacenarse.
La forma de resolver colisiones en Hopscotch es muy interesante y muy simple. En primer lugar consideremos las posiciones h(x), h(x)+1 hasta h(x)+k-1, si alguna de esas posiciones está libre entonces podemos guardar el dato allı́ sin ningún problema. Si todas las posiciones están ocupadas entonces buscamos linealmente hasta encontrar una posición libre y a partir de esta recorremos hacia atrás viendo si podemos ir moviendo datos hacia adelante de forma de liberar una posición válida para nuestro dato.
Que sucede en el caso que no se pueda liberar un espacio en las k posiciones en Hopscotch hashing?
En el caso que no se pueda liberar un espacio en las k posiciones donde puede almacenarse el dato, se debe cambiar el tamaño de la tabla y reubicar a los datos de la misma.
Enuncie las propiedades que debe cumplir una funcion de hashing.
- La función tiene que ser muy eficiente, es decir, generar el resultado en muy poco tiempo.
El motivo por el cual usamos una función de hashing es para poder recuperar un dato de forma muy eficiente en tiempo similar a O(1). Si la función de hashing fuera muy compleja e ineficiente podrı́a pasar que buscar linealmente en el vector tarde menos tiempo que usar la función de hashing y acceder a la posición indicada, lo cual invalidarı́a el uso de una función de hashing por completo. - La función tiene que producir la menor cantidad de colisiones posibles.
El segundo punto pide minimizar las colisiones, lo cual no solo implica evitar, en lo posible, que nuestras claves colisionen sino que debemos intentar que la distribución de las claves en el espacio de direcciones sea lo más pareja posible.
FNV hashing.
Data: s: string Result: h: integer 1 h = 14695981039346656037; 2 for c in s do 3 h = h * 1099511628211; 4 h = h XOR c; 5 return h;
Jenkins
Data: s: string Result: hash: integer 1 for hash=i=0;i> 6); 5 hash += (hash << 3); 6 hash xor= (hash >> 11); 7 hash += (hash << 15); 8 return hash;
Pearson.
Data: s: string Result: hash: integer 1 h = 0; 2 for c in s do 3 index = h xor c; 4 h = T[index]; 5 return h
A que cosa es Pearson una primera aproximacion y por que?
La función de Pearson nos permite también una primera aproximación rudimentaria a una función de hashing perfecta. Si tenemos pocas claves a hashear podemos simplemente probar diferentes tablas al azar hasta que alguna de las tablas nos genere una función de Pearson que sea perfecta. Este es un algoritmo aleatorizado de tipo Las Vegas ya que siempre produce un resultado exacto pero con una cierta probabilidad, aunque puede tardar mucho tiempo en generar el resultado.
Caracteristicas de funciones de hashing criptograficas.
- La función tiene que producir la menor cantidad de colisiones posibles
- Dado h(x) tiene que ser muy difı́cil hallar x
- Tiene que ser muy difı́cil hallar x e y de forma tal que h(x)=h(y)
- Un cambio mı́nimo en la clave tiene que producir un cambio significativo en el resultado (efecto avalancha)
Cual es la funcion de hash cript. mas usada hoy dia y en que se basa?
SHA-256 se basa en la combinación de dos primitivas criptográficas muy importantes: La construcción de Merkle-Damgard y la construcción de Davis-Meyer.
Explique construccion de Merkle-Damgard.
En esta construcción suponemos que existe una función ”f” que recibe un bloque de m bits y devuelve un bloque de n bits con n < m. A esta función se la llama función de compresión aunque no tiene nada que ver con compresión de datos. Simplemente devuelve menos bits que los que recibe.
El objetivo de la construcción de Merkle-Damgard es dado un string de una cantidad arbitraria de bits emitir un único resultado de tamaño igual al tamaño que emite la función f.
Supongamos que ”n” es la cantidad de bits que emite nuestra función de compresión f, dividimos nuestro mensaje entonces en bloques de ”n” bits agregando un padding al final en caso de ser necesario. El padding es crı́tico para el correcto funcionamiento de la función y no debe ser fijo.
Como la función de compresión recibe bloques de m bits agregamos un bloque ficticio llamado IV con el cual podemos comenzar el algoritmo. Notar que la construcción es muy simple y se basa en concatenar el resultado anterior de f al bloque próximo y luego volver a aplicar f.
Mediante la construcción de Merkle-Damgard podemos aplicar una función de compresión cualquiera a un mensaje de longitud arbitraria de forma segura, veamos ahora como construir una función de compresión segura.
Explique construccion de Davis-Meyer.
La construcción de Davis-Meyer permite generar una función de compresión segura a partir de un algoritmo de encripción seguro. El procedimiento es muy simple, recibimos dos bloques y usaremos uno como clave para encriptar el otro, finalizando con el xor entre el bloque 1 y el resultado de la encripción.
SHA-256 es entonces una construcción de Merkle-Damgard en donde la función de compresión es una construcción de Davis-Meyer usando SHACAL-2 como algoritmo de encripción. Cada bloque del mensaje tiene 512 bits y la función de compresión devuelve 256 bits.
Son intercambiables las funciones de hashing tradicionales y criptograficas? Por que?
Es importante destacar que es un error muy grave usar una función de hashing tradicional cuando se necesita una función de hashing criptográfica pero también es un error grave usar una función criptográfica cuando solo necesitamos una función de hashing tradicional. Esto es porque las funciones criptográficas son menos eficientes y estarı́amos perdiendo velocidad a cambio de propiedades adicionales que no necesitamos!
Explique el concepto de Hashing universal.
El concepto de Hashing Universal pasa por construir, no una función de hashing, sino una familia de funciones de hashing, de forma tal que podamos elegir las funciones que necesitemos entre el total de funciones que constituyen dicha familia.
Defina hashing universal.
Para cualquier función de hashing de nuestra familia la probabilidad de que dos claves diferentes colisionen debe ser menor o igual a 1/m, siendo m el espacio de direcciones de cada una de las funciones de hashing de la familia.
De la funcion de Carter-Wegman. Para que se usa?
h(x) = (a ∗ x + b (mod p)) (mod m)
p: un número primo mayor o igual a m
a: un número entre 1 y p − 1
b: un número entre 0 y p − 1
Se usa para valores atomicos (numericos).
Hashing para claves de long. fija.
Sea m, nuestro espacio de direcciones, p un número primo mayor o igual a m y sean claves x compuestas por r + 1 números: x 0 ..x r . Vamos a elegir r + 1 números a i entre 1 y m-1 y nuestra función de hashing quedará definida por:
sum (de i=0 a r) de: (a i ∗ x i (mod p)) (mod m)
Notemos que hemos definido una familia de funciones de hashing ya que por cada selección de los parámetros a i creamos una función diferente. En concreto como cada a i puede tomar un valor entre 0 y m − 1 hay un total de m r+1 funciones de hashing en nuestra familia.
Hashing para claves de long. variable.
Consideramos ahora el caso en el cual nuestras claves tienen longitud variable y no hay una longitud máxima definida. Si existiera una longitud máxima para las claves entonces podrı́amos simplemente hacer padding y usar la familia de funciones anterior sin perder la universalidad de la misma.
Planteamos la siguiente familia de funciones de hashing para una clave de longitud l
h(x) = h_int ((sum de(i=1 a l) de) x_i ∗ a^i ) mod p))
p: un número primo grande
a: un número aleatorio entre 0 y p−1
h_int: una función de hashing tomada de la familia universal que definimos anteriormente que recibe un número entre 0 y p − 1 y devuelve otro número entre 0 y m − 1 siendo m nuestro espacio de direcciones.
Cuckoo hashing.
Se basa en el uso de más de una función de hashing.
Cada función de hashing va a definir una posición alternativa para nuestro dato en una tabla de hash. El algoritmo de búsqueda es muy simple. El dato tiene que estar en alguna de las dos posiciones alternativas o no está en la tabla, es decir, es O(1). La inserción funciona de forma muy sencilla: almacenamos el dato en la posición indicada por la primer función de hashing. Si ese lugar estaba ocupado entonces reubicamos ese dato en su posición alternativa y ası́ sucesivamente, hasta que no hay más datos a reubicar o bien entramos en un loop.
Que problemas tiene Cuckoo hashing? Como se solucionan?
Es importante estudiar algún mecanismo para detectar si es posible o no dar de alta un nuevo dato sin necesidad de detectar que nuestro algoritmo ha entrado en loop. Para hacer esto, es posible construir un grafo en el cual hay tantos nodos como posiciones en nuestra tabla de hash y por cada dato que insertamos construimos una arista que une las dos posiciones candidatas, indicadas por la función de hashing.
En nuestro grafo cada componente conexo admite un ciclo pero no dos.
Explique formas de hacer Cuckoo mas eficiente.
El método del Cuckoo puede hacerse más eficiente admitiendo más de un registro por bucket (posición en la tabla de hash) o bien usando 3 funciones de hashing en lugar de 2. Con buckets para 2 registros y 2 funciones de hashing es posible llenar mas de un 90% de la tabla con muy baja probabilidad de que una inserción falle.
La nomenclatura a usar es C_(n,m) en donde n es la cantidad de funciones de hashing a usar y m es la cantidad de registros por bucket. Por ejemplo, en C_(2,8) usamos dos funciones de hashing con buckets que soportan 8 claves cada uno. Varios esquemas de Cuckoo Hashing logran eficiencia cercana al 95% del espacio por lo que podemos generar tablas de hash bastante compactas.
Cuckoo Hashing With a Stash
Cuando una inserción falla una alternativa muy simple es poner el registro en cuestión en un área de overflow o stash. Esto permite que la clave se almacene y que el método continue siendo eficiente. Con áreas de stash relativamente pequeñas el método del Cuckoo puede lograr una eficiencia muy importante. El costo, obvio, es tener que buscar las claves en el Stash en caso de no encontrarlas en las posiciones que indique la función de hashing. Curiosamente, si el tamaño del stash es constante, esto no afecta el orden del algoritmo, ya que O(2) = O(2 + k) siendo k el tamaño del stash una constante.
Explique Two-way hashing.
Es posible generalizar el método del cuckoo a un esquema genérico en el cual usemos múltiples funciones de hashing. Consideremos primero el caso más simple en el cual tenemos una tabla de hash en donde cada bucket tiene capacidad para k datos. Usando dos funciones de hashing tenemos dos buckets candidatos para cada clave y podemos tomar como heurı́stica almacenar el dato en el bucket que tenga menor cantidad de datos. Este esquema se denomina Two-Way hashing. Es un esquema bastante eficiente y que requiere muy pocos detalles de programación.
