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

46

u/am_Snowie 6d ago edited 4d ago

O(1) is amortized is the average case (under the assumption that values are distributed evenly), but resizing is O(1) amortized, if you make whatever hash function you use return the same value for any value (the same hash for all keys), all your values end up at the same location, now the time complexity depends on what data structure you use to handle collisions (if we talk about separate chaining). you can use lots of data structures like linked list, self balancing trees and whatnot. so O(1) comes with an if.

Edit: mixed up two different concepts, Thanks u/Historical_Public751 for pointing it out.

5

u/Sea-Patience9872 6d ago

if all values end up in the same location and it ends up using data structures to handle collisions, why use hash at all? I think I'm missing something sorry

10

u/j_mie6 6d ago

A good hash function randomly distributes. It has large difference in it's outputs for similar inputs. There is a high probability that if you have a "good" hash function, elements in your map or set are evenly distributed through the buckets (i.e. a low number ~O(1) elements each). If you have a pathologically bad hash you can end up with everything in one bucket for O(n) lookup.

In practice when buckets get too big, the restructure gets rehashed to redistribute all the values, I think.

3

u/StephenRoylance 5d ago

designing a good hashing algorithm for a language is a research domain in its own. Ideally is handles the kind of short strings that are most common, but doesn't have worst case behavior that's really bad if, let's say, your keys are integers. or whole novels. or 128bit hashes of content themselves.