6.1 Definizione e struttura di una hash table
Hash table – è una struttura dati che fornisce la possibilità di cercare, inserire ed eliminare elementi rapidamente utilizzando una hash function per calcolare gli indici in un array o lista. Le hash table sono generalmente utilizzate per implementare array associativi, noti anche come dizionari.
Aspetti importanti delle hash table
Array – è il componente principale della hash table, memorizza i puntatori agli elementi o alle liste di elementi.
Hash function: Funzione che trasforma le chiavi del dizionario in indici dell'array.
Collisioni: Situazione in cui due chiavi diverse hanno lo stesso hash value. Per risolvere le collisioni si utilizzano vari metodi, come il chaining o l'open addressing.
Esempio di dizionario:
{
"apple": 101,
"banana": 102,
"cherry": 103
}
Esempio di struttura di una hash table:
| Indice | Valore |
|---|---|
| 0 | None |
| 1 | [('apple', 101)] |
| 2 | None |
| 3 | [('banana', 102)] |
| 4 | None |
| 5 | None |
| 6 | None |
| 7 | [('cherry', 103)] |
| 8 | None |
| 9 | None |
6.2 Operazioni principali in una hash table
Operazioni principali in una hash table: inserimento, ricerca, eliminazione
1. Inserimento (Insertion): Processo di aggiunta di un nuovo elemento (coppia chiave-valore) nella hash table.
Passaggi dell'inserimento:
- Calcolare l'hash value della chiave utilizzando la hash function.
- Trovare l'indice nell'array basato sull'hash value.
- Se nell'array a questo indice c'è già un elemento (collisione), aggiungere l'elemento alla lista (nel caso di chaining) o trovare l'indice successivo disponibile (nel caso di open addressing).
Esempio di inserimento in una hash table utilizzando il chaining:
class HashTable:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
if self.table[index] is None:
self.table[index] = [(key, value)]
else:
for i, kv in enumerate(self.table[index]):
k, v = kv
if k == key:
self.table[index][i] = (key, value)
return
self.table[index].append((key, value))
# Esempio di utilizzo:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)
2. Ricerca (Search): Processo per trovare il valore per una data chiave in una hash table.
Passaggi della ricerca:
- Calcolare l'hash value della chiave utilizzando la hash function.
- Trovare l'indice nell'array basato sull'hash value.
- Verificare la presenza della chiave nella lista di elementi (nel caso di chaining) o all'indice (nel caso di open addressing).
Esempio di ricerca in una hash table utilizzando il chaining:
class HashTable:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def search(self, key):
index = self.hash_function(key)
if self.table[index] is None:
return None
for k, v in self.table[index]:
if k == key:
return v
return None
# Esempio di utilizzo:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana")) # Output: 2
print(hash_table.search("grape")) # Output: None
3. Eliminazione (Deletion): Processo di rimozione di un elemento (coppia chiave-valore) dalla hash table.
Passaggi dell'eliminazione:
- Calcolare l'hash value della chiave utilizzando la hash function.
- Trovare l'indice nell'array basato sull'hash value.
- Rimuovere l'elemento dalla lista (nel caso di chaining) o impostare il valore all'indice su
None(nel caso di open addressing).
Esempio di eliminazione da una hash table utilizzando il chaining:
class HashTable:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
if self.table[index] is None:
self.table[index] = [(key, value)]
else:
for i, kv in enumerate(self.table[index]):
k, v = kv
if k == key:
self.table[index][i] = (key, value)
return
self.table[index].append((key, value))
def delete(self, key):
index = self.hash_function(key)
if self.table[index] is None:
return
for i, kv in enumerate(self.table[index]):
k, v = kv
if k == key:
del self.table[index][i]
return
# Esempio di utilizzo:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)
hash_table.delete("banana")
print(hash_table.table)
print(hash_table.search("banana")) # Output: None
6.3 Complessità temporale della hash table
Complessità temporale delle operazioni in una hash table
Inserimento (Insertion):
- Caso medio:
O(1) - Caso peggiore:
O(n)(in caso di un gran numero di collisioni o se tutti gli elementi finiscono nella stessa posizione)
Ricerca (Search):
- Caso medio:
O(1) - Caso peggiore:
O(n)(in caso di un gran numero di collisioni o se tutti gli elementi finiscono nella stessa posizione)
Eliminazione (Deletion):
- Caso medio:
O(1) - Caso peggiore:
O(n)(in caso di un gran numero di collisioni o se tutti gli elementi finiscono nella stessa posizione)
Spiegazione:
Caso medio: Nel caso medio, la hash function distribuisce uniformemente gli elementi nella tabella, e ogni elemento si trova nella propria cella unica, garantendo un tempo di accesso costante O(1).
Caso peggiore: Nel caso peggiore, tutti gli elementi finiscono in una stessa cella a causa di una cattiva hash function o di un gran numero di collisioni. Quindi la hash table si trasforma in una lista collegata e la complessità temporale delle operazioni diventa O(n).
6.4 Esempi di utilizzo delle hash table
1. Implementazione di un dizionario (array associativo)
Le hash table vengono spesso utilizzate per implementare dizionari, che permettono di memorizzare coppie chiave-valore e forniscono un accesso rapido tramite chiave.
Esempio:
# Creazione di un dizionario
dictionary = {}
# Inserimento di elementi
dictionary["apple"] = 1
dictionary["banana"] = 2
dictionary["cherry"] = 3
# Ricerca di un elemento
print(dictionary["banana"]) # Output: 2
# Eliminazione di un elemento
del dictionary["cherry"]
# Verifica dell'esistenza di una chiave
if "apple" in dictionary:
print("La chiave 'apple' esiste nel dizionario") # Output: La chiave 'apple' esiste nel dizionario
Ora sai un po' di più sul dizionario in Python e su come è strutturato.
2. Caching dei risultati di calcoli
Le hash table vengono utilizzate per memorizzare in cache i risultati di calcoli costosi per accelerare le richieste successive.
Esempio:
# Cache per memorizzare i risultati
cache = {}
def expensive_computation(x):
if x in cache:
return cache[x]
result = x * x # Esempio di calcolo costoso
cache[x] = result
return result
# Utilizzo della cache
print(expensive_computation(10)) # Output: 100 (calcolo e caching)
print(expensive_computation(10)) # Output: 100 (da cache)
3. Conteggio della frequenza delle parole in un testo
Le hash table vengono utilizzate per contare il numero di occorrenze di ogni parola in un testo.
Esempio:
from collections import defaultdict
text = "this is a simple text with some simple words this is simple"
word_count = defaultdict(int)
for word in text.split():
word_count[word] += 1
# Output dei risultati
for word, count in word_count.items():
print(f"La parola '{word}' appare {count} volte")
4. Ricerca di duplicati in una lista
Le hash table vengono utilizzate per cercare efficacemente i duplicati in una lista.
def find_duplicates(arr):
seen = set()
duplicates = []
for item in arr:
if item in seen:
duplicates.append(item)
else:
seen.add(item)
return duplicates
# Esempio di utilizzo
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr)) # Output: [2, 4]
GO TO FULL VERSION