edited by
491 views
1 votes
1 votes

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

1 Answer

Best answer
1 votes
1 votes
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
Answer:

Related questions

0 votes
0 votes
1 answer
2
Bikram asked Nov 26, 2016
1,637 views
Three algorithms do the same task. Algorithm One is $O(N)$ and Algorithm Two is $O(\log N)$ and Algorithm Three is $O(N1/2)$. Which algorithm should execute the fastest f...
1 votes
1 votes
3 answers
3
0 votes
0 votes
0 answers
4