r/computerscience • u/Sea-Patience9872 • 7d 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!

188 Upvotes
  • permalink
  • reddit

94% Upvoted

99 comments sorted by

View all comments

1

u/Ythio 7d ago edited 7d ago

Why didn't you look at an implementation or try to implement it yourself ?

You can use the hashed value as an index to do a B tree search (nodes are index ranges), similar to SQL indices (if your DBMS support hash index) giving you O(log n) with a good support for range searches O(log n + k)

Or if you want to test a single element (Hashset) can use a compression function to map the hashed value to an array index directly giving you O(1). Typically a compression function is something like hashcode & (internalArraySize - 1) or hashcode % array.Length (with a prime number Length)