• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Probability mass function of a hash table?

  • Thread starter KataKoniK
  • Start date
168
0
A hash table is a storage structure that calculates the storage address from a record key, k where f1(k) returns the storage address. Sometimes the hash function returns the same address for several keys (called collision). To fix this problem, a scheme called secondary hashing uses a sequence of independent hash functions f1, f2, etc. each which attempts to spread the key uniformly across the table. If f1(k) produces a collision, then f2(k) is tried and so forth. If a record insertion requires the services of hash function f1... fj to sucessfully find space for a new reocrd, it is said that we require j probes. Suppose the fraction a, (a < 1) of the table is filled when we make an attempt to store a new record. Let X be the random variable standing for the number of probes necessary to insert the new record.

What is the probability mass function of X. Find its mean and variance.

Does anyone here have a clue what values to use for X? And what the probability will be? I am clueless on what to do here. Any help would be great thanks.
 
168
0
Any idea? Really stuck here. Textbook is not of any help.
 

Related Threads for: Probability mass function of a hash table?

  • Posted
Replies
4
Views
2K
  • Posted
Replies
1
Views
2K
Replies
5
Views
4K
Replies
13
Views
5K
Replies
1
Views
4K
Replies
1
Views
5K
Replies
14
Views
5K
Replies
1
Views
5K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top