Koľko dodatočnej pamäte vyžaduje riešenie so slovníkom, okrem vracaných údajov?

Použitie slovníka (hash tabuľky) vyžaduje dodatočnú pamäť úmernú počtu unikátnych kľúčov, ktoré do neho pridávate. Ak máte N unikátnych prvkov, pamäť bude približne O(N), pretože pre každý kľúč a s ním spojenú hodnotu je vyhradené miesto.

Napríklad, ak vytvárate slovník na počítanie výskytu slov v texte, pamäť bude rásť s nárastom počtu unikátnych slov. Štruktúra slovníka zvyčajne obsahuje dodatočné náklady na uloženie hash hodnôt a správu kolízií, ale všeobecne je odhad O(N) na dodatočnú pamäť najpraktickejší.