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