Mennyi extra memóriát igényel egy szótáras megoldás, a visszaküldött adatok nélkül?

A szótár (hash-tábla) használata további memóriát igényel, amely arányos azzal a mennyiséggel, ahány egyedi kulcsot adunk hozzá. Ha N egyedi elem van, akkor a memória körülbelül O(N), mivel minden kulcshoz és a hozzá tartozó értékhez helyet foglalunk.

Például, ha egy szótárat hozunk létre a szövegben előforduló szavak számolására, akkor a memória növekedni fog az egyedi szavak számával. Emellett a szótár szerkezete általában további költségeket tartalmaz a hash-értékek tárolására és az ütközések kezelésére, de általában az O(N) becslés a leggyakoribb a további memória szempontjából.