We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
To make a true hash set for the entire range of 32-bit integer you need to spend 2^32 space. You can make a hash of say (2^32 / 10000) size, which will then give you worst-case search performance O(10000). But technically it's still O(1). So I think you are correct, but this is one of these cases where theory and real world differ a lot.
Pairs
You are viewing a single comment's thread. Return to all comments →
To make a true hash set for the entire range of 32-bit integer you need to spend 2^32 space. You can make a hash of say (2^32 / 10000) size, which will then give you worst-case search performance O(10000). But technically it's still O(1). So I think you are correct, but this is one of these cases where theory and real world differ a lot.