Unidad 4 - Hashing

Introducción

El término hashing se refiere en realidad a un tipo de función con un fin dado (que vamos a ver más adelante) que se llaman funciones hash. Ésta es una función que dado un algoritmo mapea, un set de datos de longitud variable a otro set fijo.

Por ejemplo, dado un nombre de persona (que obviamente es variable), una función nos genera un número.

El número generado es lo que se llama hashcode.

Utilidad general de funciones hash

Y se preguntarán para qué sirve esto ? Tiene varias aplicaciones, no vamos a ver todas nosotros, de hecho solo una, pero va acá una lista:

• En seguridad: criptografía mejor dicho, se utiliza para varias funciones, pero la más simple es por ejemplo para guardar una contraseña, donde no queremos guardar el texto en plano ya que cualquiera podría leerlo así como está. Entonces la aplicación le aplica una función para generar una representación que solo será legible para quien conozca el algoritmo, es decir para ella misma.
• En el transporte de información: habrán visto que a veces cuando bajan un archivo de internet también está disponible otro más chiquito con un nombre como CHECKSUM. La idea de este uso es checkear de alguna forma si el contenido del archivo que uno bajó, coincide con el original del servidor. Ahora, como sería muy poco práctico volver a comparar byte por byte, resulta que el servidor ya generó un número hash del archivo original, mediante un algoritmo conocido por todos. Entonces cuando uno se baja el archivo, le aplica el mismo algoritmo y así genera otro hash. Si ambos son distintos, entonces quiere decir que en algún punto la información se corrompió. Acá ya vemos la idea de "eficiencia", aplicamos hash para hacer la comparación de dos archivos que podrían ser muy grandes, de forma más eficiente.
• Estructuras de datos: ésta es la aplicación que más nos va a interesar a nosotros. Algunas estructuras contenedoras de datos utilzan una técnica basada en funciones de hash para almacenar sus elementos. Esto es lo que vamos a ver en esta unidad.

Características de la Función Hash

Para que la función sea considerada y se utiliza como una función hash debe cumplir algunas condiciones.

La principal es que sea:

• Determinística: significa que dada una misma entrada, siempre va a generar el mismo valor como salida. Es decir que no depende de una variable externa. Se dice que tiene transparencia referencial.

Ejemplo:

hash("Hola Mundo") -> 99123545

hash("Hola Mundo") -> 99123545

Por otro lado, dependiendo de la aplicación, es decir para qué se utilice (como vimos antes tiene varias aplicaciones) podría tener otros requerimientos.

Funciones de Hash en Python

Para mezclar un poco de teoría con algo de código, veamos como sería eso de calcular el hash de un objeto en Python.

Existe una función que ya calcula el hash de un objeto:

print hash("Hola Mundo")

print hash("Hola Mundo")

Produce:

5087365090501027439

5087365090501027439

Sin embargo podemos hacer nuestra propia función de hash. Acá una muy simple para strings:

def hashMuyPavo(unString):

    return ord(unString[0]) / len(unString)

Nota: ord(caracter) es una función que la representación numérica de un caracter.

HashTable

Entonces veamos para qué es que querríamos tener esta función hash que dado un objeto de entrada me genera un número.

Como ya vimos al tratar otras estructuras como listas enlazadas, algunas operaciones sobre los elementos de las estructuras suelen ser costosas, por ejemplo con complejidad lineal, O(n), donde el tiempo se incrementará con la cantidad de elementos.

Entonces, existen implementaciones que utilizan funciones de hash para implementar operaciones en forma constante, es decir O(k), que de otra manera serían O(n).

El ejemplo:

• la búsqueda de un elemento en una lista: Esto requiere recorrer todos los elementos e ir comparándolos. O(n/2) en promedio, O(n) en el peor de los casos (era el último)
• el obtener el valor dada una clave en un diccionario: la operación get(clave) -> valor que vimos en otro capítulo, también tendrá el mismo problema. Y fíjense que es justamente la función más importanes del diccionario.

