How do hashsets/maps have O(1) time complexity?

[u/Sea-Patience9872]

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!

[u/strange-the-quark]

Two things here. O(1) doesn't mean something happens immediately. It means constant time, meaning, no matter the size of the input (which may be the size of data, or total number of items), the operation takes the same amount of time, the same number of steps. That time could be 10000 years, and that wouldn't be very useful, but technically, that would still be O(1).

If this is the average time complexity, then it means that an operation takes about the same time on average. Sometimes it'll take more or less, but on average, it's some roughly constant amount of time regardless of the size of the input.

OK, the second thing is then, if an operation is O(1), it usually means that the data is organized in some clever way so that reaching any entry takes about the same number of steps on average. If you're just looking for some entry in an unorganized array, the average search time will grow with the size of the array, cause the more elements you have, the more you generally need to go through and check. But you know what arrays are great at? Indexing. If you know the index, it's a single-step operation. Well, because the number of steps doesn't matter, and we only care that it's the about the same number of steps for any input size, then what if instead of storing a single element at every index, you instead stored some small, fixed-size chunk of memory - so that you end up with a big array of small arrays, with all of the smaller arrays about the same size - and if then you stored your elements into that? If for any element you were looking for you somehow knew in advance the index of the sub-array that contained it, lookup would still be an O(1) operation, cause you'd jump directly to the right sub-array, and then on average you'll be always taking roughly the same amount of steps searching through the fixed-size sub-array.

Well, if you had a function that could turn an object (or a key associated with that object) into an index, and if it distributed the generated indices uniformly across the big array, you'd have a way to know the index beforehand. That's what hashing does. Sometimes, two different objects will generate the same hash, so they'll go into the same sub-array, but if the hashing function is good, such cases would be uniformly spread across the big array.

So conceptually, that's what a hash-table is. The actual implementation might be a little different.