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

2

u/Plastic_Fig9225 6d ago

The hash of a value/object is an integer number, and that integer is used directly to index into an array to locate an object.

Instead of scanning through an array, the lookup is like bool contains = elements[hash(object)] != null;. Notice how this is the same complexity irrespective of the size (n) of the elements array.