2
$\begingroup$

I am wondering if Hash tables would be a good choice as it mentions dynamic sets to store data which follows normal distribution. I have doubt in this because normal distribution has bell shaped curve which means elements near the median are more than others. So, If I use hash table then that would lead to clustering.

So, any insights regarding this would be helpful.

Edit: Common operations on a dynamic set are Find,Insert, Delete, and also analysing what are the complexities for each operation.

Improve this question
$\endgroup$
2
  • $\begingroup$ I don't think you've provided enough information to provide useful answers. Please edit the question to tell us what operations you want the data structure to provide, what your requirements are, and what approaches you've considered and your analysis of them. You say "it mentions"; what mentions that? If you're referring to some source, please cite the source and summarize what it says. $\endgroup$
    – D.W. ♦
    Commented May 18, 2021 at 19:08
  • $\begingroup$ I aint referring to any other source. And the question "itself mentions" dynamic set. And the basic operations on dynamic sets are like Find, Insert, Delete operations. $\endgroup$
    – Yukti Kumari
    Commented May 19, 2021 at 4:08

2 Answers 2

Reset to default
1
$\begingroup$

A hash function might not map the nearby elements to the same bucket. For example suppose the hash function is $h(x) = x^2 \mod p$ where $p$ is some prime number say $97$. Suppose $x$ follows normal distribution with values between $1$ to $1000$. And, suppose that most of the values are concentrated around $500$. If you compute the hash values at $x = 499$, $x = 500$, and $x = 501$, the hash function gives the following values: $h(499) = 2$, $h(500) = 31$, and $h(501) = 62$. Note that, although the input values are close to each other, their mapped values are not close to each other and they lie in completely different buckets.

Designing a good hash function that uniformly maps the values across the table, mostly depends on a particular use case. But, you can always make your hash function more complex by adding more terms to it, for example, by adding more terms of the form $x^k$ to it, etc. It will hopefully provide a uniform spread of values across the table.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It cleared my doubt. Thnx $\endgroup$
    – Yukti Kumari
    Commented May 19, 2021 at 4:06
1
$\begingroup$

A 64 bit hash for 64 bit Floating-point numbers will more or less be just the bit pattern of the number; “more or less” because you need to handle +0 and -0, and you have to decide how to handle NaNs.

The index of a slot in the hash table is that hash, modulo the table size, which is likely a prime number. That index will be practically random; whether your Floating-point numbers have some distribution is not going to make any difference.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Ok. I also want to know that if the knowledge of the distribution of data can help us in choosing hash functions which guarantees uniform distribution of data in hash table. $\endgroup$
    – Yukti Kumari
    Commented May 19, 2021 at 11:37
  • 1
    $\begingroup$ Never seen any example of that. You have a 52 bit mantissa, and many of the bits are not affected by the distribution, and that’s enough to create a good hash. $\endgroup$
    – gnasher729
    Commented May 20, 2021 at 5:34
  • $\begingroup$ Thanks for the insight. $\endgroup$
    – Yukti Kumari
    Commented May 20, 2021 at 6:55

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.