Estructuras de Datos para Network Engineers 101: Hash Tables (Parte I)

Introducción

"Aqui es donde se separan los niños de los hombres."
— Yo en mi mente cuando empecé a aprender Tablas de Hash.

A muchas personas se les dificulta aprender Tablas de Hash, recuerdo que fue la Estructura de Datos que menos me gustó cuando la vi en la universidad, realmente es una estructura relativamente fácil de aprender, y aquí trataré de explicártela lo mejor posible.

Esta estructura tambien tiene la particularidad de que es MÁGICA, sí, mágica, es una de las Estructuras de Datos más eficientes y rápidas, esto es porque su tiempo de ejecución es constante en el caso promedio. En el primer post mencionamos algo relacionado con complejidad de un algoritmo y su tiempo de ejecución, las Tablas de Hash tienen una complejidad tremendamente buena, abajo te lo detallo.

La motivación de este post será un poco más práctica, se trata de una aplicación que estoy desarrollando sobre Mac Based Vlan para equipos Cisco que no poseen diche feature. Se estará implementando una Tabla de Hash y se usará el módulo de Netmiko, el cual se utiliza para Network Automation. Pero, debido a lo extenso que podría salir este post, lo dividiré en dos partes, en esta te explico todo el fundamento y luego en el otro te explico como desarrollé la aplicación.

¿Qué es una Hash Table?

La Tabla de Hash es una Estructura de Datos de manera "asociativa", esto quiere decir, que tiene que asociar "algo" con "algo" para llevar a cabo sus operaciones.

Antes de explicar como funciona, volvamos al pasado, al primer post: Habíamos dicho que un array o lista, almacena los elementos en bloques de memoria contiguos (uno al lado del otro), eso facilita muchas cosas, como el acceso a algún índice de esa estructura de manera instantánea. Esto nos dice que, si tuviéramos el índice de un elemento en un array o lista, pudiéramos acceder de inmediato a dicho elemento, en un tiempo constante, es decir, no hay que recorrer toda la estructura para llegar a ese elemento.

En la estructura de la Tabla de Hash tenemos 3 componentes importantes:

1. Los elementos a insertar
2. Una función de Hash
3. La Tabla de Hash

El primer componente, es decir, los elementos a insertar, se identifican con un Key único, esto quiere decir que, la manera de nosotros insertar o extraer un valor de la estructura es mediante dicho Key, dicho Key es elegido por nosotros. Podemos ver el Key como un apodo que le ponemos a nuestro valor para poder identificarlo dentro de la estructura, por ejemplo: en mi familia habemos muchos con nombre de Jorge, mi papá se llama Jorge, mi hermano mayor se llama Jorge, uno de mis hermanos más pequeños se llama Jorge, uno de mis primos se llama Jorge, y yo tal vez le ponga Jorge a un hijo mío para no perder la cultura 😂😂, cuando hacemos reuniones familiares y estamos todos los Jorges, usan nuestros segundos nombres (el cual sirve de Key) para referirse a nosotros.

Luego que entendemos el concepto, debemos buscar la manera de asociar el Key a la estructura, esto nos lleva al segundo componente importante, la función de Hash, esta recibe el Key como entrada y retorna un número. Es como una cafetera, le hechas el café y el agua y luego esta te devuelve el resultado. Es importante destacar que dicho número debe ser generado por funciones que corran en tiempo constante, las funciones de Hash eficientes utilizan operaciones matemáticas para lograrlo.

Luego, lo que procede es almacenar los valores en la tabla, ¿Cómo se crea la tabla? Es una lista o arreglo. ¿En que índice de la lista o arreglo almaceno los elementos? En el índice del número obtenido por la Función de Hash. ¿Aún sigues sin entender 😅? Tranquilo, a continuación te presento la hiper-mega-apoteósica imagen explicativa:

Una forma "fácil" en la que aprendí a ver las Tablas de Hash fue la siguiente: imagina que vas a un hospital a consultarte con tu médico, cuando llegas, alguien en la recepción te atiende, tu le dices a que médico quieres ir, y dependiendo del médico que sea te dicen el número del consultorio al que debes ir. Lo mismo pasa con las Tablas de Hash, de acuerdo al Key de algún Value, la Función de Hash retornará un número correspondiente a dicha posición en la tabla (recuera que es una lista o arreglo) donde debe ir el Value.

A continuación te dejo un ejemplo: supongamos que queremos guardar las edades (nuestro Value) de personas, y las asociaremos a sus nombres (nuestro Key).

Para que esta explicación sea lo más simple posible, utilizaremos una Función de Hash sencilla; tomaremos cada letra del nombre de la persona (el Key), las convertiremos en su valor ASCII y las sumaremos.

