If memory is limited and the entire dictionary cannot be stored in a hash table,

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 a table of boolean (initialized to false) from 0 to Tablesize - 1. As we read in a word, we set table [hash(word)] = true. Which of the following is time? (a) If a word hashes to a location with value that is false, the word is not in the dictionary. (b) If a word hashes to a location with value that is true, the word Ls in the dictionary. (c) Suppose we choose Tablesize = 200,007 How much memory does this require? Assume that each boolean element takes up 1 bit of memory. (d) What is the probability that thus scheme will not report a misspelled word?

Explanation / Answer

(a ) and (b) both are true.

(c) total memory require = 200007 * 1 = 200007 bit

(d) 1/2

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.