Колко допълнителна памет изисква решение със речник, без да се броят върнатите данни?

Използването на речник (хеш таблица) изисква допълнителна памет, пропорционална на броя на уникалните ключове, които се добавят към него. Ако имате N уникални елемента, паметта ще бъде приблизително O(N), тъй като за всеки ключ и свързаната с него стойност се заделя място.

Например, ако създавате речник за броене на броя на срещанията на думи в текст, паметта ще расте с увеличаването на броя на уникалните думи. Структурата на речника обикновено включва допълнителни разходи за съхранение на хеш стойности и управление на колизиите, но като цяло оценката O(N) за допълнителната памет е най-практична.