Práctica #5: Tablas hash

Descripción

Esta actividad se debe realizar y entregar por equipos.

NOTA: Los archivos necesarios para comenzar esta práctica están disponibles en el repositorio de GitHub del curso.

Esta práctica consiste en definir una clase HashTable<K, T> la cual implementa una tabla de hash con resolución de colisiones por encadenamiento (chaining), tal como se explica en el capítulo 8 del libro de [STEPHENS]. Los elementos de la tabla son parejas de llave/valor, donde las llaves son de tipo K y los valores asociados son de tipo T. La clase debe declararse e implementarse completamente en el archivo hashtable.h y debe incluir todas las operaciones que se describen a continuación.

IMPORTANTE: Antes de la definición de cada operación debes incluir un comentario que indique su correspondiente complejidad de tiempo de ejecución.

Operación	Descripción
HashTable(int num_buckets)	Constructor. Crea una tabla hash vacía con el número de cubetas indicado como argumento.
~HashTable()	Destructor. Se encarga de liberar toda la memoria dinámica ocupada por esta tabla hash.
void clear()	Función miembro. Elimina todos los elementos (parejas de llave/valor) de esta tabla hash.
bool contains_key(     K key ) const	Función miembro. Devuelve true si key es una llave contenida en esta tabla hash, o false en caso contrario.
T get(K key) const	Función miembro. Devuelve el valor asociado a la llave key de esta tabla hash. Lanza una excepción std::invalid_argument si key no existe en la tabla.
T get_or_default(     K key,     T default_value ) const	Función miembro. Devuelve el valor asociado a la llave key de esta tabla hash. Si key no existe en la tabla devuelve default_value.
bool is_empty() const	Función miembro. Devuelve true si esta tabla hash está vacía, o false en caso contrario.
std::vector<K> keys() const	Función miembro. Devuelve un vector con todas las llaves de esta tabla hash ordenadas de manera ascendente. Se puede usar la función std:sort para ordenar el vector resultante.
bool put(K key, T value)	Función miembro. Asocia key a value en esta tabla hash. Si key está previamente contenida en la tabla, actualiza su valor asociado y devuelve false. De otra forma, crea un nuevo elemento (pareja de llave/valor) y devuelve true.
void put_all(     const HashTable<K, T>&         other )	Función miembro. Añade todos los elementos (parejas de llave/valor) contenidos en other a esta tabla hash. Si alguna llave de other está previamente contenida en esta tabla, solo se actualiza su valor asociado. De lo contario se crea un nuevo elemento (pareja de llave/valor).
bool remove(K key)	Función miembro. Si key existe en esta tabla hash remueve el elemento correspondiente (pareja de llave/valor) y devuelve true. De otra forma devuelve false.
int size() const	Función miembro. Devuelve el número de elementos (parejas de llave/valor) contenidos en esta tabla hash.
bool operator==(     const HashTable<K, T>&         other ) const	Función miembro. Devuelve true si esta tabla hash es igual a other, o false en caso contario. Se considera que dos tablas hash son iguales si tienen el mismo tamaño y si tienen las mismas llaves asociadas a los mismos valores.

Prueba tu código utilizando las pruebas unitarias contenidas en el archivo tests.cpp (contiene 100 121 aserciones en total). Así mismo, corre el código usando valgrind para verificar que no existan fugas de memoria ni otro tipo de errores.

¿Qué se debe entregar?

Coloca en un comentario en la parte superior del archivo fuente hashtable.h la información personal de los autores (matrícula y nombre), por ejemplo:

/*----------------------------------------------------------
 * Práctica #5: Tablas hash
 * Implementación de la clase HashTable.
 *
 * Fecha: 15-Oct-2021
 * Autores:
 *           A01770771 Sylvie Laufeydottir
 *           A01777771 Loki Laufeyson
 *----------------------------------------------------------*/

Solo es necesario que lo entregue un miembro del equipo.

La fecha límite es el viernes 5 de noviembre.