Pages: [1]   Go Down
Print
Author Topic: Hashing, cancellazione  (Read 1029 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« on: 09-08-2011, 10:46:05 »

Nella risoluzione delle collisioni si usa tra i metodi quello del concatenamento, sul testo è scritto che la cancellazione dalla lista è eseguita in tempo O(1) ma non mi convince. L' algoritmo è:

Code:
CHAINED-HASH-DELETE(T,x)
              cancella x dalla lista T[h(key[x])]

Dice che non c' è bisogno di cercare l' elemento perchè lo passiamo come parametro, ma perchè? Io con h(...) dovrei accedere alla locazione dell' array che punta alla lista, ma l' elemento non è detto che sia in testa, perchè la complessità non dovrebbe essere O(n)?
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #1 on: 09-08-2011, 12:44:24 »

x e' un puntatore... ti basta trovare quale sia la lista che contiene l'elemento puntato da x e cancellarlo => tempo costate se le liste sono bidirezionali.
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #2 on: 09-08-2011, 22:36:36 »

Non mi è ben chiaro, nelle locazioni io memorizzo direttamente le chiavi oppure un puntatore alla chiave? Cioè se "x" punta alla chiave, io accedo alla locazione dell' array contenente l' elemento, ma in ogni caso come faccio a sapere
dov' è nella lista? Cioè se avessi:


1:
2:
3:
4: k1,k2,k4,k5

Dove i numeri indicano le locazioni dell' array, se per esempio il mio x punta alla chiave k5, io posso accedere direttamente a quell' elemento che contiene k5?
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Crasher
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 417



« Reply #3 on: 10-08-2011, 11:03:39 »

Da quel che mi ricordo x lo puoi considerare come un oggetto. La funzione hash viene calcolata in base alla chiave di x ( key[ x ] ) e in base al valore di output viene inserito nella tabella.

La ricerca di un oggetto con chiave k si calcola la funzione hash(k) per trovare la posizione di dov'è conservato l'oggetto x nella tabella e poi si scorre la lista degli oggetti in quella posizione ( la lista può essere nulla o avere dimensioni >= 1 ). Teoricamente complessità O(n) dove n = numero di oggetti della lista.

Cancellazione: stesso discorso della ricerca. Teoricamente complessità O(n).

Ma se leggi più avanti scoprirai che le funzioni hash non si creano a casaccio, ma dovrebbero soddisfare le ipotesi di uniformità semplice, ovvero le chiavi dovrebbero occupare in modo equo le m posizioni della tabella Hash (l'esempio di Daréios è dunque pessimo). Con queste ipotesi, la distribuzione delle chiavi nella tabelal è più uniforme, cosicchè non si creeranno lunghe liste di oggetti in una determinata posizione (il fattore \alpha si mantiene basso) e le complessità della ricerca e della cancellazione saranno O(1+ \alpha )
Logged

Diventa ciò che sei nato per essere
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #4 on: 10-08-2011, 12:17:44 »

Mi sono espresso male, con il mio esempio sembra che ovviamente tutte le chiavi sono in un' unica locazione e quindi in un' unica lista, volevo solo prendere in considerazione una lista per semplicità. Si andando più avanti è come dici tu, complessità \theta(1+\alpha) per la ricerca, anche per la cancellazione secondo me orientativamente doveva essere \theta(n) come dici tu, ma nel testo si legge che proprio perchè la lista è doppiamente concatenata, e il metodo prende in input l' oggetto e non la chiave, può essere eseguita in tempo O(1) e non c' è bisogno di ricercare l' elemento nella lista, cosa che non capisco come si possa fare visto che non si sa l' ordine delle chiavi. Cioè grazie all' oggetto "x" io posso calcolare mediante la funzione di hash T[h(key(x))] la locazione dove è inserita la chiave e la locazione della lista dov' è contenuta, ma nella lista non so dove si trova, quindi non devo cercarla?
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
XDnl
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 376



« Reply #5 on: 10-08-2011, 14:17:38 »

Vediamo se ho capito, forse la confusione sta nel concetto di "chiave" e "puntatore"...
La tabella hash è un vettore di liste.
Ogni lista è composta da vari nodi.
Ogni nodo contiene la chiave, eventuali dati satellite, ed i puntatori all'elemento successivo e precedente.
Una cosa di questo tipo
Code:
class Node
{
       private int key;
       private Node next, prev;
      ...
}
class List
{
        private Node head, tail;
        private int size;
        ...
        // Cancella un nodo (eventualmente aggiusta head e tail), aggiorna size
        // Impiega tempo costante perchè la lista è bidirezionale.
        private void deleteNode(Node node) { ... }
}
La tabella hash potrebbe essere  definita così:

Code:
public static final HASH_ENTRIES = 10000;
public List[] hashTable = new List[HASH_ENTRIES];

Nella funzione
Code:
CHAINED-HASH-DELETE(T,x)
              cancella x dalla lista T[h(key[x])]

per x non si intende la chiave dell'elemento da rimuovere (nell'esempio il campo int key della classe Node) ma il puntatore al nodo che contiene tale elemento.
La funzione Chained-Hash-Delete  per come è presentata cancella un elemento dalla tabella hash a partire da un nodo, non a partire dalla chiave.

E' necessario calcolare la funzione hash h(...) sulla chiave del nodo perchè bisogna determinare a quale lista appartiene, in modo tale da poter richiamare il metodo per la rimozione (ciò è necessario perchè oltre ai puntatori prev/next dei vari nodi bisogna aggiornare anche altri parametri, come size, head e tail).
Una possibile implementazione potrebbe essere
Code:
public void Chained_Hash_Delete(List[] hashTable, Node x)
{
hashTable[hashFunc(x.getKey())].deleteNode(x);
}
Supponendo che hashFunc sia la funzione di hashing.

Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #6 on: 10-08-2011, 16:43:03 »

Ti ho fatto un disegnino per farti capire in che situazione ci troviamo... quello che sostieni te e' la seguente... supponiamo che davanti a te vedi un vaso che devi rompere, ma pur vedendolo perdi tempo a cercarlo per tutta la casa per poi alla fine romperlo. Non avresti fatto prima a romperlo direttamente invece di cercarlo??? 
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #7 on: 11-08-2011, 13:51:48 »

Si così ci siamo, certo funziona. 
Quindi semplicemente, come visto dal disegno x punta al nodo, non significa che il nodo che contiene la chiave e i dati satellite si chiama x ma semplicemente x punta a quel nodo che contiene key[x] ed eventuali dati satellite, giusto? Comunque si così mi convince.
Grazie shiny e XDnl.
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Pages: [1]   Go Up
Print
Jump to: