Estructuras de Datos para Network Engineers 101: Hash Tables (Parte I)
Tags: hash, python, netmiko, networkautomation
Published: 2021-05-03 13:20:47

## 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.

|Algoritmo|Caso Promedio|Peor Caso|
|---------|-------------|---------|
|Inserción|{% katex %}O(1){% endkatex %}|{% katex %}O(n){% endkatex %}   |
|Busqueda |{% katex %}O(1){% endkatex %}|{% katex %}O(n){% endkatex %}   |
|Eliminación|{% katex %}O(1){% endkatex %}|{% katex %}O(n){% endkatex %}   |

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](https://kb.netgear.com/21586/What-is-a-MAC-based-VLAN-and-how-does-it-work-with-my-managed-switch) para equipos Cisco que no poseen diche feature. Se estará implementando una Tabla de Hash y se usará el módulo de [Netmiko](https://pynet.twb-tech.com/blog/automation/netmiko.html), 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](https://dev.to/jorgmassih/estructuras-de-datos-para-network-engineers-101-las-linked-list-50n9): 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 :joy::joy:, 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](https://es.wikipedia.org/wiki/Funci%C3%B3n_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 :sweat_smile:? Tranquilo, a continuación te presento la hiper-mega-apoteósica imagen explicativa:

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xfn5022carx4yatwy5c5.png)

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](https://elcodigoascii.com.ar) 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 {% katex inline %}\mod 5{% endkatex %} 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 :wink:.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/n2w4dcl7cqx9s2tsosnr.png)

#### 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.

![Alt text of image](https://media.giphy.com/media/urp8cVywl1Sk8/giphy.gif)

Nah!:joy::joy:, 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_](https://link.springer.com/content/pdf/10.1007/3-540-58108-1_10.pdf).

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3g0qmj89h6vqqvrygvd0.png)

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](https://www.educative.io/edpresso/what-is-chaining-in-hash-tables), 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 {% katex inline %}O(n){% endkatex %}, 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 {% katex inline %}n{% endkatex %} para llegar al elemento que queremos. Te lo explico mejor con una ilustración.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/06yrmo8xyd3hnpshc338.png)

## 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](https://dev.to/jorgmassih/estructuras-de-datos-para-network-engineers-101-las-linked-list-50n9).

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](https://info.keylimeinteractive.com/the-four-pillars-of-object-oriented-programming), de todos modos pienso hacer una serie sobre POO.

```python
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`.

```python
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.  

```python
	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.

```python
	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](https://pypi.org/project/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.

{% replit @Jorgmassih/Hashtabletutorial %}

<a href="https://www.buymeacoffee.com/jorgmassih"><img src="https://img.buymeacoffee.com/button-api/?text=Buy me a coffee here&emoji=⌨️&slug=jorgmassih&button_colour=5F7FFF&font_colour=ffffff&font_family=Lato&outline_colour=000000&coffee_colour=FFDD00"></a>