[C++] hashset e liste di collisione

[Don[ITA]]

Salve a tutti ^^
Avrei un dubbio, diciamo teorico, sull'implementazione di un hashset con gestione delle collisioni mediante liste.
E' un progetto universitario abbastanza semplice ma ho cmq qualche dubbio.
Gestire le collisioni con liste vuol dire che (ad esempio), il mio hashset è implementato mediante un array di coppie hash-lista, o che le coppie sono hash-valore e l'hashset contiene una lista in cui infilo i dati che generano hash uguale a quelli gia presenti? O ancora dovrei creare un'array di tuple formate da hash-valore-lista? se si, quando avviene una collisione il valore viene sostituito e quindi quello vecchio viene aggiunto alla lista?

Sono perplesso XD

Spero di essere stato chiaro ^^ grazie per l'attenzione :)

Saluti

[cionci]

Le coppie sono Hash lista. In ogni lista ci sono tutti i valori con lo stesso hash.

[Don[ITA]]

Quindi se volessi iterare sul mio hash set, l'iteratore punterebbe a cosa? alla coppia hash-lista, o solo alla lista?

Grazie per la risposta

Saluti

[cionci]

In C++ non esiste il contenitore hash set. Dipende tutto da come implementi l'hash set, se lo implementi con una map l'iteratore punterà alla coppia.

[Don[ITA]]

Si si lo sò che non c'è ^^ difatti il progetto ne prevede l'implementazione :)
Io l'ho implementato in due modi differenti:
-array di pair<hash, lista>: facile da gestire (non deve nemmeno essere ridimensionabile), con iteratiori che puntano alla sola lista (ho pensato che essendo un "set", non avrebbe senso tornare la coppia, ma probabilmente ho pensato una vaccata)
-lista lincata di struct fatte così:

struct tupla {
tupla* prec;
tupla* next;
int hash;
lista* list;
...ecc ecc...
};

e anche qui l'iteratore punterebbe, o meglio, il dereferenziamento dell'iteratore mi restituirebbe il riferimento alla lista della tupla corrispondente.

Però se mi dici che dipende da come implemento l'hashset allora vuol dire che sono buone tutte le soluzioni...giusto?

Arigrazie :)

Ciauz

[cionci]

Imho prima di tutto devi fare una classe lista. Quando ottieni un oggetto di classe lista ti basta fare:

list.add(element);

Sia set che map della STL lavorano sui pair, quindi ha senso che un iteratore ritorni un pair.
Mi immagino che tu non possa usare un contenitore della libreria standard per contenere i vari hash, anche perché a seconda di come hai costruito l'hash si possono sfruttare vari metodi di accesso diretto.

Mettiamo che il tuo hash sia a 24 bit. Una struttura di 16 MB è perfettamente gestibile da qualsiasi computer. In questo modo hai la possibilità di accedere con complessità O(1) alle liste.
Racchiuderei il vettore di un'altra classe hash_map (di fatto è un map, perché è ordinato secondo la chiave).
Fare un hash a 32 bit alla fine ha veramente poco senso, a quel punto ti conviene davvero utilizzare un contenitore associativo della libreria standard, perché non potresti sfruttare l'accesso O(1).

[Don[ITA]]

Si si lista ce la fornisce il prof :)
Altra cosa non mi è chiara...se io implemento l'hashset con un array di pair<hash, lista>, come fò ad ottenere O(1) in accesso???
In un ipotetico metodo find, pensavo di calcolare l'hash del dato passato come parametro e di scorrere l'array finchè non trovo l'hash uguale, ma non credo affato che sia O(1) fare così...

Mettiamo che il tuo hash sia a 24 bit. Una struttura di 16 MB è perfettamente gestibile da qualsiasi computer. In questo modo hai la possibilità di accedere con complessità O(1) alle liste.
Racchiuderei il vettore di un'altra classe hash_map (di fatto è un map, perché è ordinato secondo la chiave).
Fare un hash a 32 bit alla fine ha veramente poco senso, a quel punto ti conviene davvero utilizzare un contenitore associativo della libreria standard, perché non potresti sfruttare l'accesso O(1).

