एक hash map (dictionary) औसतन O(1) में lookups, inserts, और deletes देता है। O(n) memory को गति के बदले देकर, कई O(n²) algorithms O(n) बन जाते हैं, क्योंकि बार-बार के scans की जगह तुरंत lookups आ जाते हैं।
मूल विचार
हर बार किसी list को खोजने के बजाय, देखे गए values को एक hash map में store करें और constant time में membership जाँचें।
उदाहरण: O(n) में two-sum
():
seen = {}
i, x (nums):
need = target - x
need seen:
(seen[need], i)
seen[x] = i
two_sum([, , , ], )
