Newsgroup: it.comp.lang.pascal
Titolo: [OT] Tabelle Hash

Ciao a tutti,
sento spesso parlare di tabelle hash ma sinceramente non ho idea di cosa
siano.
Qcuno potrebbe darmi qualke idea o magari un link a qualke sito ke ne parla?
Grazie
--
DArK
===============================
        ThE DArKneSS Is JuST DArK
===============================
per rispondermi togli le mutande

 siano.
Le tabelle hash sono delle strutture dati particolari, basate
sull'associazione chiave/valore.
Cioe', partendo da una chiave (generalmente alfanumerica) si arriva alla sua
posizione all'interno di un vettore ed e' quindi facile recuperare il valore
associato.
Esempio, io potrei avere una chiave rappresentata dal nome di una citta' e
un valore rappresentato dal numero di abitanti.
Supponendo di scrivere una funzione hash di trasformazione della chiave del
genere:
var
  HashTable: array [0..8191] of Integer;
function Hash(K: String): Integer;
var
  I: Integer;
  C: Integer;
begin
  C := 0;
  for I := 1 to Length(K) do
  begin
    C := C + Ord(K[I]);
  end;
  C := C mod 8192;
  Hash := C;
end;
begin
  HashTable[Hash('New York')] := 20000000;
  HashTable[Hash('Tokyo')] := 10000000;
  HashTable[Hash('Parigi')] := 8000000;
  WriteLn('New York: ',HashTable[Hash('New York')]);
  WriteLn('Tokyo: ', HashTable[Hash('Tokyo')]);
  WriteLn('Parigi: ', HashTable[Hash('Parigi')]);
  ReadLn;
end.
Ovviamente, bisogna stare attenti alle cosiddette "collisioni", ovvero a
considerare che due chiavi distinte potrebbe avere lo stesso valore
derivante dalla hash function.
E' per questo motivo che, generalmente, le hash table contengono, come
elementi, delle liste di valori, ciascuno con la chiave memorizzata, in modo
da poter scorrere la lista e trovare il valore relativo alla chiave cercata,
nel caso essa collida con altre.
--------------------------------
Inviato via 
http://usenet.libero.it

 Grazie
Le informazioni sull'Hashing sono rare, chi ha grandi informazioni
sull'argomento può fare soldi a palate.
Ho tentato più volte di cercare info sull'argomento anche in Inglese, ma
sembra quasi impossibile.
Comunque di base è questo:
Premetto che la tecnica Hash è utilizzata sia per la gestione degli archivi,
sia per tematiche riguardanti la sicurezza.
Parlando della gestione degli archivi, la tecnica Hash serve a raggiungere
un record, in maniera associativa e diretta, questo viene reso possibile
tramite alcuni accorgimenti.
Innanzitutto mettendo di volere implementare un Archivio e di volerlo
gestire con Hash, la prima cosa è stabilire che dimensione avrà il proprio
archivio (E questa è la prima fregatura di Hash)
In pratica per realizzare la tecnica Hash, bisogna a priori sapere la
dimensione massima del nostro archivio, altrimenti la tecnica non può essere
implementata.
Supponendo di sapere la dimensione, e suppenendo che questa sia N
Bisogna creare un archivio vuoto con N posti.
Mettiamo adesso che vogliamo inserire un elemento/record nell'archivio,
bisogna scegliere la posizione dove inserire questo record, ebbene quà c'è
il vantaggio della tecnica Hash. La posizione dove inserire il record viene
trovata attraverso una funzione chiamata funzione HASH, questa funzione deve
creare un indirizzo compreso tra 1 e N, associato ad una chiave del record
da trattare.
Come viene realizzata la funzione Hash, è la parte fondamentale. Migliore è
la funzione HASH e maggiori saranno i vantaggi, purtroppo è dimostrato che i
problemi cominciano a sorgere al crescere della dimensione N dell'archivio,
infatti per N molto piccola è anche possibile realizzare il così detto Hash
Perfetto, ma per N grande questo non è possibile e quindi si ha il fenomeno
delle collisioni.
IL fenomeno delle collisioni consiste nel fatto che alcune chiavi tramite la
funzione HASH restituiscono lo stesso indirizzo, questo non dovrebbe
accadere spesso, ma può accadere al riempimento dell'archivio.
Le collisioni sono complicate da gestire, comunque il vantaggio poi è come
si può capire nella ricerca, che è immediata anche con archivi enormi, salvo
poi collisioni.
IL sistema migliore per gestire le collisioni è quello delle HASH multiple,
ovvero si crea una tabella N principale, poi si creano M tabelle di N per le
collisioni da calcolarsi con percentuali, come avviene per le Cache a
livelli.

ho trovato questo link che apiega bene:
http://www.di.unipi.it/~andrea/Didattica/Spezia-00/Dispensa/node46.html
--
Max Etere
massimili...@programmando.org
http://www.programmando.org