Un hash a 24 bit??? Non somo molto bravo in c++ ma non mi sembra ci sia un primitivo a 24 bit :confused: ... me lo devo creare io?

Sei troppo iper gentile ^_^

Grazie per la risposta

[cionci]

Non esiste un primitivo a 24 bit, ma puoi limitare il range dell'hash fino a 2^24.
Se fai un vettore di questo tipo:

lista hashtable = new lista[16777216]; //16777216 è 2^24

Puoi ottenere l'accesso O(1) alla lista con un determinato hash. Per verificare se l'elemento esiste:

hashtable[hash(elemento_da_cercare)].find(elemento_da_cercare)

Il prezzo da pagare è nell'allocazione di memoria. Infatti in questo modo bisogna allocare preventivamente tanti elementi lista quanto è la dimensione del dominio dell'hash. Quindi la funzione hash() che ho scritto sopra deve ritornare un intero fra 0 e 2^24.
Chiaramente puoi anche scendere di dimensione, ad esempio 16 bit, così puoi "sprecare" meno memoria.
Volendo puoi anche semplicemente dichiarare un vettore di puntatori a lista, risparmiando ancora più memoria se lista occupa molto spazio. In questo modo dovrai inizializzarli a null. Se un puntatore è null significa che none sistono elementi con quell'hash.

[Don[ITA]]

aaaaaaaah ok ci sono :)
Quindi se il mio hash, ad esempio, sta nel dominio 0-500, mi alloco subito un array che ricopre il dominio, così da poter usare l'hash come indice :) Geniale XD
E se invece, alloco un'array di dimensione, mettiamo 50, e dopo aver fatto l'hash ne faccio il modulo di 50? così da ottenere un indice compreso non nel dominio dell'hash ma nella dimensione dell'array?
Però adesso che ci penso non sò a priori quanto sia il dominio dell'hash...la funzione di hashing infatti può essere passata come funtore del mio hashset in fase di costruzione, quindi teoricamente potrebbe anche tornarmi qualcosa come 4294967296 (2^32) visto che l'unico limite che impongo è che l'hash sia un int (forse sarebbe meglio un unsigned int).

Cmq grazie per la risposta, ora mi è chiaro l'accesso in O(1) :D

[cionci]

Certo, se fai il modulo va bene, ma di fatto fai un altro hash ;)

[Don[ITA]]

Vero :D
Quindi per risparmiare memoria a gogo mi consigli di:
-rendere l'hash il più piccolo possibile (16 o 24 bit)
-creare un array di pair<hash, lista*> con lista* = 0 se non ci sono elementi con quell'hash

Sei er mejo :D
Ma se volessi usare delle liste lincate invece che un array, come potrei ottenere O(1) in accesso?
Riririririgrazie :D

Ciauz

[cionci]

Ovviamente no. La ricerca in O(1) è dovuta proprio al vettore.

A questo punto il pair non ti serve.

[Don[ITA]]

ok tutto chiaro ^^ grazie mille ancora

[Tommo]

Se l'elenco non viene riempito con una densità costante, ma ha delle "bolle" di NULL e di hashset pieni, potresti risparmiare memoria allocando l'array "a pezzi" invece che tutto insieme, con una specie di struttura ad albero.

Ma alla fine 16 mb non sono niente quindi mi pare eccessivo :asd:

[cionci]

Se l'elenco non viene riempito con una densità costante, ma ha delle "bolle" di NULL e di hashset pieni, potresti risparmiare memoria allocando l'array "a pezzi" invece che tutto insieme, con una specie di struttura ad albero.
Bella idea. Sicuramente può essere una valida alternativa, puoi usare alcune cifre dell'hash per allocare porzioni del vettore, che poi diventerebbe un albero.

Ad esempio, mettiamo che tu faccia una partizione del vettore che riguarda gli 8 bit più significativi.

La tabella principale contiene 2^8 elementi:

