Dunque visto che le ricerche saranno molto frequenti, scartiamo immediatamente le liste linkate (perchè l'operazione di ricerca su questa ha complessità computazionale pari a O(N), occorre scandire tutta la lista nel caso peggiore, frequente quando la ricerca da esito negativo).

1° metodo:
Se per alberi bilanciati, intendi alberi auto-bilancianti, tipo i red black allora la complessità della ricerca è
O(2*log2(N+1)).
La classe map implementata nelle libreria std accompagnata al gcc e quella del visual c è basata su questi alberi.

Per le tabelle hash, dipende se:

2° metodo:
implementate con il metodo di concatenazione (usano liste), allora la complessità della ricerca è O(1 + alfa)

3° metodo:
implementate con il metodo dell'indirizzamento aperto allora la complessità della ricerca con successo è
O( (1/alfa) * ln( 1/(1-alfa) ) )

con alfa <= 1 cioè n <= m

la complessità della ricerca senza successo è
O( 1/(1-alfa) )

con alfa <= 1 cioè n <= m

alfa è pari a n/m

n = numero di elementi nella tabella
m = dimensione della tabella hash

quindi alfa è il numero medio di elementi memmorizzati in ogni lista concatenata.


Quale è più veloce?
Facciamo un esempio:

N = 1000000

1° metodo:
O(log2(1000000)= 40 test nel caso peggiore


2° metodo:
ipotesi: m = 32749, alfa = 1000000 / 32749 = 30,53
O(1+alfa) = 31 test nel caso peggiore

3° metodo:
ipotesi: m = 1428571, alfa = 1000000 / 1428571 = 0.70
ricerca con successo: (1/alfa) * ln( 1/(1-alfa) ) = 2 test
ricerca senza successo: 1/(1-alfa) = 4 test

3 metodo:
ipotesi: m = 3333331, alfa = 1000000 / 3333331 = 0.30
ricerca con successo: (1/alfa) * ln( 1/(1-alfa) ) = 2 test
ricerca senza successo: 1/(1-alfa) = 2 test

La libreria std c++ che viene distribuita con gcc, fornisce una classe hash_map che usa la tecnica a indirizzamento aperto (3° metodo). Si tratta comunque di una estensione non standard. (lo standard non prevede hash_map solo map e non da indicazioni sulla struttura da utilizzare per questa classe).

Di solito i sorgenti della libc++ sono sotto
/usr/include/c++/versione/

le estensioni, tra cui hash_map, qui
/usr/include/c++/versione/ext

Siccome devi fare spesso ricerche sia per nickname che per ip, la soluzione più efficiente IMHO è creare due indici simili a quelli usati dai DBMS, quindi due alberi/tabelle hash o una soluzione ibrida.

Cioè in un DB creo nickname come chiave primaria su cui di solito i DBMS creano automaticamente un indice (frequentemente vengono usati i btrees che sono diversi dagli alberi binari normali e dai red-black, perchè contengono in un solo nodo più chiavi e utilizzano per cui anche la ricerca binaria, ma sono adatti per lo più ai database).

Poi sul campo IP, mettendo come vincolo UNIQUE di solito i DB creano un indice per questi campi. Al limite si usa CREATE INDEX.

Se la portabilità è obbligatoria allora hash_map ti può dare rogne, quindi solo in questo caso userei 2 map.

Se usi gcc, allora 2 hash_map, sarebbe ottimo.

Punto a sfavore di hash_map è il consumo di memoria.

map (nell'ipotesi che sia implementata con alberi) usa un quantitativo di memoria proporzionale al numero degli elementi in essa memorizzati.

hash_map alloca prima un array di x posizioni (non byte) poi quando è riempito diventa di x+y posizioni, poi x+y+z, ecc...
quindi spreca un pò di memoria.


Comunque, spesso, per aumentare il tempo di esecuzione si decide di sacrificare il consumo di memoria.