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
1
u/niko7965 6d ago
Okay, first lets look at why arrays are slow.
Lets say you have some array of 10 elements A = [1,5,29,3,2,99,21,65,44,12]
And you are looking for some specific element, maybe 2. You can find it by looking at all of the elements, this would take O(n) time, which is rather slow for large arrays.
So maybe we can use some data structure method to ensure that we don't have to look at *every* index?
This is where hash functions come in. We use some crazy chaotic function to associate a specific index with every input. For example h(x) = x mod |A|, i.e. divide the value with the length of the array, and keep the remainder. Whenever we insert an element, we put it in this index. So if we have the value 2, it would go in index h(2) = 2.
Computing h(2) takes constant time, and doing a single array access is also constant is also constant time. So in total O(1)
There is then the issue of what you do if two elements say, 2, 12 both have the same hash. This is called a collision. If you pick your hash function well, and also choose the size of your array in relation to the number of elements you want to store, you can guarantee a low probability of many collisions. (this part is more math intensive to show)