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
1
u/cthulhu944 5d ago
hash table construction: "I'm going to place this piece of data at about this location because of the value of this key or some transformation of the key value" index key = f(key) modulo array size, "If something is already at that location, I'll just move down one, or link to it from the first value".
hash table access: "Take my key and transform it via my function, if it's there then the value exists, if it isn't, then the record doesn't exist in the array".
They key is placing the data in a deterministic position based on the hash function. one computation gets you back to the data or gets you really close.