Hashing e tabelle hash domande

Che cos'è una funzione di hashing?

Una funzione di hashing è un algoritmo che trasforma un input di qualsiasi dimensione in un output di lunghezza fissa, chiamato hash.

Vero o falso: le funzioni di hashing sono sempre uniche.

Falso. Le funzioni di hashing possono generare lo stesso hash per input diversi, noti come collisioni.

Qual è l'obiettivo principale del hashing?

L'obiettivo principale è garantire l'integrità e la rapida accessibilità dei dati.

Complete: una buona funzione di hashing deve essere ______.

Deterministica, veloce, resistente alle collisioni e distribuita uniformemente.

Differenza tra hashing e cifratura.

- Hashing: irreversibile, lunghezza fissa. - Cifratura: reversibile, varia in base ai dati.

Esempio di funzione di hashing semplice.

Una funzione di hashing semplice è la somma dei valori ASCII dei caratteri di una stringa, modulo la dimensione della tabella.

Quali sono gli usi comuni delle funzioni di hashing?

- Verifica dell'integrità dei dati. - Archiviazione di password. - Creazione di identificatori unici.

Che cos'è un valore hash?

Un valore hash è l'output prodotto da una funzione di hashing, rappresenta l'input in forma compressa.

Vero o falso: il hashing è sempre sicuro.

Falso. Alcune funzioni di hashing possono essere vulnerabili a attacchi come la pre-image attack.

Causa → effetto di un hash debole.

Causa: Funzione di hashing non sicura. Effetto: Maggiore probabilità di collisioni e attacchi.

Cos'è un messaggio digest?

Un messaggio digest è un valore hash che rappresenta un insieme di dati, utilizzato per garantire integrità.

Qual è la differenza tra hash e checksum?

- Hash: utilizzato per l'integrità. - Checksum: verifica degli errori di trasmissione.

Cosa sono le tabelle hash?

Strutture dati che mappano chiavi a valori. Permettono accesso rapido ai dati.

Vantaggi delle tabelle hash?

- Accesso in tempo costante - Buona gestione della memoria - Efficiente per ricerche

Come si crea una tabella hash?

Si definisce una funzione di hashing, si alloca un array e si inseriscono chiavi tramite la funzione.

Cosa è una funzione di hashing?

Funzione che trasforma una chiave in un indice nella tabella hash.

Vero o falso: Le tabelle hash sempre gestiscono collisioni.

Vero, le collisioni devono essere gestite con metodi come chaining o open addressing.

Esempio di inserimento in una tabella hash.

Chiave: 23 Funzione di hashing: $\displaystyle h(k) = k \bmod 10$ Indice: $\displaystyle h(23) = 3$

Cosa significa 'carico' in riferimento alle tabelle hash?

Rapporto tra elementi e dimensione della tabella. Un carico alto aumenta collisioni.

Cosa determina la dimensione di una tabella hash?

La dimensione deve essere un numero primo per ridurre le collisioni e migliorare la distribuzione.

Qual è il problema del clustering?

Fenomeno dove le collisioni si concentrano in aree vicine della tabella, peggiorando le prestazioni.

Cosa sono le collisioni?

Occorrono quando due chiavi diverse producono lo stesso indice in una tabella hash.

Confronta chaining e open addressing.

Chaining: usa liste collegate per gestire collisioni. Open addressing: cerca il prossimo slot libero.

Cosa è una tabella hash dinamica?

Tabella che può espandersi o contrarsi in base al numero di elementi, riducendo il carico.

Cosa sono le collisioni in hashing?

Le collisioni si verificano quando due chiavi diverse producono lo stesso valore di hash.

Vero o falso: le collisioni possono essere evitate completamente.

Falso. Non è possibile evitare completamente le collisioni a causa del principio del pigeonhole.

Qual è l'effetto di una collisione?

Le collisioni possono ridurre l'efficienza della ricerca e causare problemi di accesso ai dati.

Quali sono i metodi di risoluzione delle collisioni?

- Chaining - Open Addressing - Double Hashing - Linear Probing

Chaining vs Open Addressing: differenza principale?

Chaining usa liste collegate per gestire le collisioni, mentre Open Addressing cerca spazi liberi nella stessa tabella.

Cosa implica il Linear Probing?

Nel Linear Probing, si cerca la prossima posizione libera sequenzialmente nella tabella hash.

Cosa rappresenta la funzione di hash?

La funzione di hash mappa una chiave a un indice nella tabella hash, idealmente unico.

Quando è efficace il Double Hashing?

Il Double Hashing è efficace quando si desidera una distribuzione più uniforme delle chiavi e ridurre le collisioni.

Qual è un esempio di collisione?

Se la funzione di hash mappa 'ciao' e 'oic' a 5, c'è una collisione.

Qual è il problema principale delle collisioni?

Aumentano il tempo di accesso ai dati e complicano la gestione della tabella hash.

Cosa si deve considerare nella scelta della funzione di hash?

La funzione deve avere una buona distribuzione delle chiavi e una bassa probabilità di collisione.

Cosa è la risoluzione delle collisioni?

È il processo di gestire le collisioni per garantire l'integrità e l'accesso ai dati nella tabella hash.

Applicazione del hashing in database?

Il hashing è utilizzato per velocizzare le ricerche nei database, riducendo il tempo di accesso ai dati.

Vero o falso: il hashing è usato solo per la sicurezza?

Falso. Il hashing è anche per indicizzazione, gestione della memoria e deduplicazione.

Come si usa il hashing nelle password?

Le password vengono hashate per memorizzare solo il valore hash, non la password in chiaro.

Cosa è una tabella hash?

Una struttura dati che utilizza funzioni di hashing per mappare chiavi a valori in modo efficiente.

Esempio di utilizzo del hashing in file?

Il hashing aiuta a verificare l'integrità dei file, ad esempio usando checksum.

Hashing e caching: perché sono correlati?

Il caching usa il hashing per memorizzare risultati di operazioni costose e velocizzare l'accesso.

Compara hashing e crittografia.

- Hashing: non reversibile - Crittografia: reversibile - Entrambi per la sicurezza.

Quale applicazione del hashing nei sistemi distribuiti?

Il hashing distribuito è usato per bilanciare il carico tra nodi in architetture di rete.

Hashing nelle strutture dati: cosa migliora?

Migliora l'efficienza della ricerca, inserimento e cancellazione di elementi.

Con quale algoritmo si usano le tabelle hash?

Algoritmi come SHA-256 o MD5 sono comunemente usati per generare valori hash.

Qual è l'effetto del hashing sulla deduplicazione?

Consente di identificare e rimuovere file duplicati confrontando valori hash.

Hashing in blockchain: perché è fondamentale?

Garantisce l'integrità e la sequenza delle transazioni in un registro distribuito.