lista **hashtable[256];

devi impostare a NULL ogni elemento del vettore.
A questo punto ogni volta che vuoi inserire un elemento nell'hash ottieni gli 8 bit più significativi dell'hash, recuperi il valaore di hashtable corrispondente, se è NULL significa che non ci sono elementi:

if(hashtable[hash >> 16] == NULL)
{
hashtable[hash >> 16] = new lista*[65536];
}
if(hashtable[hash >> 16][hash & 0x0FFFF] == NULL)
{
hashtable[hash >> 16][hash & 0x0FFFF] = new lista();
}
hashtable[hash >> 16][hash & 0x0FFFF].add(nuovo_elemento);

[Tommo]

Però in questa maniera non hai molta libertà sul pagesize, che deve essere per forza 65536... forse sarebbe meglio fare tipo così:


//pagesize definito altrove
void addHash( lista* list )
{
//ricava hash
unsigned int hash = ...

//ottieni il primo indirizzo "grossolano"
unsigned int pageIndex = hash/pagesize;
Lista** subList = pages[ pageIndex ];

if( subList == NULL )
subList = new Lista**[ pagesize ];

//ora esiste la page necessaria, salvo list
subList [ hash - pageIndex ] = list;
}


in questo modo pagesize potrebbe essere qualsiasi valore trovato empiricamente.
D'altra parte, la convenienza di questo approccio dipende dal rapporto vuoti/pagesize... se pagesize fosse sbagliato, si finirebbe per consumare più memoria o con il fare troppe allocazioni.
E poi vuoi mettere usare un Lista*** :asd:

[cionci]

Ok, era solo per fare un esempio, poi le dimensioni le può cambiare come più vuole ;)

[Don[ITA]]

uuuuuuuuuuuuuu strepitoso ^^
Grazie Tommo per l'idea :)

[Don[ITA]]

Ok i consigli mi sono stati mega utilissime, ma ora ho qualche piccolo problema tecnico :D
Per prima cosa mi sono inmplementato l'hashset in modo semplice con un array di puntatori a liste:


template <class key, class hashFunc = defaultHashFunc<key> > class hashset {

typedef unsigned short size_type; //tipo riferito alla dimensione (max 65535)
typedef key value_type; //tipo riferito al dato
typedef hashFunc hasher; //tipo riferito alla funzione di hashing
typedef lista<value_type> collision;// tipo riferito alla lista di collisioni
typedef collision* col_ptr; //tipo riferito al puntatore alla lista di collisioni

col_ptr* data; //array di puntatori alle liste di collisioni
size_type max_size; //dimensione massima dell'hashset
hasher hash; //funzione di hashing
...ecc...

e subito mi sono venuti dei dubbi sul distruttore...essendo un array di puntatori può comunque essere corretto fare solo cosi?

~hashset() {
delete[] data;
data = 0;
max_size = 0;
}


Poi altro problemuccio che proprio non capisco con gli iteratori...
Ecco come ho scritto la classe:

class const_iterator : public iterator<bidirectional_iterator_tag, const key, ptrdiff_t, const key*, const key&> {

friend class hashset;

col_ptr* dato;
col_ptr* first;
col_ptr* last;

const_iterator(col_ptr* d, col_ptr* f, col_ptr* l) : dato(d), first(f), last(l) {}
...ecc ecc metori ++(), --(), ecc ecc...

e per l'operatore di dereferenziamento ho pensato di far tornare un reference (ovviamente costante trattandosi di const iterator) alla lista di collisioni in questo modo:

const collision &operator*() const {
return *(*dato);
}

Solo che quando provo a stampare il contenuto di un iteratore nel main mi esplode tutto dando l'errore di win...il test lo fà cosi ad esempio:

hashset<int> hs;
hs.insert(20);
hs.insert(30);
hs.insert(40);
cout << *(hs.begin()) << endl;

E non capisco assolutamente a cosa potrebbe essere inputato questo errore :confused:

Grazie per la pazienza e l'aiuto :D

Ciauz