Problemi di collisione e come risolverli

7.1 Definizione delle collisioni in una hash table

Collisione in una hash table si verifica quando due chiavi diverse vengono hashate allo stesso indice di un array. Questo porta a più di un elemento che tenta di occupare la stessa cella nella hash table.

Esempio di collisione:

Supponiamo di avere una funzione hash semplice, che restituisce il resto della divisione della chiave per la dimensione della tabella. Per le chiavi 5 e 15 con dimensione della tabella 10, entrambe le chiavi daranno lo stesso indice: 5 % 10 = 5 e 15 % 10 = 5. Questo è una collisione.

Un altro esempio:

Supponi di creare un dizionario di nomi e hai una funzione hash semplice che restituisce la prima lettera del nome. Ma risulta che l'80% dei nomi inizia con la lettera "A". Questo non è solo una collisione, è un problema.

7.2 Metodi di risoluzione delle collisioni – chaining

Ci sono diversi metodi per risolvere le collisioni nelle hash table. I due metodi più comuni sono il chaining e l'open addressing.

Chaining

Vantaggi:

• Semplicità di implementazione.
• Efficienza con un numero ridotto di collisioni.
• Minore dipendenza dalla densità di riempimento della hash table.

Svantaggi:

• Richiede memoria aggiuntiva per i puntatori nella lista collegata.
• Le prestazioni possono diminuire con un gran numero di collisioni a causa di lunghe catene.

Esempio di implementazione del metodo chaining:

Puoi solo studiare la caratteristica della funzione insert, ma ho deciso di fornire il codice completo per comodità.

class HashTableChaining:
    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 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

    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 d'uso:
hash_table = HashTableChaining(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana"))  # Output: 2
hash_table.delete("banana")
print(hash_table.search("banana"))  # Output: None

7.3 Metodo numero due – open addressing

Il metodo dell'open addressing consiste nel cercare la prossima cella disponibile nell'array se si verifica una collisione. Ci sono diverse strategie per trovare una nuova cella: probing lineare, probing quadratico e doppio hashing.

Vantaggi:

• Non richiede memoria aggiuntiva per memorizzare i puntatori.
• Rappresentazione più compatta dei dati.

Svantaggi:

• Le prestazioni possono diminuire significativamente con un'elevata densità di riempimento della tabella.
• Richiede più risorse computazionali per risolvere le collisioni.

Esempi di strategie di open addressing

Probing lineare (Linear Probing):

• Probing con passo di 1: index = (index + 1) % size.
• Semplice, ma può portare a "clusterizzazione".

Probing quadratico (Quadratic Probing):

• Probing con passo crescente quadraticamente: index = (index + i^2) % size.
• Riduce il problema della clusterizzazione, ma è più complesso da implementare.

Doppio hashing (Double Hashing):

• Utilizzo di una seconda funzione hash per calcolare il passo: index = (index + i * hash2(key)) % size.
• Meno problemi di clusterizzazione, ma più complesso da implementare.

Esempio di implementazione del metodo dell'open addressing (probing lineare): Fornirò il codice completo funzionante, per semplicità puoi esaminare solo il lavoro della funzione insert

class HashTableOpenAddressing:
    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)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = (key, value)
                return
            index = (index + 1) % self.size
            if index == original_index:
                raise Exception("Hash table is full")
        self.table[index] = (key, value)

    def search(self, key):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = (index + 1) % self.size
            if index == original_index:
                break
        return None

    def delete(self, key):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = None
                return
            index = (index + 1) % self.size
            if index == original_index:
                break

# Esempio d'uso:
hash_table = HashTableOpenAddressing(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana"))  # Output: 2
hash_table.delete("banana")
print(hash_table.search("banana"))  # Output: None

7.4 Influenza delle collisioni su una hash table

Influenza delle collisioni sulle prestazioni.

Tempo medio di accesso:

• In condizioni ideali (senza collisioni) il tempo medio di accesso agli elementi in una hash table è O(1).
• Le collisioni aumentano il tempo di accesso, poiché è richiesta la gestione delle catene o il probing delle celle, aumentando il numero di operazioni.

Aumento della lunghezza delle catene:

• Nel metodo chaining, l'aumento della lunghezza delle catene con molte collisioni può portare a un tempo di accesso lineare O(n) per operazioni di ricerca, inserimento e cancellazione.
• Catene lunghe aumentano il numero di confronti necessari per cercare o inserire un elemento.

Complessità spaziale:

• Nel metodo chaining è richiesta memoria aggiuntiva per memorizzare i puntatori nelle liste collegate.
• Nel metodo dell'open addressing il riempimento della tabella oltre un certo livello (di solito intorno al 70-80%) aumenta significativamente il numero di collisioni e quindi il tempo di accesso.

Clusterizzazione: Nel metodo dell'open addressing (specialmente nel probing lineare) si verifica la clusterizzazione, quando diverse celle consecutive diventano occupate, aumentando la probabilità di collisioni e riducendo le prestazioni.

Esempio di analisi dell'influenza delle collisioni sulle prestazioni:

Questo è proprio per chi ama andare a fondo

import time
import random

# Probing lineare
class HashTableOpenAddressing:
    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)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = (key, value)
                return
            index = (index + 1) % self.size
            if index == original_index:
                raise Exception("Hash table is full")
        self.table[index] = (key, value)

    def search(self, key):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = (index + 1) % self.size
            if index == original_index:
                break
        return None

# Generazione di una grande quantità di dati per l'inserimento
hash_table = HashTableOpenAddressing(1000)
keys = [random.randint(1, 10000) for _ in range(800)]

# Inserimento dati e misurazione del tempo
start_time = time.time()
for key in keys:
    hash_table.insert(key, key)
print(f"Tempo di inserimento: {time.time() - start_time:.6f} secondi")

# Ricerca dati e misurazione del tempo
start_time = time.time()
for key in keys:
    hash_table.search(key)
print(f"Tempo di ricerca: {time.time() - start_time:.6f} secondi")