Probability mass function of a hash table?

KataKoniK

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.

Related Introductory Physics Homework Help News on Phys.org

KataKoniK

Any idea? Really stuck here. Textbook is not of any help.

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