Entones, para resolver esto, existe una estructura llamada Hash Table (o tabla de hash), que consiste en almacenar los elementos de entrada utilizando el hashcode como índice de la posición en la que ocupará.

Veamos acá un ejemplo para la implementación de un Diccionario como hashtable:

La ventaja es que ahora ubicar a "John Smith" por ejempo, no requiere recorrer todos los 153 elementos anteriores y comparar 153 veces.

Veamos un ejemplo bien pavo en python. No vamos a implementar una estructura de datos completa, pero mostramos una simplificación para que se den una idea:

Definimos operaciones para crear una lista que va a representar nuestra nueva estructura, llamada HashSet

def crearHashSet(): pass

def agregar(hashset, elemento): pass

def contiene(hashset, elemento): pass

Solo tendremos dos operaciones básicas, el agregar un elemento, y el contiene que sirve para checkear si el elemento dado está en el set.

Entonces esto lo usaríamos así:

s = crearHashSet()

agregar(s, "Hola")

print 'Contiene Hola:', contiene(s, "Hola")

print 'Contiene Chau:', contiene(s, "Chau")

Lo cual imprime:

Contiene Hola: True

Contiene Chau: False

Las implementaciones de Lista que vimos hasta ahora, deberían recorrer todos los elementos e ir comparando hasta el final, o bien encontrar el elemento. Con costo lineal.

Una implementación muy simple que utiliza hashing sería:

def crearHashSet():

    l = []

    for _ in range(200):

        l.append(None)

    return l

def agregar(hashset, elemento):

    hashset[hashMuyPavo(elemento)] = elemento

def contiene(hashset, elemento):

    return hashset[hashMuyPavo(elemento)] == elemento

Lo interesante acá está en la implementación del contiene. Estamos usando la función hash simple que hicimos antes más arriba. Con lo cual este set solo va a funcionar con strings.

Lo interesante es que el contiene() no está recorriendo los elementos. Lo que hace es:

• dado el elemento a checkear, le aplica la función de hash para obtener el hashcode (un número)
• con ese número accede a la posición de la lista.
• luego compara solo el contenido de esa posición con el elemento dado.

Así, solo realizó una comparación, y no tuvo que recorrer. El costo ahora es O(k) constante.

Desventajas

Espacio ocupado

De esto que vimos recién surge la desventaja del HashSet o HashTable, y es que, podría desperdiciar memoria. Ya que la lista tiene que tener un tamaño fijo, no importa si tiene elementos en todas las posiciones o no. En realidad la causa es que los datos suelen estar "alejados", y las posiciones entre ellos estarían vacías.

Veamos como lo utilizamos y las posiciones que realmete ocupa:

agregar(s, "Chau")

agregar(s, "Adios")

agregar(s, "Au revoir")

agregar(s, "Bye")

agregar(s, "A plus tard")

print '-' * 20

print 'Contiene Bye:', contiene(s, "Bye")

Si imprimimos la lista veremos algo así:

SET: [None, None, None, None, None, 'A plus tard', None, 'Au revoir', None, None, None, None, None, 'Adios', None, None, 'Chau', None, ....]

Tamaño de la lista

Otro problema que seguramente habrán notada es que la lista donde se guardan los elementos tiene un tamaño fijo (esa es la idea de hashtable). Ahora cómo calculamos ese tamaño ? En nuestro caso tenemos hardcodeado un 200 porque queríamos evitar encarar ese problema de entrada.

Sin embargo hay dos problemas entonces:

• quién dice cual será ese tamaño ?
• qué pasa si el hashcode de un elemento me dá un número mayor a ese tamaño (200 en nuestro caso) ?

En nuestra implementación para el segundo caso, se va a romper, porque va a intentar acceder a una posición de la lista que no existe.

Existen diferentes estrategias para resolver esto, nombramos algunas comunes acá:

