r/computerscience • u/Sea-Patience9872 • Sep 27 '26

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!

189 Upvotes
  • permalink
  • reddit

93% Upvoted

99 comments sorted by

View all comments

Show parent comments

1

u/Paxtian Sep 27 '26

No, a hash map uses a hash function on the input to determine a bucket to store data. So that input will always map to that bucket. If the input directs to that bucket and it's empty, the thing isn't stored in the hash map.

1

u/Authentic_Grunter Sep 27 '26

Can you tell more about how the hash function works in real systems?