Concetto di funzione hash

5.1 Definizione di funzione hash e il suo utilizzo

Funzione hash — è una funzione che accetta dati di input (o chiave) e restituisce una dimensione fissa di bit, solitamente chiamata hash o valore hash. Lo scopo principale di una funzione hash è distribuire efficacemente i dati su una tabella hash per garantire un accesso rapido agli elementi.

Utilizzo:

• Tabelle hash: Utilizzate per implementare array associativi (dizionari in Python), garantendo un accesso rapido ai dati tramite chiave.
• Controllo dell'integrità dei dati: Le funzioni hash vengono utilizzate per verificare l'integrità dei file e dei dati (ad esempio, algoritmi MD5, SHA-1, SHA-256).
• Crittografia: Le funzioni hash sono utilizzate in algoritmi crittografici per la cifratura e la creazione di firme digitali.
• Motori di ricerca: Utilizzate per l'indicizzazione dei dati e la ricerca rapida delle informazioni.
• Gestione della cache: Usate per organizzare le cache, per trovare rapidamente i dati.

Esempio di utilizzo di una funzione hash in Python:

# Esempio di utilizzo di una funzione hash in Python per una tabella hash (dizionario)
data = {"apple": 1, "banana": 2, "cherry": 3}

# Ottenere il valore hash della chiave
key = "banana"
hash_value = hash(key)

print(f"Valore hash per la chiave '{key}': {hash_value}")

5.2 Analoghe nella vita reale

Con una funzione hash puoi suddividere un grande gruppo di oggetti in gruppi approssimativamente uguali. Inoltre, se continui ad aggiungere nuovi oggetti, continueranno a distribuirsi uniformemente nei gruppi.

Supponiamo di avere 1000 persone e di doverle suddividere in 30 gruppi. Ecco come si può fare.

Metodo 1. In base alla prima lettera del nome.

Il primo gruppo è formato da tutti coloro il cui nome inizia con "A", il secondo gruppo da tutti quelli il cui nome inizia con "B", e così via. La regola "Il tuo gruppo è la prima lettera del tuo nome" è una funzione hash. Ma con una funzione hash del genere rischiamo di avere molte persone nel gruppo "A" e poche in "Z".

Metodo 2. In base alla data di nascita.

Nati il primo giorno di qualsiasi mese — primo gruppo, il secondo giorno — secondo gruppo, e così via. Ci saranno 31 gruppi. Nel 31° gruppo ci saranno circa la metà delle persone rispetto agli altri gruppi, ma le persone in tali gruppi saranno distribuite in modo molto più uniforme che nel primo caso.

Metodo 3. Numero di telefono

La soluzione ideale è ottenere un numero che sia, da un lato, il più casuale possibile (in modo che tali numeri siano distribuiti uniformemente), e dall'altro dovrebbe sempre essere calcolato rapidamente ed essere lo stesso.

Prendiamo le 4 cifre finali del numero di telefono - ci saranno 10.000 varianti. Quindi dividiamo questo numero interamente per 30. Allora avremo 30 possibili resti dalla divisione: 0, 1, 2, ..., 29. Questi saranno i numeri dei nostri gruppi.

Utile! A proposito, quasi ogni funzione hash utilizza il resto della divisione interamente — è molto semplice e consente di regolare il numero di gruppi in cui suddividere gli elementi.

5.3 Proprietà principali di una funzione hash

Le proprietà principali di una buona funzione hash:

Determinismo: La stessa funzione hash deve sempre restituire lo stesso valore hash per lo stesso valore di input.

Esempio:

key = "example"
assert hash(key) == hash(key)

Importante! L'operatore assert verifica che l'espressione alla sua destra sia True. Se l'espressione non è vera False, verrà sollevata un'eccezione.

Uniformità: Una buona funzione hash dovrebbe distribuire uniformemente i valori su tutto il range dei possibili valori hash, per evitare collisioni.

Esempio dalla vita di uno sviluppatore Python: Nel dizionario (classe dict) di Python, la funzione hash hash() distribuisce chiavi uniformemente.

Efficienza di calcolo: La funzione hash dovrebbe essere veloce ed efficiente, per non rallentare le operazioni di inserimento e ricerca.

Esempio dalla vita di uno sviluppatore Python: Le funzioni hash standard in Python sono implementate per funzionare con chiavi di diversi tipi, come stringhe e numeri.

