I am trying to understand the assumption of Simple Uniform Hashing (SUHA) as e.g., in CLRS textbook; or other courses about hashing.
The usual description given to SUHA is (cf. CLRS):
"we shall assume that any given element [i.e., key] is equally likely to hash into any of the m slots, independently of where any other element has hashed to. We call this the assumption of simple uniform hashing."
However this is quite informal, and thus I don't fully understand it. My understanding is that the assumption supposedly means that
$ Pr[h(k)=\ell]=1/m\,$, for any given key $k$ and slot in the table $\ell=0,\ldots,m-1$, where $m$ is the number of slots in the table. But since given a key $k$ the deterministic hash function $h$ is fixed on $k$, there is no probability distribution here!
Perhaps it is meant here that $k$ is a random variable distributed uniformly over all keys?
Question: what is the distribution the probability $ Pr[h(k)=\ell]=1/m\,$ is defined over in SUHA?
My understanding is the SUHA is an (idealized) assumption that formally means that the probability $Pr[h(k)]$ is the probability of the event of inserting a key to the table nevertheless the time of insertion (it might be the first key I insert or the last one).
In other words, the sample space of probability $\Omega$ is
$\Omega:=($the set of all [ordered] sequences of insertions to the hash table$)$.
The probability event $h(k)=\ell$ is thus the set of all [ordered] sequences of insertions to the hash table in which the $n+1$th insertion hashes to $\ell$, where $n+1$ is the ``current'' insertion that I'm analyzing and where $n$ is the current number of keys in my hash table.
In SUHA we shall also assume that $h(k)=\ell$ for every $n$ (the current position of insertion in the sequence); namely, we assume that the event $h(k)=\ell$ is completely independent of the sequence.
To sum up the answer: the probability $Pr[h(k)=\ell]$ is taken over all possible ordered sequences of insertions to the hash table.