Introducción.

	Después de haber usado las estructuras de datos conocidas como listas enlazadas y los árboles binarios de búsqueda, unos métodos fiables y eficaces en el guardado y en la búsqueda de información, seguro que el usuario no pretende que le ofrezcamos otra opción para suplir dichas necesidades. Es aquí dónde se equivoca. Les presentamos, con mucho orgullo, la estructura Hash: pensada para esas personas que guardan una gran cantidad de información, sin importar el orden, pero que no le interesa perder tiempo esperando los tediosos segundos de reacción de las primeras estructuras de datos mencionadas. 
	Pero... ¿Ésto significa que las listas enlazadas y los árboles binarios de búsqueda no son métodos espectaculares de guardado de información? La respuesta es un rotundo no. Éstas estructuras son muy eficaces en su trabajo y su uso se mantiene en la actualidad. Ésto no cambia que haya otras opciones, como la ya presentada estructura Hash, que tiene muchas ventajas. Entonces, vamos con el asunto.


TDA HASH.

	En general, un hash está compuesto por los siguientes elementos: la estructura en dónde se va a localizar la información, y una función especial, conocida como la función de hash. En rasgos generales, la información que se va a guardar, va a ser mandada por el usuario con una clave, que la identifique de las otras. La función de hash le va a asignar a dicha clave un número, que es incambiable, y caracteriza a dicha clave. Ese número es ahora utilizado para encontrar la posición en la que se guardará el elemento, en la estructura antes mencionada. Es natural preguntarse sí dos claves distintas pueden "sacar" el mismo número de la función hash, y la respuesta es que sí, y cómo se resuelve éste resultado, también conocido como una colisión, es lo que caracteriza a los tipos de hash que existen.   
	El funcionamiento de dicha estructura es entonces sencillo. Para insertar, se utiliza la clave mandada para localizar la posición en la que la información se va a almacenar. Para buscar y eliminar elemento se utiliza el mismo proceso. El usuario puede ver que es un proceso sencillo, y seguro que ya lo quiere probar con la información que quiere almacenar, pero antes veamos los distintos tipos de hash, y el que se decidió implementar para éste proyecto. 

Hash Cerrado.
	La estructura de éste hash es un vector en el que se guarda la información. El tamaño de dicho vector se mantiene constante durante todo el proceso, salvo una excepción, que se explicará más adelante. Sí hay una colisión cuando se inserta un elemento, el hash cerrado lo resuelve de la siguiente forma: recorre el vector hasta encontrar una posición vacía, en la que se inserta el elemento. Aunque el hash cerrado es muy beneficioso desde el punto de vista de memoria utilizada, las cosas se pueden complicar cuando, por ejemplo, se busca un elemento con una clave, y la posición donde debería estar el elemento está ocupada por otro, entonces hay que recorrer el vector en su búsqueda. 

Hash Abierto.
	El hash abierto, como su nombre lo indica, permite usar memoria aparte de la estructura principal para almacenar los elementos. Es el tipo de hash que emplea el trabajo presentado, en el que se decidió usar, como estructura principal, un vector de listas: en cada posición del vector hay un puntero a una lista enlazada, por lo que se resuelve el defecto del hash cerrado. Sí se inserta un elemento en un hash vacío, se crea una lista en su posición específica dada por su clave, y se añade dicho elemento. Sí se inserta otro, y hay una colisión, simplemente se añade el elemento a la lista ya existente. Dicho proceso facilita mucho las cosas para la búsqueda y eliminación de información, ya que, dada una clave, el elemento siempre se va a encontrar en la lista que hay en la respectiva posición.


Comentarios adicionales del TDA Hash.

	Como se explicó, un hash es una estructura muy llamativa por sus cualidades, respecto a las otras estructuras ya mencionadas. La estructura principal, en nuestro caso un vector de listas, tiene por lo menos una capacidad dada desde el comienzo. Entre más elementos se añadan al hash, más posibilidades hay de que haya colisiones, por lo que, cuando el factor de ocupación (número de elementos insertados dividido por la capacidad del hash) es igual o mayor a uno, es preferible crear una estructura nueva con una capacidad mayor, en la que se van a insertar los mismos elementos, actualizando la estructura original. Éste proceso se conoce como rehasheo, y es muy útil para evitar colisiones que de otra forma hubieran sucedido. 

¿Vale la pena?
	Puede ser que el usuario ya esté cómodo con las listas enlazadas o con los árboles binarios. ¿Vale la pena el cambio? La respuesta es un depende. La inserción en una lista enlazada mal implementada es O(n), que significa que aumenta el tiempo conforme aumenta el número de elementos. A su vez, la inserción en árboles binarios de búsqueda es O(log(n)), lo cual es mucho mejor, pero igual depende de la cantidad de elementos en el árbol. Para la búsqueda y eliminación, cada estructura mantiene el mismo tiempo ya mencionado para su incersión. Ahora veamos cómo lo maneja un hash: para cualquier proceso, ya sea inserción, eliminación, o búsqueda, se utiliza la clave para calcular la posición en la que se va a almacenar/encuentra el elemento en la estructura principal. La idea es que la función de hasheo sea lo más aleatoria posible, pero que sea rápida al mismo tiempo. En la implementación presentada, en la que se recomienda que la clave tenga por lo menos dos letras, el tiempo es relativamente corto, dependiendo netamente de la longitud de la clave. Por lo que, en comparación, la inserción, eliminación o búsqueda de un elemento con su clave es O(longitud de clave). Comparando con las otras estructuras, cuando hay muchos elementos, O(n)>O(log(n))>>>O(longitud de clave), por lo que es más rápido y eficaz el uso de un hash. En otros casos, no hay mucha diferencia entre el uso de uno u otro, por lo que queda a criterio del usuario cual usar en cuáles casos.


Compilación y Ejecución del TDA Hash.
	
	Antes de usar la estructura de datos, es muy importante que el usuario lea las pre y post condiciones de las funciones que se encuentran en el archivo hash.h. Una vez hecho esto, para usarlo, el usuario solo tiene que poner en la cabecera de su .c #include "hash.h" y #include "hash_iterador.h". Para compilarlo, se recomienda poner dicho .c en la misma carpeta junto a los otros archivos. Procedemos a abrir la términal desde dicha carpeta, para no preocuparnos de la ruta a cada archivo, y compilamos con la siguiente línea: "gcc -g -Wall -Werror -std=c99 -Wconversion -Wtype-limits -pedantic -O0 NOMBRE_ARCHIVO_USUARIO.c hash.c lista.c hash_iterador.c -o ejecutable". Los flags son puramente opcionales, pero se recomiendan para poder encontrar cualquier posible error, y así garantizar el correcto funcionamiento de su programa. Para ejecutarlo, pones ./ejecutable y siente la magia.