248 views

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?

1. If a word hashes to a location with value $0$, the word is not in the dictionary.
2. If a word hashes to a location with value $1$, then the word is in the dictionary.
3. If a word hashes to a location with value $2$, the word is not in the dictionary.
4. None of the above.

@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.

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.
by

### 1 comment

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.