Describe this For tables implemented using probing, sometimes quadratic probing

Question

Describe this For tables implemented using probing, sometimes quadratic probing is used. method Suppose a programmer has to write a spell checker application. will be stored in a hashtable. For the hash method, the programmer decides to sum the ascii codes of the characters for each word. He reasons that since each word is distinct (no dups), this method will generate a unique hash for each word. Is his reasoning correct? 6. 7. The words in the dictionary Hashtables do not keep data ordered by keys. Suppose that you are required to write the following method for a hashtable that uses chaining: 8. This makes some operations more difficult. public object [1 getRange (string first, string last) This method returns an ordered array of all keys in the table that fall within the range first..last inclusive. Your method must be as efficient in terms of time and storage complexity as possible. Describe how you might implement the method.

Explanation / Answer

Hi Dear,

I have answered Q6.

Please repost others in separate post.

Quadratic Probing We look for i^2 th slot in i’th iteration.

let hash(x) be the slot index computed using hash function.
If slot hash(x) % S is full, then we try (hash(x) + 1*1) % S
If (hash(x) + 1*1) % S is also full, then we try (hash(x) + 2*2) % S
If (hash(x) + 2*2) % S is also full, then we try (hash(x) + 3*3) % S

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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