Kui palju lisamälu nõuab sõnastikuga lahendus, välja arvatud tagastatavad andmed?

Sõnastiku (hash-tabeli) kasutamine nõuab täiendavat mälu, mis on proportsionaalne sinna lisatud unikaalsete võtmete arvuga. Kui teil on N unikaalset elementi, on mälu ligikaudu O(N), kuna iga võtme ja sellega seotud väärtuse jaoks eraldatakse ruumi.

Näiteks, kui loote sõnastiku, et lugeda sõnade esinemissagedust tekstis, kasvab mälu koos unikaalsete sõnade arvu suurenemisega. Lisaks sisaldab sõnastiku struktuur tavaliselt täiendavaid kulusid hash-väärtuste salvestamiseks ja kokkupõrgete haldamiseks, kuid üldiselt on O(N) hinnang täiendavale mälule kõige praktilisem.