Comment by nine_k
8 years 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.
I'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