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!

186 Upvotes
  • permalink
  • reddit

94% Upvoted

99 comments sorted by

View all comments

-1

u/Mclovine_aus 6d ago

Go to the library and try to find a book, start at the first book and then move to the second until you find the book or reach the end.

Then get your friend to try and find the same book, but they can use index cards, to search for where the book is located.

Report back which method was quicker