Los algoritmos de Hash suelen retornar números grandes, esto puede provocar que necesitemos índices grandes dentro de la tabla, lo que se traduce a mucha ocupación en memoria. Algo que se suele hacer es ajustar dicho índice al tamaño de nuestra tabla, es decir, si nuestra tabla será de tamaño de 100 índices, entonces dividimos el número entre 100 y tomamos el residuo (o resto) porque este nunca será mayor al divisor, esto nos garantiza que el valor del hash nunca quedará fuera de la tabla cuando utilicemos un número fijo de valores. En nuestro ejemplo utilizaremos una tabla de tamaño 5, por lo que tendremos que obtener el $\mod 5$ de las sumas resultantes de los valores de los caracteres, entonces, ese resultado será nuestro índice dentro de la tabla. A continuación, una imagen que vale más que mil palabras que te pueda escribir 😉.

Colisiones

Ya estamos claros en que el índice en donde se alojarán los datos es dados por una función de Hash, pero, ¿Qué pasa si dos Keys producen el mismo número de índice cuando pasan por la Función de Hash? Bueno, en ese caso explota la Tabla de Hash, tienes que activar de inmediato la alarma anti incendios y a parte de eso, correr lo más lejos posible en el menor tiempo posible.

Nah!😂😂, cuando eso pasa ocurre lo que se llama una "Colisión", por lo regular, las colisiones ocurren en los malos algoritmos de Funciones de Hash, de hecho, en teoría estas están siempre supuestas a pasar, no obstante un buen diseño de dicha función reduce las probabilidades de que estas ocurran. Si te interesa el diseño de Funciones de Hash te dejo este Paper.

Tal como se muestra en la imagen anterior, existe una colisión en el ejemplo anterior cuando intentamos insertar a 'Felisa' en la Tabla de Hash, esto porque su índice correspondiente coincide con el índice para 'Isaac'.

Lidiando con Colisiones

Existen varias maneras, porque después de todo, hay que almacenar más de un dato en la misma posición de la tabla, una muy popular es The Chainning Technique, esta consiste en tener una Estructura de Datos como una Linked List en cada índice de la Tabla de Hash. Debido a las colisiones es que se dijo al principio que en el peor caso las operaciones en la Tabla de Hash tomarían una complejidad de tiempo de $O(n)$ , el peor de los casos se da cuando todas entradas a la Tabla de Hash producen colisiones entre ellas y por consiguiente, se almacenarían en el mismo lugar y tendriamos que recorrer toda la Linked List de tamaño $n$ para llegar al elemento que queremos. Te lo explico mejor con una ilustración.

Creando nuestra propia Tabla de Hash

Antes de empezar, quisiera decir que el lenguaje que hemos estado utilizando a lo largo de esta serie contiene esta Estructura de Datos de manera Built-in, no obstante, estaremos realizando nuestra propia estructura para demostrar los conceptos que hemos explicado anteriormente. Es importante mencionar que se utilizará Chainning Technique para manejar las colisiones, para emplear dicho mecanismo haremos uso de nuestra clase Linked List creada en el primer post.

Primero debemos definir los nodos a utilizar en nuestra Tabla de Hash, ya que estos serán utilizados por nuestras Linked Lists, podríamos utilizar la clase Nodo del principio, pero ahora tenemos un atributo adicional que representa al Key, entonces, haciendo uso del segundo y tercer pilar de la POO, la encapsulación y la herencia; crearemos una clase que herede de la clase Nodo para añadir el atributo de key. Si quieres saber más acerca de los 4 pilares de la POO, te recomiendo esto, de todos modos pienso hacer una serie sobre POO.

class HashNode(Node):
    def __init__(self, key, value):
        self._key = key

        super().__init__(value)

    @property
    def key(self):
        return self._key

Nota importante: Recordemos que una Key es un atributo inmutable, y cambiarlo podría implicar moverlo en la Tabla de Hash. Dicha operación no es permitida en esta estructura, entonces, haremos uso de la propiedad key y no le crearemos un setter para que no se pueda modificar.

Ahora vamos a crear nuestra clase HashTable, recordemos que dicha tabla tiene que tener un tamaño específico, también debe tener una Función de Hash asociada para colocar los elementos de acuerdo a su key, por lo cual, como parámetro para instanciar la clase vamos a requerir un número size y una Función de Hash hash_func. Adicional, tenemos el atributo hash_function que nos define la Función de Hash requerida, y tambien el atributo de la tabla table, el cual no es más que una lista de Linked Lists vacías del tamaño del atributo size.

