È possibile utilizzare hashtable per implementare multimap?

Question

È possibile utilizzare hashtable per implementare multimap?

Naviga le tue risposte

#1 da (3 voti)
#2 da (2 voti)

0

È corretto che gli hashtable non presuppongono che nessuna chiave venga condivisa tra più di un record?

In altre parole, è possibile utilizzare le hashtables per implementare multimaps?
Quando si utilizza una tabella hash, non è possibile più record con la stessa chiave il valore va trattato nello stesso modo in cui si ha a che fare con l'hash collisione?

In particolare, le seguenti operazioni possono funzionare allo stesso modo di risoluzione della collisione dell'hash:
- inserendo due record diversi con lo stesso valore chiave e
- cercando eventualmente più di un record con lo stesso valore chiave
- eliminando probabilmente più di un record con lo stesso valore chiave.

Grazie.

data-structures hashtable map

posta Tim 19.10.2016 - 08:51

fonte

2 risposte

Leggi altre domande sui tag data-structures hashtable map

Utilizzo di ID HTML o classe anziché commenti Ridondanza nel processo che legge e cancella dal database

score 3 · Answer 1

Gli hashtables si occupano sempre della possibilità di collisioni hash, in quanto vi sono buone probabilità che si verifichino anche per chiavi diverse, la dimensione degli hash utilizzati è molto più piccola di quella usata per la crittografia, ad esempio.

Un modo in cui gestiscono le collisioni è utilizzando un elenco di coppie collegate che condividono un hash chiave.

Quindi, non vedo alcun impedimento nell'implementare un multimap nello stesso modo.

score 2 · Answer 2

Sì, il contratto di interfacce tabella / mappa come Java Map<K,V> oder. NET IDictionary<K,V> di solito specifica che una chiave ha esattamente un valore di tipo V .

Perché non le multi-mappe? Perché questo è un caso d'angolo che viene usato molto raramente mentre le mappe a valore singolo sono usate molto più frequentemente. È più facile utilizzare una mappa multipla utilizzando Map<K,Set<V>> laddove necessario invece di avere multi-mappe dello standard ed estrarre tutto il singolo elemento dell'immagine.

In effetti questo è quello che farei se volessi implementare una classe multi-map: creerei una Map<K,Set<V>> della struttura dati sottostante e delegheremo la maggior parte del lavoro a quell'oggetto. Che sia una mappa hash o un'altra mappa non è poi così importante.