Hi,
Kindly guide me with the following question:

A hash table can store a maximum of 10 records. At present there are records in location 1, 3, 4, 7, 8, 9, 10. What is the chance of a new record going into location 2, with a hash function resolve crash by linear probing?

Zulfi.

 

So what is your initial approach to the problem?
How many empty spots are there in the table?

 

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.

 

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.

How many empty spots are there in the table?

Empty spots are: 2, 5, and 6. If we use equal chance then the probability can be .33.

Which hash values will result in something being stored in location #2?

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.

 

Actually I dont have any idea how to solve this.

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.

Empty spots are: 2, 5, and 6. If we use equal chance then the probability can be .33.

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

They have not specified their hash function. If its remainder hashing function then, numbers having 2 at the end can go in this location.

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"?

I cant understand why there is no record in 0th position.

Zulfi.

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?

 

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

 

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?

 

Hi,
Thanks for your reply. I would try to answer your questions.

How many possible outcomes does key%11 have?

0..10

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

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

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?

42. Because its the only free location

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

If we are using resolving collision using linear probing then at last record would be stored at 42. Probability is 100%.

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?

Using linear probing (step size=1)it would go to 42.

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

Using linear probing, it would go to 44.

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

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

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?

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.

 

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.

Because you have a fence post error.

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

But still i need your help to solve my problem.

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.

 

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.

 

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

 

Thanks for a very good help session.

Zulfi.

 

Glad you found it helpful.