• Incrementar el tamaño de la lista: partimos con un tamaño, pero a medida que ingresan elementos con hashcodes más grandes, vamos agrandando la lista. A ésto se lo conoce como hashing dinámico.
• Aplicar una reducción al hashcode: es decir que nuestro HashSet no va a utilizar el hashcode como índice así como viene, sino que lo transforma para que de un número de [0 a tamaño] (0 a 200 en nuestro ejemplo). Cómo se hacía eso ? con el módulo de la división.

Nuestra nueva implementación con mod, para que no se rompa ante hashcodes muy grandes sería:

def crearHashSet():

    return [None for _ in range(200)]

def agregar(hashset, elemento):

    hashCode = hashMuyPavo(elemento) % 200

    hashset[hashCode] = elemento

def contiene(hashset, elemento):

    hashCode = hashMuyPavo(elemento) % 200

    return hashset[hashCode] == elemento

De paso cambiamos la forma en la que se crea la lista para utilizar listas por comprensión.

Con esta solución igualmente vamos a tener el siguiente problema, de hecho incrementamos la posibilidad de...

Colisiones

Podemos identificar otro problema mirando la implementación de nuestra función de hash. Así, a simple vista, vemos que sería fácil reproducir un caso donde dos strings distintos producen el mismo hash.

Se tienen que dar dos condiciones, dado el string A, y el B

• longitud de A = longitud de B
• primer caracter de A = primer caracter de B

Ejemplo:

print "Chau=", hashMuyPavo("Chau")

print "Ciao=", hashMuyPavo("Ciao")

Produce:

Chau= 16

Ciao= 16

Esto va a ser un problema en nuestra implementación simple de HashSet.

Veamos:

s = crearHashSet()

agregar(s, "Chau")

print 'Contiene Chau:', contiene(s, "Chau")  # BOOM!

agregar(s, "Ciao")

print 'Contiene Ciao:', contiene(s, "Ciao")

print 'Contiene Chau:', contiene(s, "Chau")  # BOOM!

Esto produce:

Contiene Chau: True

Contiene Ciao: True

Contiene Chau: False

Como vemos al agregar el nuevo elemento "Ciao" que tiene el mismo hashcode que "Chau", se está pisando el anterior. A esto se lo denomina colisión.

Colisiones y solución de HashTable con Buckets

Todas las funciones de hash que mapean un conjunto de entrada más grande que el de salida, van a producir colisiones. Lógicamente, porque estamos tratando de mapear por ejemplo 5.000 nombres de personas, a un array fijo de 200 posiciones, por ejemplo.

Entonces por un lado se intentará utilizar funciones uniformes, para evitar colisiones incluso cuando todavía queda espacio en la estructura.

Sin embargo esto no soluciona el problema. Entonces, otra estrategia muy común es modificar nuestro HashSet para que cada posición de la lista no contenga un único elemento, sino que contendrá a su vez una lista. Entonces ahora si, en cada posición podrá haber más de un elemento, sin que se pisen. Si dice que nuestra lista ahora tiene buckets.

Acá vemos un diagrama ejemplificador:

Hagamos entonces una nueva implementación de nuestro HashSet. Lo primero que definimos es cómo queremos que funcione:

s = crearHashSet(hashMuyPavo)

agregar(s, "Chau")

agregar(s, "Ciao")

print 'Contiene Chau?', contiene(s, "Chau")

print 'Contiene Ciao?', contiene(s, "Ciao")

Esperamos que esto de: True y True

Y acá la implementación con algunas mejoras adicionales respecto de la anterior.

Por un lado vamos a definir una clase (struct) para evitar usar la lista diréctamente:

class HashSetConBuckets:

    def __init__(self, funcionHash):

        self.funcionHash = funcionHash

        self.buckets = [ [] for _ in range(200) ]

Acá notamos que nuestra clase tiene dos elementos:

• La función de hash que la recibe por parámetro al construirse. Esto nos permite que nuestro HashSetConBuckets se pueda parametrizar con cualquier función de hash. Antes usábamos siempre nuestro "hashMuyPavo". Fíjense que acá estamos usando la idea de funciones de orden superior con alguna variante.
• Una lista de buckets: acá es donde realmente estarán los elementos, pero a diferencia del ejemplo anterior, estamos definiéndo su contenido por comprensión. Además, lo más importante es que esta lista no va a contener None en todas sus posiciones, sino que va a contener listas vacías (por ahora).

