hash table insertion probability

Discussion in 'Homework Help' started by zulfi100, Jul 1, 2013.

  1. zulfi100

    Thread Starter Member

    Jun 7, 2012
    320
    0
    Hi,
    Kindly guide me with the following question:

    Zulfi.
     
  2. Papabravo

    Expert

    Feb 24, 2006
    10,140
    1,790
    So what is your initial approach to the problem?
    How many empty spots are there in the table?
     
    Last edited: Jul 1, 2013
  3. WBahn

    Moderator

    Mar 31, 2012
    17,743
    4,790
    Which hash values will result in something being stored in location #2?

    You won't get much more help unless you show some attempt to work the problem yourself.
     
  4. zulfi100

    Thread Starter Member

    Jun 7, 2012
    320
    0
    Hi,
    Thanks for your response.
    Actually I dont have any idea how to solve this. Thats why i have posted this question on the forum.
    Empty spots are: 2, 5, and 6. If we use equal chance then the probability can be .33.

    They have not specified their hash function. If its remainder hashing function then, numbers having 2 at the end can go in this location. I cant understand why there is no record in 0th position.

    Zulfi.
     
  5. WBahn

    Moderator

    Mar 31, 2012
    17,743
    4,790
    If that's truly the case -- that you don't have the faintest idea how to even start this problem -- then the problem is too far beyond you right now for you to even be attempting it. You need to step down to much simpler problems that will lead you toward being able to have an idea of where to at least start on a problem like this.

    But why would you assume an equal chance for each slot getting used?

    It doesn't matter what hash function they use as long as the hash function results in essentially equal probability of each possible result.

    But what happens if there is a hash collision?

    Let's say that the hash of the new item comes out to be 1. Where will that item get stored? It can't get stored in location 1 since there is already something there. Not storing it at all is not an option because you have room to store it, so it has to be stored somewhere.

    What does it mean when it says, "with a hash function resolve crash by linear probing"?

    You don't have a location 0. You have ten locations and they are obviously numbered 1 through 10.

    Make a table with 10 rows. Each row is one possible hash of the next record to be stored. For each hash, what location will the record be stored in.

    hash location
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10


    Each row has to map to one of the available locations.

    Of the ten possible hash outcomes (which are assumed to occur with equal probability), how many map to location 2?
     
  6. zulfi100

    Thread Starter Member

    Jun 7, 2012
    320
    0
    Hi,
    Thanks for your reply. I have studied hashing but i cant develop the logic to solve this. I am fully conversant with the terms used in this question viz: hashing function, linear probing, and collision resolving technique. But i have not worked with probability. If i get solution to this problem i would understand this concept.
    Considering the remainder hashing function and keys:56,58, 59, 62, 63, 64, 65, following situation would arise after inserting the above values in the table using:
    hashing function=key%11
    1|56
    2|
    3|58
    4|59
    5|
    6|
    7|62
    8|63
    9|64
    10|65

    For 2 we can have a key of 55
    Of the 10 possible outcomes, only the outcome which has remainder=2, can go to location 2.
    Linear probing means that if the array index is occupied we will check index+1 or index+2 and so on for availability
     
  7. WBahn

    Moderator

    Mar 31, 2012
    17,743
    4,790
    How many possible outcomes does key%11 have?

    Why would you use that modulus if you only have ten locations?

    Let's make this really simple.

    You have 100 possible locations but 99 of them are already in use with location 42 being the only one that is free.

    Q1) Regardless of what the key is on the next record, where will it be stored?

    Q2) What is the probability that the next record will be stored at location 42?

    Now let's change it so that there are two locations that are free, namely 42 and 44.

    Q3) If the next record has a key that would normally put it into location 40, which location will it actually end up in?

    Q4) If the next record has a key that would normally put it into location 43, which location will it actually end up in?

    Q5) If the next record has a key that would normally put it into location 45, which location will it actually end up in?

    Q6) Of the 100 possible normal locations, how many of them will actually end up in location 42 and how many of them will actually end up in location 44?
     
  8. zulfi100

    Thread Starter Member

    Jun 7, 2012
    320
    0
    Hi,
    Thanks for your reply. I would try to answer your questions.

    0..10

    Yes, you are right, this is not a good hashing function for this case.

    42. Because its the only free location
    If we are using resolving collision using linear probing then at last record would be stored at 42. Probability is 100%.

    Using linear probing (step size=1)it would go to 42.
    Using linear probing, it would go to 44.
    42. Following shows an example where if we reach end of array, we will start again from zero.
    https://www.cs.washington.edu/education/courses/326/00wi/handouts/lecture16/sld015.htm
    More chances for location 42. i.e. Outcomes 1 to 41 and then from 45 to 100 will store the element in location 42 (41+55+1=97 outcomes will store the val. On the other hand if the outcome of hashing function is 43, it would go to 44 only (only two outcomes). I dont know why one outcome is missing? Thanks for your guidance. But still i need your help to solve my problem.

    Zulfi.
     
  9. WBahn

    Moderator

    Mar 31, 2012
    17,743
    4,790
    Because you have a fence post error.

    How many outcomes, inclusive, are there between 45 and 50? It is NOT (50-45)=5.

    You shouldn't. Just apply the same line of reasoning you used above on your problem and ask which outcomes will end up in each available location.
     
  10. zulfi100

    Thread Starter Member

    Jun 7, 2012
    320
    0
    Hi,
    Thanks for providing me good insight about this problem.
    Okay my solution is:
    For outcomes, 7, 8, 9, 10, 1, 2 (total=6)there are chances for a new record to go into the position 2. So probability is 0.6.

    Kindly let me know about the correctness of this.

    Zulfi.
     
  11. WBahn

    Moderator

    Mar 31, 2012
    17,743
    4,790
    Yes, that is correct.

    The table I was trying to get you to write back in post five was:

    hash location
    1 2
    2 2
    3 5
    4 5
    5 5
    6 6
    7 2
    8 2
    9 2
    10 2
     
  12. zulfi100

    Thread Starter Member

    Jun 7, 2012
    320
    0
    Thanks for a very good help session.

    Zulfi.
     
  13. WBahn

    Moderator

    Mar 31, 2012
    17,743
    4,790
    Glad you found it helpful.
     
Loading...