Ricerca chiavi su HashTable con espressioni regolari

[Poker1]

Ciao a tutti!!!
ho una HashTable che ha come chiavi delle stringhe e vorrei eseguire delle ricerche restituendo tutti i valori che hanno un match con una espressione regolare su tutte le chiavi... come potrei fare?

Devo necessariamente scorrere tutte le chiavi e guardarle una per una? Non posso in un qualche modo adattare la ricerca alla funzione della HashTable containsKey ?

[andbin]

Originariamente inviato da Poker1
ho una HashTable che ha come chiavi delle stringhe e vorrei eseguire delle ricerche restituendo tutti i valori che hanno un match con una espressione regolare su tutte le chiavi... come potrei fare?

Devo necessariamente scorrere tutte le chiavi e guardarle una per una? Non posso in un qualche modo adattare la ricerca alla funzione della HashTable containsKey ?

Sì, direi che l'unica è fare una iterazione sulle chiavi e per ognuna verificare se fa il match con la regex. E comunque ti consiglio di precompilare con Pattern la regex. Cioè non fare str.matches(blabla) perché la compila ogni volta!

Tieni sempre presente come è fatta una mappa come HashMap o Hashtable (non TreeMap perché come dice il nome, è un albero).
Viene usata internamente una "hash-table" composta da una lista di N "bucket". Data una chiave, viene calcolato l'hash e tramite una apposita funzione, questo hash si traduce in un indice nella lista dei bucket.
Sotto il bucket c'è una lista linkata di entry formate da chiave+valore e viene scansionata cercando la chiave con equals(). Una volta trovata la chiave, si ottiene subito il valore.

[Poker1]

Ma quindi se io vado a fare una scansione di tutte le chiavi ho una complessita O(n) e quindi per questo tipo di ricerca ( con espressione regolare ) perdo la complessita' O(c) che ha la hashmap giusto? e' come cercare in un array "normale".

[andbin]

Originariamente inviato da Poker1
Ma quindi se io vado a fare una scansione di tutte le chiavi ho una complessita O(n)

Sorry per il ritardo (mi ero dimenticato). Nelle Map basate su una hash-table, la complessità della iterazione è O(h/n), dove 'h' è la capacità della hash-table (il numero di "bucket", non il numero di entry).