Funzioni di hash e il loro utilizzo

10.1 Introduzione alle funzioni di hash e tabelle di hash

Andiamo a rivedere e approfondire la nostra comprensione delle funzioni di hash e delle tabelle di hash. Una funzione di hash è un algoritmo che trasforma input di lunghezza arbitraria in una stringa di lunghezza fissa. Le caratteristiche principali delle funzioni di hash sono:

• Determinismo: lo stesso input dà sempre lo stesso risultato.
• Calcolo veloce: l'hash deve essere calcolato rapidamente.
• Irreversibilità (per le funzioni di hash crittografiche): dall'hash è impossibile (o molto difficile) ricostruire i dati originali.
• Distribuzione uniforme: piccoli cambiamenti nei dati di input portano a cambiamenti significativi nell'hash.

In parole povere, questa funzione ha lo stesso valore per gli stessi oggetti, ma se la funzione di hash di due oggetti è la stessa, questi oggetti non sono necessariamente uguali. In matematica questo è chiamato condizione necessaria ma non sufficiente.

Una tabella di hash è una struttura dati che utilizza una funzione di hash per memorizzare e cercare efficacemente informazioni. Consiste di:

• Un array di "bucket" per memorizzare i dati.
• Una funzione di hash che determina in quale bucket mettere i dati.

Le tabelle di hash forniscono un accesso rapido ai dati, di solito con complessità O(1) nel caso medio.

Uso delle funzioni di hash nella vita reale

Esempio: Tecnologie Blockchain

Nella blockchain le funzioni di hash sono utilizzate per creare identificatori unici per i blocchi e garantire l'integrità dei dati. Ogni blocco contiene l'hash del blocco precedente, creando una catena e rendendo il sistema resistente ai cambiamenti.

import hashlib
import time

class Block:
    def __init__(self, data, previous_hash):
        self.timestamp = time.time()
        self.data = data
        self.previous_hash = previous_hash
        self.hash = self.calculate_hash()

    def calculate_hash(self):
        hash_string = str(self.timestamp) + str(self.data) + str(self.previous_hash)
        return hashlib.sha256(hash_string.encode()).hexdigest()

# Esempio di utilizzo
block1 = Block("Transazione 1", "0")
block2 = Block("Transazione 2", block1.hash)
print(f"Hash del blocco 1: {block1.hash}")
print(f"Hash del blocco 2: {block2.hash}")

Confronto delle prestazioni

Considera il problema di trovare i duplicati in un array. Confrontiamo la soluzione usando una tabella di hash e senza di essa:

import time

def find_duplicates_with_hash(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

def find_duplicates_without_hash(arr):
    duplicates = []
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] == arr[j] and arr[i] not in duplicates:
                duplicates.append(arr[i])
    return duplicates

# Test delle prestazioni
arr = list(range(10000)) + list(range(5000))  # Array con duplicati

start = time.time()
find_duplicates_with_hash(arr)
end = time.time()
print(f"Tempo di esecuzione con tabella di hash: {end - start} secondi")

start = time.time()
find_duplicates_without_hash(arr)
end = time.time()
print(f"Tempo di esecuzione senza tabella di hash: {end - start} secondi")

Esegui il programma e verifica quanto l'uso della tabella di hash accelera la ricerca dei duplicati. Soprattutto su grandi insiemi di dati.

10.2 Esempi di utilizzo delle funzioni di hash in problemi reali

1. Hashing delle password

Le funzioni di hash sono utilizzate per memorizzare in modo sicuro le password. Invece di memorizzare le password in chiaro, i sistemi memorizzano i loro hash. Quando un utente inserisce una password, il sistema ne calcola l'hash e lo confronta con quello memorizzato nel database.

Esempio di implementazione:

import hashlib

def hash_password(password):
    return hashlib.sha256(password.encode()).hexdigest()

# Esempio di utilizzo:
password = "securepassword"
hashed_password = hash_password(password)
print(f"Hash della password: {hashed_password}")

2. Controllo dell'integrità dei dati

Le funzioni di hash sono utilizzate per verificare l'integrità dei file e dei dati. Ad esempio, per verificare se un file è stato modificato o danneggiato durante la trasmissione.

Esempio di implementazione:

import hashlib

def get_file_hash(file_path):
    hasher = hashlib.sha256()
    with open(file_path, 'rb') as file:
        buf = file.read()
        hasher.update(buf)
    return hasher.hexdigest()

# Esempio di utilizzo:
file_hash = get_file_hash('example.txt')
print(f"SHA-256 hash del file: {file_hash}")

3. Motori di ricerca e indicizzazione

I motori di ricerca utilizzano funzioni di hash per creare indici e cercare informazioni rapidamente. Ogni documento è indicizzato per parole chiave e le funzioni di hash aiutano a trovare rapidamente i documenti contenenti determinate parole.

Esempio di implementazione:

def create_index(text):
    index = {}
    words = text.split()
    for word in words:
        word_hash = hash(word)
        if word_hash not in index:
            index[word_hash] = []
        index[word_hash].append(word)
    return index

# Esempio di utilizzo:
text = "This is an example text for indexing"
index = create_index(text)
print(f"Indice: {index}")

10.3 Ottimizzazione della ricerca con funzioni di hash

1. Uso delle tabelle di hash per trovare duplicati

Le tabelle di hash permettono di trovare rapidamente i duplicati in un array, confrontando i valori di hash degli elementi.

Esempio di implementazione:

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]

2. Ottimizzazione della ricerca di coppie con una somma specificata

Le tabelle di hash permettono di trovare in modo efficiente coppie di numeri in un array la cui somma è uguale ad un valore dato.

Esempio di implementazione:

def find_pairs_with_sum(arr, target_sum):
    seen = set()
    pairs = []

    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((complement, num))
        seen.add(num)

    return pairs

# Esempio di utilizzo:
arr = [2, 4, 3, 7, 8, -2, 10, -1]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # Output: [(4, 2), (8, -2)]

10.4 Esempi di utilizzo delle funzioni di hash in vari algoritmi

1. Conteggio delle parole in un testo

Usa una tabella di hash per contare il numero di occorrenze di ogni parola in un testo.

Esempio di implementazione:

def count_words(text):
    word_count = {}
    words = text.split()

    for word in words:
        if word in word_count:
            word_count[word] += 1
        else:
            word_count[word] = 1

    return word_count

# Esempio di utilizzo:
text = "this is a test this is only a test"
print(count_words(text))  # Output: {'this': 2, 'is': 2, 'a': 2, 'test': 2, 'only': 1}

2. Verifica di intersezione tra due array

Controlla se due array si intersecano (hanno almeno un elemento in comune).

Esempio di implementazione:

def has_intersection(arr1, arr2):
    set1 = set(arr1)
    for item in arr2:
        if item in set1:
            return True
    return False

# Esempio di utilizzo:
arr1 = [1, 2, 3, 4]
arr2 = [3, 5, 6, 7]
arr3 = [8, 9, 10]
print(has_intersection(arr1, arr2))  # Output: True
print(has_intersection(arr1, arr3))  # Output: False

3. Controllo dell'unicità degli elementi in un array

Verifica se un array contiene solo elementi unici.

Esempio di implementazione:

def all_unique(arr):
    seen = set()
    for item in arr:
        if item in seen:
            return False
        seen.add(item)
    return True

# Esempio di utilizzo:
arr1 = [1, 2, 3, 4, 5]
arr2 = [1, 2, 3, 4, 5, 3]
print(all_unique(arr1))  # Output: True
print(all_unique(arr2))  # Output: False