¿Qué es una tabla hash y cómo se hace en C? [closed]

11 minutos de lectura

Tengo algunas preguntas sobre una estructura de datos llamada tabla hash (también conocida como matriz asociativa) y cómo se implementa en C.

¿Cómo se hace una tabla hash en C? ¿Qué es una tabla hash y cómo se implementa? ¿Por qué querría usar una tabla hash en lugar de una matriz?

NOTA: Sé que esta es una pregunta muy amplia que requerirá una respuesta larga, pero hice esto porque algunas personas me preguntaron qué era todo. así que lo pongo aquí para explicarlo completamente y ayudar a los demás.

  • @doubleshap Tenía algunos amigos que querían saber qué era y quería publicarlo aquí para que pudiera ayudar a cualquier otra persona en el futuro.

    – maxib7

    10 de agosto de 2015 a las 22:16

  • sí, lo siento por la pregunta realmente general. Comenzó como una pregunta sobre cómo implementar una tabla hash para almacenar nombres en C, pero cuando comencé a escribir la respuesta, quería explicarla más a fondo y se convirtió en esto.

    – maxib7

    10 de agosto de 2015 a las 23:01

avatar de usuario
maxib7

requisitos previos

Para esta respuesta, supondré que sabe cómo usar punteros, estructuras y tiene una comprensión básica del lenguaje C.

También si no lo sabes. Cuando se habla de la velocidad de los algoritmos y las estructuras de datos, debe conocer los términos:

O() = (se pronuncia “Big-oh”) Big-oh u O() se refiere al tiempo de ejecución del “peor de los casos”. De manera similar, en matemáticas, es una notación O grande y describe el comportamiento límite de una función. Si algo es O (1), eso es tiempo constante “realmente bueno”. Si algo es O(n), eso significa que la lista tiene un millón de longitud. En el peor de los casos, se ejecutará un millón de veces. O() es generalmente el que se usa para determinar qué tan rápido se ejecuta algo porque así de rápido se ejecutará en el peor de los casos.

Ω = (letra griega Omega) se refiere a su mejor escenario posible. No se usa tanto como O(), por lo que no entraré en demasiados detalles al respecto. Pero solo sepa que si algo es Ω (1), en el mejor de los casos, solo tomará una vez.

Θ = (letra griega theta) es único en el sentido de que solo se usa cuando el tiempo de ejecución de O() y Ω() es el mismo. Entonces, como en el caso del algoritmo de clasificación recursivo ordenar por fusión. Su tiempo de ejecución es Θ(n(log(n))). Lo que significa que es O(n(log(n))) y es Ω(n(log(n))).

¿Qué es una tabla hash?

Una tabla hash o matriz asociativa es una estructura de datos popular utilizada en la programación. Una tabla hash es solo una lista enlazada (hablaré de lo que es una lista enlazada más adelante) con una función hash. Una función hash básicamente solo toma cosas y las coloca en diferentes “canastas”. Cada “canasta” es solo otra lista enlazada o algo más, según cómo lo implemente. Explicaré más detalles sobre las tablas hash cuando le muestre cómo implementar una.

¿Por qué querría usar una tabla hash en lugar de una matriz?

Una matriz es muy fácil de usar y simple de hacer, pero también tiene sus desventajas. Para este ejemplo, digamos que tenemos un programa y en el que queremos mantener a todos sus usuarios en una matriz.

Eso es bastante simple. Digamos que planeamos que este programa no tenga más de 100 usuarios y llenemos esa matriz con nuestros usuarios.

char* users[100];

// iterate over every user and "store" their name
for (int i = 0; i < userCount; i++)
{
    users[i] = "New username here";
}

Eso funciona muy bien y muy rápido también. Eso es O (1) justo ahí. Podemos acceder a cualquier usuario en tiempo constante.

Pero supongamos ahora que nuestro programa se vuelve muy popular. Ahora tiene más de 80 usuarios. ¡UH oh! Será mejor que aumentemos el tamaño de esa matriz o de lo contrario obtendremos un desbordamiento de búfer.

¿Entonces cómo hacemos eso? Bueno, vamos a tener que hacer una nueva matriz que sea más grande y copiar el contenido de la matriz anterior en la nueva matriz.

