0
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\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$
    – Rick Decker
    Apr 4, 2020 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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