2 ms·
> can any hash table whose hash function operates over the entire string ever show O(1) time? If we limit the length of the has key, the time taken by the hash
by nine_k 8y ago
> can any hash table whose hash function operates over the entire string ever show O(1) time?
If we limit the length of the has key, the time taken by the hash function is also limited and turns into a constant. Big-O is all about asymptotic behavior.
OTOH noticing how the hash function's run time depends on the size of the key can be separately useful. I suspect all such functions are linear in practice, though.
- dekhn 8y agoI'm talking about functions where the entire string is used to that's necessary on the internet when dealing with billions of strings that are similar to each other