Eso es muy costoso y no queremos hacer eso. Queremos pensar inteligentemente y no usar algo que tenga un tamaño fijo. Bueno, ya sabemos cómo usar los punteros a nuestro favor y podemos agrupar información en un struct si quisiéramos.

Entonces podríamos crear un struct para almacenar el nombre de usuario y luego hacer que apunte (a través de un puntero) a un nuevo struct. Voilá! Ahora tenemos una estructura de datos que es ampliable. Es una lista de información agrupada que está unida por punteros. Por lo tanto, el nombre de la lista vinculada.

Listas vinculadas

Así que vamos a crear esa lista enlazada. Primero vamos a necesitar un struct

typedef struct node
{
    char* name;
    struct node* next;
}
node;

Muy bien, entonces tenemos una cadena. name y un… Espera un segundo… Nunca he oído hablar de un tipo de datos llamado struct node. Bueno, para nuestra conveniencia, yo typedef un nuevo “tipo de datos” llamado node que también pasa a ser nuestro struct llamado node.

Entonces, ahora que tenemos nuestro nodo para nuestra lista, ¿qué necesitamos a continuación? Bueno, necesitamos crear una “raíz” en nuestra lista para que podamos traverse (explicaré lo que quiero decir con traverse luego). Así que vamos a asignar una raíz. (recuérdalo node tipo de datos I typdefeditado antes)

node* first = NULL;

Entonces, ahora que tenemos nuestra raíz, todo lo que tenemos que hacer es crear una función para insertar nuevos nombres de usuario en nuestra lista.

/*
 * inserts a name called buffer into
 * our linked list
 */
void insert(char* buffer)
{     
    // try to instantiate node for number
    node* newptr = malloc(sizeof(node));
    if (newptr == NULL)
    {
        return;
    }

    // make a new ponter
    newptr->name = buffer;
    newptr->next = NULL;

    // check for empty list
    if (first == NULL)
    {
        first = newptr;
    }
    // check for insertion at tail
    else
    {
        // keep track of the previous spot in list
        node* predptr = first;

        // because we don't know how long this list is
        // we must induce a forever loop until we find the end
        while (true)
        {
            // check if it is the end of the list
            if (predptr->next == NULL)
            {
                // add new node to end of list
                predptr->next = newptr;

                // break out of forever loop
                break;
            }

            // update pointer
            predptr = predptr->next;
        }
    }         
}

Ahí vas. Tenemos una lista enlazada básica y ahora podemos seguir agregando usuarios todo lo que queramos y no tenemos que preocuparnos por quedarnos sin espacio. Pero esto viene con inconvenientes. El gran problema con esto es que cada nodo o “usuario” en nuestra lista es “anónimo”. No sabemos dónde están ni cuántos usuarios tenemos con esto. (Por supuesto, hay formas de hacer esto mucho mejor, solo quiero mostrar una lista enlazada muy básica) Tenemos que recorrer toda la lista para agregar un usuario porque no podemos acceder al final directamente.

Es como si estuviéramos en una gran tormenta de polvo y no puedes ver nada y tenemos que llegar a nuestro granero. No podemos ver dónde está nuestro granero, pero tenemos una solución. Hay personas paradas allí (nuestras nodes) y todos están sosteniendo dos cuerdas (nuestros punteros). Cada persona solo posee una cuerda, pero otra persona sostiene esa cuerda en el otro extremo. Al igual que nuestro struct, la cuerda actúa como un indicador de dónde están. Entonces, ¿cómo llegamos a nuestro granero? (para este ejemplo, el granero es la última “persona” de la lista). Bueno, no tenemos idea de cuán grande es nuestra línea de personas o adónde van. De hecho, todo lo que vemos es un poste de cerca con una cuerda atada. (¡Nuestra raíz!) Ese poste de la cerca nunca cambiará, así que podemos agarrar el poste y comenzar a movernos hasta que veamos a nuestra primera persona. Esa persona está sosteniendo dos cuerdas (el puntero del poste y su puntero).

Así que seguimos viajando a lo largo de la cuerda hasta que llegamos a una nueva persona y nos agarramos a su cuerda. ¡Finalmente, llegamos al final y encontramos nuestro granero!

Así que esa es una lista enlazada en pocas palabras. Sus ventajas son que puede expandirse tanto como desee, pero su tiempo de ejecución depende del tamaño de la lista, es decir, O(n). Entonces, si hay 1 millón de usuarios, ¡tendría que ejecutarse 1 millón de veces para insertar un nuevo nombre! Wow, eso parece realmente un desperdicio solo para insertar 1 nombre.

