Hash table
Una funzione hash assegna una key a un bucket; le collisioni richiedono una strategia.
Che cos’è Hash table?
Una funzione hash assegna una key a un bucket; le collisioni richiedono una strategia.
Conta parole con chaining e unordered_map.
Punti importanti
- Definisci gli invarianti prima delle operazioni.
- Gestisci stati vuoto, pieno e fallimenti di memoria.
- Valuta insieme complessità e ownership.
Esempi di codice C e 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=1Confronto tra C e C++
L’esempio C usa key fisse per mostrare i bucket; std::unordered_map possiede nodi, cresce e accetta stringhe arbitrarie.
C
Strutture e operazioni sono separate, con allocazione esplicita.
C++
Classi e container proteggono invarianti e risorse.
Esercizi pratici
Esegui entrambe le versioni e modificale per osservare le diverse garanzie.
- Testa stati vuoto e pieno.
- Implementa cleanup e cerca leak.
- Confronta con un container standard.