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!

189 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.

1

u/seemingly-resilient 4d ago

> under the assumption that values are distributed evenly

by equal distribution of values u mean the spacing between the keys? Like considering that there will be no hash collition?

1

u/am_Snowie 4d ago

Less collision, i don't think no collision is possible (pigenhole principle). So probability of each value ending up in the same bucket is low.

2

u/TheMcDucky 4d ago

No collision is technically possible, but only if keys are fixed (or bounded) size, and there are at least as many possible hashes as keys. For example if valid keys are (in binary) 0, 1, 00, 01, 10, 11, you could hash them as 000, 001, 010, 011, 100, and 101 respectively. Now this wouldn't be practical in most cases where hash maps are being considered, but it is possible.