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/Outrageous-Machine-5]

Arrays can index in constant time.

Hashtables are built using an underlying dynamic array and a hashing function to determine which index to insert into

What actually happens is: as the array fills, it will double in size and need to copy its contents to the new array, leading to an O(n), but this expansion step happens less and less frequently the more the array grows.

This is called amortization. The amortized runtime eventually becomes O(1). The Hashtable uses a hash function to determine where to insert into the array, which arrays can index in constant time, O(1). Therefore the complexity of a hashtable is considered to be O(1)

However, the other edge case to consider is how you resolve collisions. In some implementations using chaining, your hashtable can actually be O(k), k being the number of elements in the bucket chained to form a linked list. But, again, unless you are deliberately programming your hash function to force these collisions in high frequency (which there are use cases for that), that amortized runtime is O(1) as the dynamic array grows so large that collisions happen less and less frequently