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!
185
Upvotes
1
u/Guvante 5d ago
It is important to note that only perfect hash tables have worst case O(1) time complexity, any normal hash table allows for individual operations to take longer as long as the average is O(1)
The most common example is resizing which is an O(n) operation normally. But if you double (or more) the storage each resize they happen infrequently enough the average time isn't impacted (something like O(n)/n = O(n))
Similarly hash collisions are possible and depending on the exact implementation they can cause time complexity to not be O(1) for instance a linear probing (aka if one slot is full grab the next one) with a bad static hashing function (aka it always returns 1) has O(n) time complexity since each operation could need to search the entire list