I was reading the CLRS. In the Hashing Chapter on page 262 a statement says: "For example, if we know that the keys are random real numbers $k$ independently and uniformly distributed in the range $0 \leq k < 1$, then the hash function $h(k)= \lfloor km \rfloor$."

Question: Does Uniformly distributed meant all numbers have equal probability. if so then all numbers have the same $k$ values and belong to the same slot.

  • $\begingroup$ They have the same $k$ with zero probability. $\endgroup$
    – user16034
    Nov 21, 2022 at 8:01

2 Answers 2


Keys are uniformly distributed means that they are drawn from a space with equal probability.

So if we set the hash function to be $h(k)=\lfloor{km}\rfloor$, then each given element is equally likely to hash into any of the $m$ slots. (Refer to the definition of simple uniform hashing in page 259 CLRS)

Yes, it is true that each element with key $k$ will be hashed to the same slot. But the point is the elements are chosen uniformly independently, so they have the same probability to hash to any of the $m$ slots.

  • $\begingroup$ 'Uniformly distributed in the range 0 <= k < 1' Here k talks about the probability of each element to hash or something else. Thanks $\endgroup$
    – bmchaitu
    Nov 6, 2019 at 17:38
  • $\begingroup$ Well I think it talks about the key values. The keys are chosen uniformly in the interval [0, 1]. So the prob of it being any value in this interval is equal. $\endgroup$
    – Snjór
    Nov 6, 2019 at 18:12
  • $\begingroup$ Snjor, your argument means that a dice always shows the same number when you throw it. That’s not my experience. $\endgroup$
    – gnasher729
    Dec 6, 2019 at 18:32
  • 2
    $\begingroup$ @bmchaitu In reference to your first comment above, $k$ doesn't have anything to do with probability. It is simply a real number in the interval $[0, 1)$. Probability comes in only when you decide that each value $k$ is as likely as any other. $\endgroup$ Apr 4, 2020 at 19:38

Your conclusion "then all numbers have the same $k$ values" is not justified. The samples are anywhere in $[0,1)$ and can fall in any slot.

Uniformly means that in the long run, all slots will be filled in a balanced way. (The $\text{pdf}$ of $k$ is continuous and constant. The expectation of the filling of any bin is $\dfrac nb$ for $n$ drawings and $b$ bins. In other words, the probability to fall in a given bin is $\dfrac1b$.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.