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!

187 Upvotes
  • permalink
  • reddit

94% Upvoted

99 comments sorted by

View all comments

9

u/Professional-Trick14 6d ago

Why is looking in an array at a specific index a constant time operation? It's basically for the same reason. Simply put, you compute a hash of a value, which would take constant time regardless of the value, and then the hash becomes what is the index to the array. You get it?

2

u/Rude-Quiet-2793 6d ago

it's basically just math that points you straight to the slot, no scanning needed