DSA - Graphs and Hashing -Q19

Question

A program that checks spelling works in the following way :  

A hash table has been defined in which each entry is a Boolean variable initialized to .A hash function has been applied to each word in the dictionary, and the appropriate entry in the hash table has been set to . To check the spelling in a document, the hash function is applied to every word in the document, and the appropriate entry in the hash table is examined. Which of the following is(are) correct?

I. true means the word was in the dictionary.

II. false means the word was not in the dictionary.

III. Hash table size should increase with document size.

(A) I only

(B) II only

(C) I and II only

(D) II and III only

Answer 1

I. true means the word was in the dictionary.

This is Not correct because True may not mean that word was in dictionary. Assume the scenario where a word w1 in the dictionary hashes to a slot m so we will set m to True. But now assume that another word w2 also hashes to slot m then we will again apply  hash  function and it will now hash to some slot n and slot n will be marked true. But observe that the word corresponding to slot n didn't make slot n true But some other word (w2) made slot n true. So, when the word corresponding to slot n comes in the document then it will hash to slot n and slot n, though is true, doesn't mean that the word was in dictionary.

II. false means the word was not in the dictionary.

This is true. Initially all entries are false and if after the hashing of all words in the hash table if still a slot is false then it means that the word was not in dictionary.

III. Hash table size should increase with document size.

Hash table size depends on the dictioanry, Not on document.

Comments

Amazing explanation Deepak