Razpredelna tabela (angl. hash map, slovar) daje O(1) v povprečju za iskanja, vstavljanja in brisanja. Z zamenjavo O(n) pomnilnika za hitrost se marsikateri O(n²) algoritem spremeni v O(n) z zamenjavo ponavljajočih pregledov z trenutnimi iskanjem.
Osnovna ideja
Namesto pregleda seznama vsakič, shranjene vrednosti shranimo v razpredelno tabelo in preverimo pripadnost v konstantnem času.
Primer: two-sum v O(n)
():
seen = {}
i, x (nums):
need = target - x
need seen:
(seen[need], i)
seen[x] = i
two_sum([, , , ], )
