File hash

Permettono un accesso diretto molto efficiente (da alcuni punti di vista)

La tecnica si basa su quella utilizzata per le tavole hash in memoria centrale

Tavola hash

Obiettivo: accesso diretto ad un insieme di record sulla base del valore di un campo (detto chiave, che per semplicità supponiamo identificante, ma non è necessario)

Se i possibili valori della chiave sono in numero paragonabile al numero di record (e corrispondono ad un “tipo indice”) allora usiamo un array (ad esempio: università con 1000 studenti e numeri di matricola compresi fra 1 e 1000 o poco più e file con tutti gli studenti)

Se i possibili valori della chiave sono molti di più di quelli effettivamente utilizzati, non possiamo usare l’array (spreco) (ad esempio: 40 studenti e numero di matricola di 6 cifre - un milione di possibili chiavi)

Volendo continuare ad usare qualcosa di simile ad un array, ma senza sprecare spazio, possiamo pensare di trasformare i valori della chiave in possibili indici di un array:

• funzione hash:
  • associa ad ogni valore della chiave un “indirizzo”, in uno spazio di dimensione paragonabile (leggermente superiore) rispetto a quello strettamente necessario
  • poichè il numero di possibili chiavi è molto maggiore del numero di possibili indirizzi (”lo spazio delle chiavi è più grande dello spazio degli indirizzi”), la funzione non può essere iniettiva e quindi esiste la possibilità di collisioni (chiavi diverse che corrispondono allo stesso indirizzo)
  • le buone funzioni hash distribuiscono in modo casuale e uniforme, riducendo le probabilità di collisione (che si riduce aumentando lo spazio ridondante)

Tavola hash, collisioni

Varie tecniche:

• posizioni successive disponibili
• tabella di overflow (gestita in forma collegata)
• funzioni hash “alternative”

Nota:

• le collisioni ci sono (quasi) sempre
• le collisioni multiple hanno probabilità che decresce al decrescere della molteplicità
• la molteplicità media delle collisioni è molto bassa

File hash

L’idea è la stessa della tavola hash, ma si basa sull’organizzazione in blocchi: