Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Probability mass function of a hash table?

  1. Jun 11, 2005 #1
    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.
  2. jcsd
  3. Jun 12, 2005 #2
    Any idea? Really stuck here. Textbook is not of any help.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook