Чӣ қадар ёддоштҳои иловагӣ барои ҳалли бо луғат талаб мешавад, бе ҳисоб кардани маълумоти баргардондашуда?

Истифодаи луғат (хеш таблица) талаб мекунад ёдгории иловагӣ, ки нисбат ба шумораи калидҳои беназири, ки ба он илова карда мешаванд, нисбатан зиёд аст. Агар N унсурҳои беназир дошта бошед, ёдгории тақрибан O(N) хоҳад буд, зеро барои ҳар калид ва арзиши пайвастшуда ҷой таъин карда мешавад.

Масалан, агар шумо луғатро барои ҳисоб кардани шумораи вурудоти калимаҳое, ки дар матн ҳастанд, эҷод кунед, ёдгории он бо афзоиши шумораи калимаҳои беназир меафзояд. Илова бар ин, сохтори луғат одатан хароҷоти иловагӣ барои нигоҳдории арзишҳои хеш ва идоракунии коллизияҳоро дар бар мегирад, аммо дар умум, тахмини O(N) дар ёдгории иловагӣ бештар амалӣ аст.