Test by Bikram | Data Structures | Test 2 | Question: 14

Question

If memory is limited and the entire dictionary cannot be stored in a hash table, we can still get an efficient algorithm that almost always works. We declare an array H_TABLE of bits (initialized to zeros) from $0$ to TABLE_SIZE $– 1$. As we read in a word, we set H_TABLE[hash(word)] $= 1$. In this scenario, which of the following is true?

• A. If a word hashes to a location with value $0$, the word is not in the dictionary.
• B. If a word hashes to a location with value $1$, then the word is in the dictionary.
• C. If a word hashes to a location with value $2$, the word is not in the dictionary.
• D. None of the above.

Comments

@Bikram sir I am not geeting the answer, could you please explain the solution

---

@shiveshRoy option A is false because if a word hashes to location value 0, it may also be possible that the word is not read yet and not just that it is not present.
So, option B is the answer. As it hashes to location with value 1 only when the word is in the dictionary.

---

@Bikram Sir please provide the solution.

Answer 1

option B is the answer.

As it hashes to location with value 1 only when the word is in the dictionary.

option A is false because if a word hashes to location value 0, it may also be possible that the word is not read yet and not just that it is not present.

Comments

But it's not mentioned in the question that the hash function is one-one, i.e. there is no guarantee that more than one word can have the same hash value.