Tabla hash
Una función hash asigna cada key a un bucket; las colisiones requieren una estrategia.
¿Qué es Tabla hash?
Una función hash asigna cada key a un bucket; las colisiones requieren una estrategia.
Cuenta palabras con chaining y unordered_map.
Puntos importantes
- Define invariantes antes de implementar operaciones.
- Maneja estados vacío, lleno y fallos de memoria.
- Evalúa complejidad y ownership conjuntamente.
Ejemplos de código C y C++
main.c
#include <stdio.h>
#include <string.h>
typedef struct Item {
const char *key;
int count;
struct Item *next;
} Item;
unsigned hash(const char *text) {
unsigned value = 5381;
while (*text) {
value = value * 33u ^ (unsigned char)*text++;
}
return value % 5;
}
int main(void) {
const char *words[] = {"c", "cpp", "c"};
Item items[2] = {{"c", 0, NULL}, {"cpp", 0, NULL}};
Item *buckets[5] = {0};
for (int index = 0; index < 2; ++index) {
unsigned bucket = hash(items[index].key);
items[index].next = buckets[bucket];
buckets[bucket] = &items[index];
}
for (int index = 0; index < 3; ++index) {
Item *item = buckets[hash(words[index])];
for (; item; item = item->next) {
if (strcmp(item->key, words[index]) == 0) {
++item->count;
break;
}
}
}
printf("c=%d cpp=%d\n", items[0].count, items[1].count);
}
c=2 cpp=1C++
main.cpp
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, int> counts;
for (const std::string word : {"c", "cpp", "c"}) {
++counts[word];
}
std::cout << "c=" << counts["c"]
<< " cpp=" << counts["cpp"] << '\n';
}
c=2 cpp=1Comparación entre C y C++
El ejemplo C fija keys para mostrar buckets; std::unordered_map posee nodos, crece y acepta strings arbitrarios.
C
Estructuras y operaciones están separadas y la memoria es explícita.
C++
Clases y contenedores protegen invariantes y recursos.
Ejercicios prácticos
Ejecuta ambas versiones y modifícalas para observar sus garantías.
- Prueba estados vacío y lleno.
- Implementa cleanup y busca fugas.
- Compara con un contenedor estándar.