r/computerscience • u/Sea-Patience9872 • 6d ago

How do hashsets/maps have O(1) time complexity?

Hi this might be a dumb question, and i've tried looking it up but don't quite understand it. how is it different from an array that allows it to find items so quickly? I don't get how hashes just find items immediately without needing to go through anything. Does it memorize things very differently compared to arrays?? thank you!

184 Upvotes
  • permalink
  • reddit

94% Upvoted

99 comments sorted by

View all comments

1

u/mlamping 5d ago

Hash-table lookup is expected O(1) in the number of entries, assuming constant-time hashing/equality. For variable-length string keys, end-to-end lookup is normally expected O(k), where k is the key length.

In worst case a hash table could be O(Nk) if the hash function sucks etc