Hash table (tabella hash)
Ultimo aggiornamento
Una tabella hash memorizza gli elementi in un array di bucket. Per collocare o trovare una chiave, la passa a una funzione di hash e prende il risultato modulo il numero di bucket: così ottiene l'indice del bucket in O(1). Premi play qui sopra per vedere ogni chiave trasformata con l'hash in un bucket e memorizzata, poi una ricerca che salta dritta al bucket giusto.
Quando due chiavi finiscono nello stesso bucket, cioè in caso di collisione, questa visualizzazione usa il concatenamento separato: ogni bucket contiene una piccola lista e le chiavi in collisione vengono aggiunte in fondo. Finché la tabella non è troppo piena (fattore di carico basso) e l'hash distribuisce bene le chiavi, le catene restano corte e inserimento, ricerca ed eliminazione sono O(1) in media.
Complessità temporale
| Operazione | Media | Caso peggiore |
|---|---|---|
| Inserimento | O(1) | O(n) (tutte le chiavi collidono) |
| Ricerca | O(1) | O(n) |
| Eliminazione | O(1) | O(n) |
| Spazio | O(n) | O(n) |
Concetti chiave
| Termine | Significato |
|---|---|
| Funzione di hash | Associa una chiave a un indice di bucket |
| Collisione | Due chiavi finiscono nello stesso bucket |
| Concatenamento separato | Ogni bucket contiene una lista delle voci in collisione |
| Indirizzamento aperto | Alternativa: cerca la prossima posizione libera |
| Fattore di carico | voci / bucket: determina il ridimensionamento |
Esempio svolto
Inserimento delle chiavi 20, 34, 9, 13 in una tabella con 7 bucket, usando hash(k) = k % 7:
| Passo | Struttura | Azione |
|---|---|---|
Inserisci 20 | bucket 6: [20] | 20 % 7 = 6, bucket 6 vuoto, memorizza 20 |
Inserisci 34 | bucket 6: [20, 34] | 34 % 7 = 6, collisione con 20, aggiungi 34 alla catena |
Inserisci 9 | bucket 2: [9] | 9 % 7 = 2, bucket 2 vuoto, memorizza 9 |
Inserisci 13 | bucket 6: [20, 34, 13] | 13 % 7 = 6, collisione, aggiungi 13 alla catena del bucket 6 |
Cerca 34 | bucket 6: [20, 34, 13] | 34 % 7 = 6, scorri la catena: 20 no, 34 corrisponde: trovato |
Quando usare una tabella hash
| Usala quando | Evitala quando |
|---|---|
Ti servono inserimento, ricerca ed eliminazione per chiave O(1) in media | Ti servono le chiavi in ordine: usa un BST bilanciato |
| Le chiavi non hanno un ordine utile e verifichi solo l'appartenenza esatta | Ti servono query su intervalli o ricerche della chiave più vicina |
| Puoi permetterti un po' di memoria extra per i bucket e un fattore di carico basso | La memoria è estremamente limitata e ogni byte conta |
| Esiste una buona funzione di hash per il tuo tipo di chiave | La latenza nel caso peggiore deve essere limitata: le collisioni la portano a O(n) |
Codice Hash Table
Un'implementazione di Hash Table pulita ed eseguibile in Python, JavaScript, Java, C++, C. Scegli un linguaggio, copia il codice o aprilo già caricato nel Playground di Coddy.
Codice Hash Table in Python
Python
1class HashTable:2 def __init__(self, size=8):3 self.size = size4 self.buckets = [[] for _ in range(size)]5
6 def _index(self, key):7 # Hash the key to a bucket; different keys can collide8 return sum(ord(ch) for ch in key) % self.size9
10 def set(self, key, value):11 bucket = self.buckets[self._index(key)]12 for i, (k, _) in enumerate(bucket):13 if k == key:14 bucket[i] = (key, value) # update existing key15 return16 bucket.append((key, value)) # chain on collision17
18 def get(self, key):19 for k, v in self.buckets[self._index(key)]:20 if k == key:21 return v22 raise KeyError(key)23
24 def delete(self, key):25 bucket = self.buckets[self._index(key)]26 for i, (k, _) in enumerate(bucket):27 if k == key:28 del bucket[i]29 return30 raise KeyError(key)31
32
33table = HashTable()34table.set("apple", 3)35table.set("banana", 7)36table.set("cherry", 5)37
38print("apple ->", table.get("apple"))39print("banana ->", table.get("banana"))40table.set("apple", 10)41print("apple ->", table.get("apple"))42table.delete("banana")43print("bucket sizes:", [len(b) for b in table.buckets])Codice Hash Table in JavaScript
JavaScript
1class HashTable {2 constructor(size = 8) {3 this.size = size;4 this.buckets = Array.from({ length: size }, () => []);5 }6
7 // Fold character codes into a bucket index8 hash(key) {9 let h = 0;10 for (const ch of key) h = (h * 31 + ch.charCodeAt(0)) % this.size;11 return h;12 }13
14 set(key, value) {15 const bucket = this.buckets[this.hash(key)];16 const pair = bucket.find(([k]) => k === key);17 if (pair) pair[1] = value;18 else bucket.push([key, value]); // Separate chaining on collision19 }20
21 get(key) {22 const bucket = this.buckets[this.hash(key)];23 const pair = bucket.find(([k]) => k === key);24 return pair ? pair[1] : undefined;25 }26
27 delete(key) {28 const bucket = this.buckets[this.hash(key)];29 const index = bucket.findIndex(([k]) => k === key);30 if (index === -1) return false;31 bucket.splice(index, 1);32 return true;33 }34}35
36const table = new HashTable();37table.set("apple", 3);38table.set("banana", 7);39table.set("cherry", 5);40table.set("apple", 4);41console.log("apple ->", table.get("apple"));42console.log("banana in bucket", table.hash("banana"));43table.delete("cherry");44console.log("cherry after delete:", table.get("cherry"));Codice Hash Table in Java
Java
1public class Main {2 static class Entry {3 String key; int value;4 Entry next; // chain for keys sharing a bucket5 Entry(String key, int value) { this.key = key; this.value = value; }6 }7
8 static final int CAPACITY = 8;9 static Entry[] buckets = new Entry[CAPACITY];10
11 static int index(String key) { return Math.abs(key.hashCode()) % CAPACITY; }12
13 static void put(String key, int value) {14 int i = index(key);15 for (Entry e = buckets[i]; e != null; e = e.next) {16 if (e.key.equals(key)) { e.value = value; return; }17 }18 Entry entry = new Entry(key, value);19 entry.next = buckets[i]; // prepend to the chain20 buckets[i] = entry;21 }22
23 static Integer get(String key) {24 for (Entry e = buckets[index(key)]; e != null; e = e.next) {25 if (e.key.equals(key)) return e.value;26 }27 return null;28 }29
30 static void remove(String key) {31 int i = index(key);32 Entry prev = null;33 for (Entry e = buckets[i]; e != null; prev = e, e = e.next) {34 if (e.key.equals(key)) {35 if (prev == null) buckets[i] = e.next;36 else prev.next = e.next;37 return;38 }39 }40 }41
42 public static void main(String[] args) {43 put("apple", 3); put("banana", 7); put("cherry", 5);44 System.out.println("apple -> " + get("apple"));45 put("apple", 10); // update in place46 System.out.println("apple -> " + get("apple"));47 remove("banana");48 System.out.println("banana -> " + get("banana"));49 }50}Codice Hash Table in C++
C++
1#include <iostream>2#include <string>3#include <vector>4
5struct HashTable {6 static constexpr int CAPACITY = 8;7 // Separate chaining: each bucket holds (key, value) pairs8 std::vector<std::vector<std::pair<std::string, int>>> buckets{CAPACITY};9
10 size_t hash(const std::string& key) const {11 size_t h = 0;12 for (char c : key) h = h * 31 + static_cast<unsigned char>(c);13 return h % CAPACITY;14 }15
16 void set(const std::string& key, int value) {17 auto& bucket = buckets[hash(key)];18 for (auto& entry : bucket) {19 if (entry.first == key) {20 entry.second = value; // update existing key21 return;22 }23 }24 bucket.push_back({key, value});25 }26
27 const int* get(const std::string& key) const {28 for (const auto& entry : buckets[hash(key)]) {29 if (entry.first == key) return &entry.second;30 }31 return nullptr;32 }33
34 void erase(const std::string& key) {35 auto& bucket = buckets[hash(key)];36 for (size_t i = 0; i < bucket.size(); ++i) {37 if (bucket[i].first == key) {38 bucket.erase(bucket.begin() + i);39 return;40 }41 }42 }43};44
45int main() {46 HashTable table;47 table.set("apple", 3);48 table.set("banana", 7);49 table.set("apple", 4); // overwrites the old value50 for (const std::string& key : {"apple", "banana", "grape"}) {51 const int* value = table.get(key);52 if (value != nullptr) std::cout << key << " = " << *value << "\n";53 else std::cout << key << " not found\n";54 }55 table.erase("banana");56 std::cout << "banana after erase: "57 << (table.get("banana") ? "found" : "not found") << "\n";58 return 0;59}Codice Hash Table in C
C
1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4
5#define CAPACITY 86
7// Separate chaining: each bucket is a linked list of entries8typedef struct Entry {9 char key[16];10 int value;11 struct Entry* next;12} Entry;13
14Entry* buckets[CAPACITY];15
16unsigned int hash(const char* key) {17 unsigned int h = 5381; // djb2, then modulo the bucket count18 for (; *key; key++) h = h * 33 + (unsigned char)*key;19 return h % CAPACITY;20}21
22void set(const char* key, int value) {23 unsigned int i = hash(key);24 for (Entry* e = buckets[i]; e != NULL; e = e->next) {25 if (strcmp(e->key, key) == 0) {26 e->value = value; // update existing key27 return;28 }29 }30 Entry* e = malloc(sizeof(Entry));31 strcpy(e->key, key);32 e->value = value;33 e->next = buckets[i];34 buckets[i] = e;35}36
37int* get(const char* key) {38 for (Entry* e = buckets[hash(key)]; e != NULL; e = e->next) {39 if (strcmp(e->key, key) == 0) return &e->value;40 }41 return NULL;42}43
44void removeKey(const char* key) {45 Entry** link = &buckets[hash(key)];46 while (*link != NULL) {47 if (strcmp((*link)->key, key) == 0) {48 Entry* old = *link;49 *link = old->next;50 free(old);51 return;52 }53 link = &(*link)->next;54 }55}56
57void printBuckets(void) {58 for (int i = 0; i < CAPACITY; i++) {59 printf("bucket %d:", i);60 for (Entry* e = buckets[i]; e != NULL; e = e->next) {61 printf(" (%s=%d)", e->key, e->value);62 }63 printf("\n");64 }65}66
67int main(void) {68 set("apple", 3);69 set("banana", 7);70 set("apple", 4); // overwrites the old value71 set("grape", 9);72 printBuckets();73 int* value = get("apple");74 printf("get(apple): %d\n", value ? *value : -1);75 removeKey("banana");76 printf("banana after remove: %s\n", get("banana") ? "found" : "not found");77 return 0;78}Domande frequenti sulla tabella hash
Cos'è una collisione di hash e come si risolve?
Una collisione avviene quando due chiavi diverse finiscono nello stesso bucket. Le due soluzioni comuni sono il concatenamento separato (ogni bucket contiene una lista e le chiavi in collisione vengono aggiunte, come mostrato qui) e l'indirizzamento aperto (cerca la prossima posizione vuota nell'array). Entrambe mantengono corrette le ricerche; cambiano l'organizzazione in memoria e le prestazioni sotto carico elevato.
Qual è la complessità temporale di una tabella hash?
Inserimento, ricerca ed eliminazione sono
O(1) in media quando la funzione di hash distribuisce le chiavi in modo uniforme e il fattore di carico resta basso. Nel caso peggiore, con tutte le chiavi in collisione in un unico bucket, degradano a O(n), ed è per questo che una buona funzione di hash e il ridimensionamento contano.Cos'è il fattore di carico?
Il fattore di carico è il numero di voci memorizzate diviso il numero di bucket. Quando cresce, le catene si allungano e le operazioni rallentano, quindi la maggior parte delle tabelle hash si ridimensiona (ricalcola l'hash in un array più grande) quando supera una soglia come 0,75.
Quando conviene usare una tabella hash invece di un albero binario di ricerca?
Usa una tabella hash quando ti servono solo ricerche per corrispondenza esatta e vuoi una velocità
O(1) in media senza requisiti di ordine. Usa un albero binario di ricerca bilanciato quando ti servono chiavi in ordine, query su intervalli o ricerche di predecessore/successore, che una tabella hash non gestisce in modo efficiente. Un BST garantisce operazioni O(log n), mentre una tabella hash rinuncia a questa garanzia in cambio di prestazioni medie migliori.Qual è la differenza tra concatenamento separato e indirizzamento aperto?
Il concatenamento separato memorizza le chiavi in collisione in una lista per ogni bucket, quindi un bucket può contenere molte voci e la tabella non si riempie mai davvero. L'indirizzamento aperto tiene tutto nell'array stesso e, in caso di collisione, cerca la prossima posizione libera: sfrutta bene la cache ma peggiora bruscamente quando il fattore di carico si avvicina a 1 e richiede una gestione attenta delle eliminazioni. Il concatenamento tollera fattori di carico più alti; l'indirizzamento aperto usa la memoria in modo più compatto.
Perché non posso contare su una tabella hash per mantenere le chiavi in ordine di inserimento o ordinate?
Una funzione di hash sparpaglia di proposito le chiavi tra i bucket per evitare raggruppamenti, quindi l'ordine di iterazione riflette la disposizione dei bucket, non l'ordine di inserimento né quello ordinato. Se ti serve un ordine, usa una mappa ordinata/un albero o una struttura come una mappa che conserva l'ordine di inserimento (ad es. il
dict di Python conserva l'ordine di inserimento, ma è una garanzia del linguaggio, non una proprietà intrinseca delle tabelle hash). Non dare mai per scontato che l'ordine di iterazione corrisponda a quello in cui hai inserito le chiavi, a meno che il linguaggio non lo prometta esplicitamente.Risorse correlate
Altre visualizzazioni
