Re:A new fast hash table in response to Google’s new fast ha...
by nine_k on Tuesday May 29, 2018 @10:32AM
(#17179456)
> 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.
Re:A new fast hash table in response to Google’s new fast ha...
by dekhn on Tuesday May 29, 2018 @10:34AM
(#17179478)
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
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.