in Programming edited by
248 views
1 vote
1 vote

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.
in Programming edited by
by
248 views

3 Comments

@Bikram sir I am not geeting the answer, could you please explain the solution
0
0
@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.
2
2

@Bikram Sir please provide the solution.

0
0

1 Answer

1 vote
1 vote
Best answer
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.
selected 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.
2
2
Answer:

Related questions