1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Problem on Probability -- Hash Table & Collisions

  1. Jan 6, 2015 #1
    1. The problem statement, all variables and given/known data
    Consider a hash table with ##n## buckets, where external (overflow) chaining is used to resolve collisions. The hash function is such that the probability that a key value is hashed to a particular bucket is ##\frac{1}{n}##. The hash table is initially empty and ##K## distinct values are inserted in the table

    (a) What is the probability that bucket number 1 is empty after the the ##K^{th}## insertion ?
    (b) What is the probability that no collision has occured in any of the ##K## insertions ?
    (c) What is the probability that the first collision occurs at the ##K^{th}## insertions ?

    2. Relevant equations


    3. The attempt at a solution
    Probability that a key value is hashed to the first bucket = ##\frac{1}{n}##
    Probability that a key value is doesn't hashed to the first bucket = ##1 - \frac{1}{n}## = ##\frac{n-1}{n}##

    (a) Probability that bucket number 1 is empty after the the ##K^{th}## insertion = ##(\frac{n-1}{n})^k##
    (b) Probability that no collision has occured in any of the ##K## insertions = ##1 \times \frac{1}{n-1} \times \frac{1}{n-2} \times ... \times \frac{1}{n-(k-1)}##
    (c) Probability that the first collision occurs at the ##K^{th}## insertions = ##1 \times \frac{1}{n-1} \times \frac{1}{n-2} \times ... \times \frac{1}{n-(k-2)} \times \frac{1}{k-1}##

    are my above ans correct or I've done some mistake. Please share
     
  2. jcsd
  3. Jan 6, 2015 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Where does the last factor at (c) come from?
    Everything else looks right.
     
  4. Jan 7, 2015 #3
    Probability that no collision has occured in any of the ##K-1## insertions P(K-1)= ##1 \times \frac{1}{n-1} \times \frac{1}{n-2} \times ... \times \frac{1}{n-(k-2)}##
    Probability that the first collision occurs at the ##K^{th}## insertions = ## P(K-1) \times## Probability of collision of ##K^{th}## element
    As K-1 slots are filled, first collision will occur if ##K^{th}## element will get into these slot, It'll do it with probability = ##\frac{1}{k-1}##
    Hence
    Probability that the first collision occurs at the ##K^{th}## insertions = ##1 \times \frac{1}{n-1} \times \frac{1}{n-2} \times ... \times \frac{1}{n-(k-2)} \times \frac{1}{k-1}##
     
  5. Jan 7, 2015 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    No it does not.
    If 2 out of 100 slots are filled, then the next element won't go to a filled slot with a probability of 1/(3-1)=1/2.
     
  6. Jan 10, 2015 #5
    Would it be ##\frac{k}{n}## in place of ##\frac{1}{k-1}## in (c)
     
  7. Jan 10, 2015 #6

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Nearly. The numerator should be k-1.
     
  8. Jan 11, 2015 #7
    Oops little mistake, you are right. ##\frac{k-1}{n}## is right.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Problem on Probability -- Hash Table & Collisions
  1. Thermo Tables Problem (Replies: 1)

Loading...