[SERALE] - Quicksort
Clicca QUI per vedere il messaggio nel forum |
| xSharKMaNx |
Ciao ragazzi,
qualcuno ha capito qualcosa della lezione di ieri 10.10.2011 ?
L'ultima parte... quando ha cominciato a parlare di varianza, probabilità etc... io mi son perso alla grande.
Ciao a tutti
Daniele |
| zack1988 |
| Io ero a bocca aperta. |
| xSharKMaNx |
Chiedo l'aiuto del pubblico...
Hash Table
Oltre ad aver capito che è un array di liste quando ha cominciato a parlare di formule io mi sono perso.... |
| panzone |
Originally posted by xSharKMaNx
Chiedo l'aiuto del pubblico...
Hash Table
Oltre ad aver capito che è un array di liste quando ha cominciato a parlare di formule io mi sono perso....
E' il problema di far spiegare ad un matematico certe cose :D Per carità, sicuramente interessante ed utile, ma se sei ad algoritmi significa che un idea di quello fatto a continuo e discreta ce l' hai ed è inutile esser cosi prolissi.
Un hash table è, per l' appunto, un array di liste gestite tramite hash. Per hash si intende il risultato di una funzione che, dato in input un elemento, questa genera un codice, un qualcosa che identifica il mio oggetto ( solitamente nelle implementazioni si utilizza un numero, per tutta una serie di motivi ).
Esempio semplicissimo di funzione hash: ho una stringa. Il suo valore di hash è dato dalla somma del valore ASCII dei suoi caratteri. Quindi, usando questa funzione, posso ottenere un valore che mi permette di identificare la stringa.
Ora, le hash table. Come abbiamo visto dalla mia funzione hash precedente, ottengo un numero. E se usassi questo numero come ( ad esempio ) l' indice di un array per salvare la mia stringa ? Se ci pensi sarebbe molto comodo in fase di ricerca: difatti, visto che la stringa verrà salvata solo in quella posizione, indicata dal mio hash, per la ricerca non dovrò scorrere tutto il vettore, ma semplicemente controllare l' indice ( ricavabile usando la funzione di hash ) per vedere se è presente ! Come vedi, dunque, il tempo di ricerca di un vettore tende ad essere costante.
Ora, gli svantaggi dell' hashing: il primo punto è che le hash table si prendono un casino di memoria: non è detto difatti che userai tutti gli indici in maniera ordinata e dunque potresti trovarti vettori immensi con immense aree vuote.
Esempio: ho la stringa "ciao", che è, usando la funzione di hashing detta prima, il valore 412. Questo significa che devo allocare almeno 412 posizioni, ma le 411 posizioni precedenti ( al momento e molto probabilmente ) resteranno vuote :D
Poi, altro svantaggio ( ed è il motivo per cui si usano array di liste ): le funzioni hash posson generare lo stesso valore con input diversi. Basta vedere l' esempio precedente: e se dopo "ciao" volessi salvare la parola "bibo", che anche lei con la funzione precedente ha valore 412 ? Semplicemente, usando un array di liste, posso salvare entrambe le stringe in una lista presente all' indirizzo 412 del vettore. In fase di ricerca vado direttamente in quella posizione e scorro la lista ( che sarà sicuramente più veloce che scorrere l' intero vettore per vedere se le mie stringhe son presenti).
Questo cosa significa ? Che la hash table avranno pure tempo costante di ricerca, tuttavia il loro utilizzo deve essere ben giustificato dalla mole di dati che si andranno ad inserire e dalla stabilità della funzione hash ( se questa genera facilmente output uguali, se questa genera output il più possibile distribuiti ecc. ecc. ). |
|
|
|
