# Do all the numbers belong to same slot in the Hashtable?

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.

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

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.

• 'Uniformly distributed in the range 0 <= k < 1' Here k talks about the probability of each element to hash or something else. Thanks Nov 6, 2019 at 17:38
• 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. Nov 6, 2019 at 18:12
• Snjor, your argument means that a dice always shows the same number when you throw it. That’s not my experience. Dec 6, 2019 at 18:32
• @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. 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$$.)