Luego definimos el crear, agregar y contiene:

def crearHashSet(funcionHash):

    return HashSetConBuckets(funcionHash)

def hashCodeDe(hashset, elemento):

    return hashset.funcionHash(elemento) % len(hashset.buckets)

def agregar(hashset, elemento):

    hashCode = hashCodeDe(hashset, elemento)

    hashset.buckets[hashCode].append(elemento)

def contiene(hashset, elemento):

    hashCode = hashCodeDe(hashset, elemento)

    bucket = hashset.buckets[hashCode]

    return elemento in bucket   # aca recorreriamos comparando

Como calcular el hashcode se hizo un poco complejo lo llevamos a otra función chiquita hashCodeDe que dado un set, y un elemento, retorna el hashcode del elemento. Para esto, utiliza la función de hash que se había pasado al HashSet al momento de construirlo. Además al resultado le aplica el modulo de la división por el tamaño de la lista de buckets, en lugar de hardcodera el 200 :)

Pero lo más interesante está en el agregar y el contiene.

• agregar:
  • Calcula el hashcode del nuevo elemento
  • Utiliza ese hashcode como índice
  • A diferencia de la implementación más básica, acá no modificamos la posición diréctamente, ya que contiene una lista, ahora simplemente agregamos el nuevo elemento a esa lista.
• contiene:
  • En forma similar, calcula el hashcode
  • lo usa como índice para obtener la lista "bucket"
  • Luego acá sí, no queda otra que ver si el elemento está en la lista. En este caso estamos usando el operador in de python, pero tenemos que entender que internamente éste no tiene otra opción que recorrer toda la lista y comparar para ver si el elemento está.

De esto se desprende que, si bien ahora nuestro set soporta varios elementos con mismo hashcode, tenemos un costo de tiempo de procesamiento. Sin embargo sigue siendo una mejor solución que tener una lista única y recorrerla toda porque:

• El hashcode actúa como un primer índice para ubicar el bucket donde puede estar el elemento
• El bucket tiene menos elementos que el total, con lo cual recorrerlo no debería ser tan costoso.

HashMap

HashMap es una implementación del TDA Diccionario, que utiliza funciones de hash para almacenar los elementos utilizando el hashcode como índice. En definitiva la idea es la misma que vimos antes en nuestra implementación de HashSet. La diferencia es que:

• HashSet: contiene elementos simples (como una lista), aunque sin un orden específico.
• HashMap: al ser un diccionario, almacena entradas formadas por clave-valor. Donde no puede haber más de una entrada con la misma clave.

Acá vemos un diagrama ejemplo de implementación de HashMap:

Características "deseables" de una función

A continuación una lista de características "deseables" (no obligatorias) para las funciones de hash.

• Rápida: la idea es que vamos a aplicar la función bastante seguido, con lo cual debería ser un cálculo "rápido". En general no es que uno deba preocuparse demasiado de esto, porque las cuentas en general son procesadas bastante eficientemente por la computadora. Pero sí, como ejemplo extremo podemos decir que la función no debería acceder a disco, o cualquier otra operación de I/O ya que en general éstas son las operaciones que más tiempo consumen.
• Determinística: ya lo vimos
• Uniforme: debería distribuir los elementos del dominio en forma uniforme sobre el rango (fijo) de elementos de la imagen. Para evitar así que se compacte y que muchos elementos de entrada produzcan hash muy cercanos. Relacionado con esto...
• De Bajas Colisiones: una colisión es cuando dado dos elementos de entrada, la función genera el mismo valor de hash. Cuando una función no genera ni una colisión, se dice que es perfecta.

TODO's

• Hablar del tamaño inicial y de como ajustarlo para que crezca (hashing dinámico)