class HashTable:
    def __init__(self, size: int=1024, hash_func:type(lambda x: None) = hash):
        self.size = size
        self.hash_function = hash_func
        self.table = [LinkedList() for _ in range(self.size)]

    def _test_hash_value(self, value):
        if value > self.size:
            raise Exception('Hash function must return a lower number than Hash Table size: {}'.format(self.size))

Nota: La Función de Hash estará como parametro en la clase debido a que la queremos de manera implicita, esto es para poder modificarla de acuerdo a la aplicación del Hash.

Como se pudo observar, se introdujo una función llamada _test_hash_value, la cual velará porque la Funcion de Hash no retorne un valor que pueda estár fuera del índice de la tabla, de ocurrir, se activará una excepcion.

Luego, procedemos con los métodos más importantes: los de insertar y buscar elementos en la Tabla de Hash, para ambos vamos a utilizar los Magic Methods __setitem__ y __getitem__.

Para insertar en la tabla, se obtiene el valor calculado por la Función de Hash y luego se ubica la Linked List de esa posición en la tabla, si la tabla está vacía es porque no hay ningún otro elemento y no ha ocurrido una colisión, sólo tendríamos que asignar el nodo al head de esa Linked List. Cuando ocurre una colisión, se debe insertar el nodo al final de la Linked List. En el caso de la actualización de algún value, se buscará en la Linked List por por dicho Key y Value.

Para buscar en la tabla, hacemos un procedimiento similar, primero sometemos el key a la Función de Hash, luego, accedemos a la Linked List en esa posición y verificamos si el Key se encuentra en la misma.

    def __setitem__(self, key, value):
        node = HashNode(key, value)

        # obtiene el indice calculado por la función de hash
        hash_value = self.hash_function(node.key, self.size)

        # verifica si el valor del índice está en la tabla
        self._test_hash_value(hash_value)

        # obtiene la linked list del índice obtenido
        table_value = self.table[hash_value]

        # asigna el nodo a la posición si no hay algun otro
        if table_value.head is None:
            table_value.head = node

        # lidia con las colisiones y la actualización de values
        else:
            for hash_node in table_value:
                # si el key ya está en la tabla, lo actualiza
                if hash_node.key == key:
                    hash_node.value = value
                    break
                # si ocurre una colisión, añade el nodo al final
                if hash_node.next is None:
                    hash_node.next = node
                    break

    def __getitem__(self, key):
        # obtiene el indice calculado por la función de hash
        hash_value = self.hash_function(key, self.size)

        # verifica si el valor del índice está en la tabla
        self._test_hash_value(hash_value)

        node = self.table[hash_value].head

        # si no hay nodo en la cabeza de la LL, entonces está vacia
        if node is None:
            return None

        # busca un nodo en la Linked List
        while node.key != key:
            if node.next is None:
                return None
            node = node.next

        value = node.value
        return value

Por último, tenemos la función para remover elementos, la cual es básicamente la misma que la función que la de inserción, sólo que una vez encontrado el nodo, lo desvincula de la Linked List. Esto se hace a través de una método llamado unlink añadido a nuestra clase Linked List, esta clase elimina un nodo especifico de una Linked List.

    def remove(self, key):
        # obtiene el indice calculado por la función de hash
        hash_value = self.hash_function(key, self.size)

        # verifica si el valor del índice está en la tabla
        self._test_hash_value(hash_value)

        # verifica si el nodo existe para desvincularlo
        # de una linked list en específico
        item_value = self[key]

        if item_value is None:
            return None

        table_value = self.table[hash_value]
        table_value.unlink(HashNode(key, item_value))

Conclusión

Aunque estamos en la parte conclusiva, esto no quiere decir que cerraremos este tema aquí, ya sabes los fundamentos, el siguiente post será totalmente práctico. Verás una aplicación utilizando el módulo de Netmiko y otros más que facilitan tareas de automatización.

Por otra parte, creamos una clase que maneja las Tablas de Hash de manera correcta, tal vez no sea la más óptima pero sirve para practicar los conceptos. Mi profesor de Estructura de Datos decía que la mejor forma para comprobar los conocimientos es hacer una implementación de estos, aunque también decía que en teoría, la teoría y la práctica son lo mismo; sin embargo, en la práctica no ocurre así... ¿Paradójico verdad?

A continuación, haremos una comparación de desempeño entre la clase que hemos hecho con la que Python ya trae de manera Built-in, a partir de los resultados decidiremos cual vamos a utilizar para desarrollar la aplicación del siguiente post. Abajo te dejo el Replit del código utilizado junto con la demostración.