PDA

Visualizza la versione completa : [C++] Dynamic Hashing


AyFrank
11-01-2013, 15:55
Salve, ho la necessità di eseguire operazioni di inserimento - ricerca su intervalli di valori molto ampi (per dare un esempio 1500 - 1000000), e cercando in rete mi sono imbattuto in questo hashing dinamico, non mi è però molto chiaro come funziona la cosa, qualche delucidazione sarebbe assai gradita! :D

MdE2005
11-01-2013, 16:13
Originariamente inviato da AyFrank
qualche delucidazione sarebbe assai gradita! :D

Sarebbe gradita a noi :dhò:

Qual'è la tua domanda? Voi informazioni sull'hashing dinamico? Precisa un pò meglio cosa devi fare, magari postando il codice provato e gli eventuali errori sollevati.

AyFrank
11-01-2013, 16:34
Originariamente inviato da MdE2005
Sarebbe gradita a noi :dhò:

Qual'è la tua domanda? Voi informazioni sull'hashing dinamico? Precisa un pò meglio cosa devi fare, magari postando il codice provato e gli eventuali errori sollevati.
Hai ragione, mi sono appena accorto di non aver chiesto praticamente niente :D

Ho letto qualcosa sul "dynamic perfect hashing", ancora non ho scritto niente perché non ho ben chiaro qual'è il meccanismo. Per ogni insieme di elementi k (dim = d) che collidono sulle celle della tabella principale avrò un'ulteriore tabella hash secondaria (dim = d^2)?

Non mi dispiacerebbe neanche ricevere qualche altra idea per la risoluzione del mio problema (spero che almeno questo si sia capito), che non comprenda però meccanismi di riallocazione troppo pesanti...

MegaAlchimista
11-01-2013, 19:25
Insomma.... Io credo che la tua richiesta possa essere più ricca di dettagli :D ...
1500 - 1000000 è l'intervallo all'interno del quale risiede il massimo numero di elementi che devi inserire nella hash table?
Oppure vuoi limitarti ad un eventuale massimo di 1000000 indici ma gli elementi sono di più?
Oppure devi essere un grado di fare 1000000 inserimenti/ricerche per volta?

Inoltre , di che tipo sono gli elementi che vuoi inserire in tabella? stringhe, altro?
Perchè una funzione di hashing ovviamente dipende in primo luogo dal tipo su cui va ad operare!
Inoltre nel caso fossero stringhe (presumo siano stringhe), hanno una qualche proprietà particolare? Per esempio sono formattate in un certo modo o hanno carateri speciali o altre caratteristiche?
Non so... Possono essere nomi di persona, url, path, poesie, verbi, frasi dei baci perugina...

AyFrank
11-01-2013, 19:58
Originariamente inviato da MegaAlchimista
Insomma.... Io credo che la tua richiesta possa essere più ricca di dettagli :D ...
1500 - 1000000 è l'intervallo all'interno del quale risiede il massimo numero di elementi che devi inserire nella hash table?
Oppure vuoi limitarti ad un eventuale massimo di 1000000 indici ma gli elementi sono di più?
Oppure devi essere un grado di fare 1000000 inserimenti/ricerche per volta?

Inoltre , di che tipo sono gli elementi che vuoi inserire in tabella? stringhe, altro?
Perchè una funzione di hashing ovviamente dipende in primo luogo dal tipo su cui va ad operare!
Inoltre nel caso fossero stringhe (presumo siano stringhe), hanno una qualche proprietà particolare? Per esempio sono formattate in un certo modo o hanno carateri speciali o altre caratteristiche?
Non so... Possono essere nomi di persona, url, path, poesie, verbi, frasi dei baci perugina...
Allora cercherò di essere il più chiaro possibile:
ho in input una lista di archi pesati 0 <= N <= 1000000, devo realizzare una struttura per poter poi calcolare un minimo albero ricoprente. Ho la necessità quindi di memorizzare tutti i vertici non sapendo a priori quanti possano essere.
Avendo N archi potrò avere dunque da sqrt (N*8) / 2 (circa) a N+1 vertici (che con 1000000 di archi corrisponde più o meno all'intervallo 1500 - 1000000). Ogni vertice è un'oggetto contenente una stringa (che identifica univocamente il vertice) ed una lista di archi (contenente i vertici adiacenti).
Avendo intervalli così grandi, e dato il mio problema, sto cercando una struttura dati dinamica che mi consenta la memorizzazione dei vertici nella maniera più efficiente possibile, ed avevo quindi pensato ad una tabella hash dinamica...

Qui sorge il mio bisogno di aiuto: non riesco a capire i meccanismi di implementazione di questa struttura dati...

Loading