Dictionarygegevensstructuren

Dictionarygegevensstructuren, ook wel dictionaries, kaarten of maps genoemd, zijn datastructuren die sleutel-waarde-paren koppelen. Elke sleutel komt slechts één keer voor in de structuur en wijst naar een bijbehorende waarde. De belangrijkste operaties zijn toevoegen of bijwerken (put), opzoeken op basis van een sleutel (get/lookup) en verwijderen (delete). Vaak is ook iteratie over alle paren relevant, bijvoorbeeld om de inhoud te doorlopen of te serialiseren.

De meest voorkomende implementaties zijn hashtabellen en geordende kaarten zoals gebalanceerde zoekbomen (bijv. rode-zwartboom, AVL). Daarnaast bestaan probabilistische alternatieven zoals skiplists en speciale tries voor string- of prefix-gebruik. Hashtabellen bieden gemiddeld constante tijd voor insert, lookup en delete, maar leveren geen natuurlijke volgorde op; de volgorde hangt af van de hashfunctie en de toegepaste conflict-resolutie. Worst-case tijd is O(n). Geordende kaarten behouden een sortering en maken doorlopen in sleutelvolgorde mogelijk; de gebruikelijke complexiteit is O(log n) per operatie. Tries bieden efficiënte prefix-match en lexicografische navigatie, maar kunnen aanzienlijk meer geheugen vergen.

Toepassingen van dictionarygegevensstructuren zijn onder meer caches, configuratiegegevens, symboltabellen in compilers, en indexering binnen databases. De keuze voor een implementatie hangt af van factoren zoals vereiste volgorde, geheugenbudget, prestaties onder concurrency en mutabiliteit, en de gewenste operationele complexiteit. In programmeertalen wordt dit concept vaak gerealiseerd als Maps, Dictionaries of associative arrays.