Afortunadamente, somos inteligentes y podemos crear una mejor solución. ¿Por qué no, en lugar de tener una sola lista enlazada, tenemos algunas listas enlazadas? Una matriz de listas vinculadas, por así decirlo. ¿Por qué no hacemos una matriz de tamaño 26? Así podemos tener una lista enlazada única para cada letra del alfabeto. Ahora, en lugar de un tiempo de ejecución de n. Podemos decir razonablemente que nuestro nuevo tiempo de ejecución será n/26. Ahora, eso no hará mucha diferencia si tienes una lista de 1 millón. Pero vamos a mantenerlo simple para este ejemplo.

Así que tenemos una matriz de listas vinculadas, pero ¿cómo vamos a clasificar a nuestros usuarios en la matriz? Bueno… ¿por qué no hacemos una función que decida qué usuario debe ir a dónde? Esta función “hash” a los usuarios si lo hace en una matriz o “tabla”. Así que vamos a crear esta lista enlazada “hash”. Por lo tanto, el nombre tabla hash

Tabla de picadillo

Como acabo de decir, nuestra tabla hash será una matriz de listas vinculadas y será codificada por la primera letra de su nombre de usuario. A irá a la posición 0, B a 1, y así sucesivamente.

los struct para esta tabla hash será la misma que la estructura de nuestra lista enlazada anterior

typedef struct node
{
    char* name;
    struct node* next;
}
node;

Ahora, al igual que nuestra lista enlazada, necesitamos una raíz para nuestra tabla hash

node* first[26] = {NULL};

La raíz será una matriz del tamaño del alfabeto y todas las posiciones en ella se inicializarán para NULL. (Recuerde: el último elemento en una lista enlazada siempre tiene que apuntar a NULL o de lo contrario no sabríamos que fue el final)

Hagamos una función principal. Se necesita un nombre de usuario que vamos a codificar y luego insertar.

int main(char* name)
{
    // hash the name into a spot
    int hashedValue = hash(name);

    // insert the name in table with hashed value
    insert(hashedValue, name);
}

Así que aquí está nuestra función hash. Es bastante simple. Todo lo que queremos hacer es mirar la primera letra de la palabra y dar un valor de 0 a 25 según la letra que sea.

/*
 * takes a string and hashes it into the correct bucket
 */
int hash(const char* buffer)
{
    // assign a number to the first char of buffer from 0-25
    return tolower(buffer[0]) - 'a';
}

Así que ahora todo lo que necesitamos es crear nuestra función de inserción. Se verá como nuestra función de inserción anterior, excepto que cada vez que hagamos referencia a nuestra raíz, lo haremos como una matriz.

/*
 * takes a string and inserts it into a linked list at a part of the hash table
 */
void insert(int key, const char* buffer)
{
    // try to instantiate node to insert word
    node* newptr = malloc(sizeof(node));
    if (newptr == NULL)
    {
        return;
    }

    // make a new pointer
    strcpy(newptr->name, buffer);
    newptr->next = NULL;

    // check for empty list
    if (first[key] == NULL)
    {
       first[key] = newptr;
    }
    // check for insertion at tail
    else
    {
        node* predptr = first[key];
        while (true)
        {
            // insert at tail
            if (predptr->next == NULL)
            {
                predptr->next = newptr;
                break;
            }

            // update pointer
            predptr = predptr->next;
        }
    }
}

Eso es lo básico de una tabla hash. Es bastante simple si sabes cómo usar punteros y estructuras. Sé que fue un ejemplo bastante simple de una tabla hash con solo una función de inserción, pero puede mejorarlo mucho y ser más creativo con su función hash. También puede hacer que la matriz sea tan grande como desee o incluso usar una matriz multidimensional.

  • se bloqueará cuando haga strcpy porque no asignó memoria para la cadena.

    –Bill Morgan

    13 de junio de 2020 a las 2:01

  • “Bueno, vamos a tener que hacer una nueva matriz que sea más grande y copiar el contenido de la matriz anterior en la nueva matriz”. Esto es un poco engañoso. Matrices dinámicas que utilizan realloc son de uso generalizado.

    – programador

    11 de marzo de 2021 a las 10:02

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad