Search code examples
cdata-structureshashtable

Hash Table using quadratic probing question

I've attached a screenshot of the question I'm not sure about. Why would the string "Banana" % 13 go to spots 8 and 9?

I didn't really try anything other than mod 13 in each spot and since it's going to just equal itself it could go in any spot.enter image description here

Solution

  • The information you need to use is that quadratic probing is used to resolve hash collisions.

    Assuming quadratic probing in your lecture is defined as follows:

    i := Number of attempts (with 0 being the first attempt)
s := string you need to insert
Position(s, i) = (hash(s) + i²) mod 13 // Maps a string and a number of attempts to a position within the hash table

    You can systematically exclude hash value as impossible hash values, because there are only two possibilities:

    1. The position you want to place it is not occupied: this would mean you could place banana there. But, as already explained in the question, banana did end up in spot 12, so in any other position than 12 this could not possibly have been the case, otherwise banana would be placed at that position, not at position 12. => this rules out 1, 4, 7 and 11 to be possible hash values of banana

    2. The position you want to place it is already occupied: in that case you would use quadratic probing to find the next suitable position, where you have again those two possibilities: occupied or not occupied. Now it's just a matter of systematically excluding impossible positions:

    I am starting from the front:

    • Position 0: Is occupied by another word than banana => there must have been a collision if the hash value of banana was 0 => we then would try position (0 + 1²) mod 13 = 1. This position is not occupied, meaning banana would have been placed there if the hash value was 0. It isn't, so we can rule out 0. You can apply the same logic to possible hash values 3, 6 and 10 which rules them out as well.

    • Position 2: Is occupied by another word than banana => there must have been a collision if the hash value of banana was => we then would try position (2 + 1²) mod 13 = 3. This position is also occupied. => we try (2 + 2²) mod 13 = 6. 6 is also occupied. => we try (2 + 3²) mod 13 = 11. This position is not occupied, meaning banana would have been placed there if the hash value was 2. It isn't, so we can rule out 2.

    • Position 5: Is occupied by another word than banana => there must have been a collision if the hash value of banana was 5 => we then would try position (5 + 1²) mod 13 = 6. This position is also occupied. => we try (5 + 2²) mod 13 = 9. 9 is also occupied. => we try (5 + 3²) mod 13 = 1. This position is not occupied, meaning banana would have been placed there if the hash value was 5. It isn't, so we can rule out 5.

    • Position 8: Is occupied by another word than banana => there must have been a collision if the hash value of banana was 8 => we then would try position (8 + 1²) mod 13 = 9. This position is also occupied. => we try (8 + 2²) mod 13 = 12. 12 is also occupied, but by the word banana. => banana could have had a hash value of 8

    • Position 9: Is occupied by another word than banana => there must have been a collision if the hash value of banana was 9 => we then would try position (9 + 1²) mod 13 = 10. This position is also occupied. => we try (9 + 2²) mod 13 = 0. 0 is also occupied. => we try (9 + 3²) mod 13 = 5. 5 is also occupied. => we try (9 + 4²) mod 13 = 12. 12 is also occupied, but by the word banana. => banana could have had a hash value of 9

    • Position 12: Trivial and already tackled in the question.