C++ / Tablas hash

Bienvenidos sean a este post, hoy veremos otra estructura de datos.

Hasta ahora hemos visto a distintas estructuras de datos para manejar la informacion, asi como tambien tree para entender como trabajan. En el post anterior mencionamos que set y map son mas que eficientes para la mayoria de los casos. Pero tambien mencionamos que existe uno mejor para poder manipular la informacion. Las tablas hash son muchas rapidas que las anteriormente citadas, y estas son basicamente un vector indexado. Por ejemplo, puede ser un gran vector que posee punteros a listas.

std::vector<std::list<T>> tabla_hash;

El principal superpoder de un vector es su acceso a los elementos ya que toma un tiempo constante. Esto permite a su vez que las tablas hash use cualquier tipo como la clave de los contenedores. La idea basica de una tabla hash es usar una funcion hash bien curada que generara un indice unico para la clave de entrada. Para entender el concepto, vamos a analizar el siguiente ejemplo:

#include <iostream>
#include <list>

using namespace std;

class TablaHash
{
int capacidad;
list<int> *tabla;

public:
        TablaHash(int V);
        void ingresar(int clave, int dato);
        void borrar(int clave);
        void mostrarHash();

        int chequearPrima(int n)
        {
                int i;
                if (n == 1 || n == 0) return 0;
                for (i = 2; i < n / 2; i++)
                        if (n % i == 0) return 0;

                return 1;
        }
        int getPrima(int n)
        {
                if (n % 2 == 0) n++;
                while (!chequearPrima(n)) n += 2;

                return n;
        }

        int funcionHash(int clave)
        {
                return (clave % capacidad);
        }
};
TablaHash::TablaHash(int c)
{
        int tam = getPrima(c);
        this->capacidad = tam;
        tabla = new list<int>[capacidad];
}
void TablaHash::ingresar(int clave, int dato)
{
        int indice = funcionHash(clave);
        tabla[indice].push_back(dato);
}

void TablaHash::borrar(int clave)
{
        int indice = funcionHash(clave);

        list<int>::iterator i;
        for (i = tabla[indice].begin(); i != tabla[indice].end(); i++)
                if (*i == clave) break;

        if (i != tabla[indice].end()) tabla[indice].erase(i);
}

void TablaHash::mostrarHash()
{
        for (int i = 0; i < capacidad; i++)
        {
                cout << "tabla[" << i << "]";
                for (auto x : tabla[i])
                        cout << " --> " << x;
                cout << endl;
        }
}

int main()
{
        int claves[] = {231, 321, 212, 321, 433, 262};
        int datos[] = {123, 432, 523, 43, 423, 111};
        int tam = sizeof(claves) / sizeof(claves[0]);

        TablaHash h(tam);

        for (int i = 0; i < tam; i++)
                h.ingresar(claves[i], datos[i]);

        h.mostrarHash();
}

Primero definimos una clase llamada TablaHash, la cual sera encargada de manejar la tabla de hash. Tendremos una variable para manejar la capacidad y un puntero para almacenar la tabla. En la parte publica tenemos cuatro prototipos: el constructor, un metodo para ingresar los valores, otro para eliminarlos y el ultimo para mostrar el hash pero en un rato los definiremos. Luego tenemos una serie de metodos para el hash. La primera es para chequear la prima del numero recibido, donde si el valor recibido es 1 o 0 devuelve 0. Si n es mayor a 1 usaremos un bucle que se limitara por la mitad del valor recibido. Si el modulo del valor pasado dividido por i no posee ningun resto y devuelve 0, en caso de no cumplirse nada de esto devuelve 1.

El siguiente metodo devuelve el valor primo informado. Para ello, tenemos un condicional donde si el resto de la division es igual a 0, incrementa el valor recibido en uno. Luego tenemos un bucle donde lo haremos mientras el metodo anterior no devuelva false o sea distinto de 0 y en este, incrementaremos el valor recibido en dos. Una vez finalizado, devolvemos el resultado final de n. El ultimo metodo devuelve el resto de la clave recibida por la capacidad de la tabla. Lo siguiente es la definicion de los prototipos anteriores.

Lo primero que definiremos sera el constructor, en este estableceremos el valor de capacidad y crearemos la tabla donde almacenaremos los valores. El siguiente metodo es para ingresar los datos, este recibira la clave y el valor asociado. Primero definimos una variable que representa al indice en la lista, mediante la clave recibida y la funcionHash, mediante este y push_back asociamos este al valor que apuntara. El siguiente metodo a definir es el encargado de eliminar el valor que le pasemos mediante la clave. Volvemos a repetir el proceso de generar un indice mediante funcionHash y la clave recibida. Luego generamos un objeto iterador, el cual usaremos en el siguiente bucle para pasar por todos los elementos de la tabla y donde si el iterador coincide con la clave informada salimos del bucle. Con nuestro puntero determinado lo comparamos con un condicional. Si este es distinto al final de la tabla procede a eliminarlo de la misma.

Por ultimo, tenemos la definicion para mostrar los datos de la tabla. Esta pasara por todas las posiciones de la tabla, gracias a capacidad, y en ella representaremos a cada posicion de la tabla y de cada una de ellas mostraremos los valores asociados y asi hasta terminar con la tabla general. En el main, primero definimos dos arrays con distintos valores que representan a las claves y los datos que asociaremos respectivamente. La variable sera para el tamaño de nuestra tabla y luego crearemos el objeto de la clase anterior. Lo siguiente es ingresar las claves y valores para asociarlos y tenerlos en nuestra tabla,, y finalmente lo mostramos. Compilemos y veamos como es la salida:

$ ./hash
tabla[0] --> 123
tabla[1]
tabla[2] --> 523
tabla[3] --> 111
tabla[4]
tabla[5]
tabla[6] --> 432 --> 43 --> 423
$

Observen como se fueron agregados en posiciones no consecutivas, asi como tambien surgio un inconveniente. La coincidencia de valores con una clave asociada, pero esto se soluciono mediante el uso de list porque a medida que coinciden las va agregando al final de la misma. Tal como vemos en el ultimo caso.

En resumen, hoy hemos visto a tabla hash, que es, como se crea, para que esta pensado, asi como algunas caracteristicas mas. Espero les haya resultado de utilidad sigueme en tumblr, Twitter o Facebook para recibir una notificacion cada vez que subo un nuevo post en este blog, nos vemos en el proximo post.