Minimizzazione delle collisioni: Una collisione si verifica quando due chiavi diverse hanno lo stesso valore hash. Una buona funzione hash dovrebbe minimizzare la probabilità di collisioni.

Esempio dalla vita di uno sviluppatore Python: L'algoritmo SHA-256 minimizza la probabilità di collisioni durante l'hashing dei dati.

Distribuzione degli hash: Per grandi quantità di dati la funzione hash deve garantire una distribuzione uniforme dei valori hash su tutta la tabella hash.

Esempio dalla vita di uno sviluppatore Python: Le funzioni hash standard in Python gestiscono bene la distribuzione delle chiavi nelle tabelle hash.

5.4 Esempi di funzioni hash e la loro implementazione

Le funzioni hash prendono in input dati di dimensioni arbitrarie e restituiscono un valore hash di dimensione fissa. Vediamo alcuni esempi di funzioni hash e la loro implementazione.

Esempio 1: Funzione hash semplice per stringhe

Una delle funzioni hash più semplici per le stringhe può essere implementata utilizzando la somma dei codici dei caratteri della stringa:

def simple_hash(key):
    hash_value = 0
    for char in key:
        hash_value += ord(char)
    return hash_value % 1000  # Supponiamo che la nostra tabella abbia dimensione 1000

# Esempio di utilizzo:
key = "example"
print(f"Valore hash per la chiave '{key}': {simple_hash(key)}")

Esempio 2: Funzione hash per stringhe utilizzando hashing polinomiale

L'hashing polinomiale è una tecnica più complessa ma efficace:

def polynomial_hash(key, a=33, m=1000):
    hash_value = 0
    for char in key:
        hash_value = (hash_value * a + ord(char)) % m
    return hash_value

# Esempio di utilizzo:
key = "example"
print(f"Valore hash per la chiave '{key}': {polynomial_hash(key)}")

Esempio 3: Funzione hash integrata in Python

Python offre una funzione integrata hash() per ottenere il valore hash di vari tipi di dati:

key = "example"
print(f"Valore hash per la chiave '{key}': {hash(key)}")

Esempio 4: Funzione hash crittografica (SHA-256)

Le funzioni hash crittografiche, come SHA-256, sono utilizzate per garantire la sicurezza dei dati:

import hashlib

def sha256_hash(key):
    return hashlib.sha256(key.encode()).hexdigest()

# Esempio di utilizzo:
key = "example"
print(f"Valore hash per la chiave '{key}': {sha256_hash(key)}")

5.5 Introduzione all'hashing e il suo utilizzo

Hashing — è il processo di conversione dei dati di input di dimensioni arbitrarie in un valore hash di dimensione fissa utilizzando una funzione hash. L'hashing è ampiamente utilizzato nelle scienze informatiche e nella programmazione per l'ottimizzazione e la sicurezza.

Principali applicazioni dell'hashing:

1. Tabelle hash (dizionari): Le tabelle hash utilizzano funzioni hash per organizzare e accedere rapidamente ai dati.

data = {"apple": 1, "banana": 2, "cherry": 3}
key = "banana"
hash_value = hash(key)
print(f"Valore hash per la chiave '{key}': {hash_value}")

2. Controllo dell'integrità dei dati: Le funzioni hash sono utilizzate per verificare l'integrità dei file e dei dati.

Esempio: Verifica dell'integrità del file utilizzando SHA-256:

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()

file_hash = get_file_hash('example.txt')
print(f"Hash SHA-256 del file: {file_hash}")

3. Crittografia e sicurezza: Le funzioni hash sono utilizzate per creare primitivi crittografici, come firme digitali e hash delle password.

Esempio: Hashing di una password utilizzando SHA-256:

import hashlib

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

password = "securepassword"
hashed_password = hash_password(password)
print(f"Hash della password: {hashed_password}")

4. Motori di ricerca e indicizzazione: L'hashing è utilizzato per creare indici e cercare rapidamente i dati.

Esempio: Creazione di un indice per la ricerca testuale:

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

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

5. Gestione della cache: L'hashing è usato per organizzare le cache, per trovare rapidamente i dati.

Esempio: Cache semplice usando una funzione hash:

cache = {}

def get_from_cache(key):
    hash_key = hash(key)
    return cache.get(hash_key, None)

def add_to_cache(key, value):
    hash_key = hash(key)
    cache[hash_key] = value

# Aggiunta e recupero dei dati dalla cache
add_to_cache("test_key", "test_value")
print(get_from_cache("test_key"))  # Output: test_value