Hoeveel extra geheugen vereist een oplossing met woordenboek, exclusief de geretourneerde gegevens?

Het gebruik van een woordenboek (hash-tabel) vereist extra geheugen dat evenredig is met het aantal unieke sleutels dat eraan wordt toegevoegd. Als je N unieke elementen hebt, zal het geheugen ongeveer O(N) zijn, omdat voor elke sleutel en de bijbehorende waarde ruimte wordt gereserveerd.

Bijvoorbeeld, als je een woordenboek maakt om het aantal voorkomen van woorden in een tekst te tellen, zal het geheugen toenemen naarmate het aantal unieke woorden toeneemt. De structuur van het woordenboek bevat meestal extra overhead voor het opslaan van hash-waarden en het beheren van botsingen, maar over het algemeen is de schatting van O(N) in extra geheugen het meest praktisch.