>Hashtable analyses don't care how you get the hash function - it can take exactly 72 hours to arrive, but as long as the oracle satisifes some probability distribution guarantee, it's good. That is an O(1) operation, a single hash.
The problem is that, as n goes to infinity, you're not using the same hash function -- you can't. So even if you can assumed that one hash function has constant time, the later ones you need as you scale up wouldn't be.
And I don't know why you think you need to bring up probability distribution properties -- I made clear by now that the above points apply even to the mythic perfect hash function.
>Hopefully I've explained it better. Different models of computation are a fundamental part of theoretical computer science, since of course,
And it's fine to use different models! It's not fine to silently switch between them in an ad hoc way, which is what's necessary to make the exceptions that get you O(1) lookup for hashtables. I have never seen anyone expect the relevant caveats when quizzing coders for the correct answer on that question. That makes this part of computer science more like memorization or stamp collecting than a genuine mathematical model from which you consistently derive answers.
The problem is that, as n goes to infinity, you're not using the same hash function -- you can't. So even if you can assumed that one hash function has constant time, the later ones you need as you scale up wouldn't be.
And I don't know why you think you need to bring up probability distribution properties -- I made clear by now that the above points apply even to the mythic perfect hash function.
>Hopefully I've explained it better. Different models of computation are a fundamental part of theoretical computer science, since of course,
And it's fine to use different models! It's not fine to silently switch between them in an ad hoc way, which is what's necessary to make the exceptions that get you O(1) lookup for hashtables. I have never seen anyone expect the relevant caveats when quizzing coders for the correct answer on that question. That makes this part of computer science more like memorization or stamp collecting than a genuine mathematical model from which you consistently derive answers.