Multimap
Multimap (detta anche multihash oppure multidict), in informatica, è un contenitore associativo che contiene un elenco ordinato di coppie chiave-valore, consentendo al contempo più voci con la stessa chiave. L'ordinamento viene eseguito in base alla funzione di confronto, applicata sulle chiavi. Le operazioni di ricerca, inserimento e rimozione hanno complessità logaritmica.
L'ordine delle coppie chiave-valore le cui chiavi confrontano l'equivalente è l'ordine di inserimento e non cambia.
Il C++ presenta già all'interno del suo Standard Template Library una implementazione della struttura usando un albero binario auto-bilanciato[1] oppure anche Java, in qualità di interfaccia[2].
Alcuni esempi applicativi sono:
- In un sistema di iscrizione degli studenti, in cui gli studenti possono essere iscritti a più classi contemporaneamente, potrebbe esserci un'associazione per ogni iscrizione di uno studente in un corso, in cui la chiave è l'ID studente e il valore è l'ID del corso. Se uno studente è iscritto a tre corsi, ci saranno tre associazioni contenenti la stessa chiave.
- L'indice di un libro può riportare un numero qualsiasi di riferimenti per un determinato termine indice, e quindi può essere codificato come una multimappa dai termini dell'indice a qualsiasi numero di posizioni o pagine di riferimento.
- Le query possono avere più valori associati a un singolo campo. Questo viene comunemente generato quando un modulo Web consente di scegliere più caselle di controllo o selezioni in risposta a un singolo elemento del modulo.
Note
- ^ HPPSocialUserSignonPage - Hewlett Packard Enterprise Community, su community.hpe.com. URL consultato l'8 gennaio 2022.
- ^ MultiMap (Apache Commons Collections 3.2.2 API), su commons.apache.org. URL consultato l'8 gennaio 2022.
V · D · M | |
---|---|
Tipi | Collezione · Container |
Astratte | Array associativo (Multimap) · Lista · Pila · Coda (Deque) · Coda di priorità · Set (Multiset · Mfset) |
Array | Bit array · Buffer circolare · Array dinamico · Hash table · Array sparso |
Collegate | Lista di associazioni · Lista concatenata · Skip list · Unrolled linked list · Lista concatenata tramite XOR |
Alberi | B-albero · Albero binario di ricerca (Albero AA · Albero AVL · RB-Albero · Albero binario di ricerca bilanciato · Albero splay) · Heap (Heap binario · Heap binomiale · Heap di Fibonacci) · Albero di Merkle · Albero SPQR · Albero PQ · Albero indicizzato binario |
Grafi | Diagramma binario di decisione · Digrafo aciclico · Automa a stati finiti deterministico aciclico |
Alberi di partizionamento dei dati spaziali | Albero quadramentale · M-tree · R-tree (R* tree · R+ tree) · X-tree |
Lista di strutture dati |