chaining and probing are two methods used to resolve collisions in hash tables s

Question

chaining and probing are two methods used to resolve collisions in hash tables so that the amortized access time is O(1). For each of the following claims, indicate whether it is true of chaining, probing, both, or neither. (match each statement below to one of the 4 items)

1) Needs additional memory beyond the primary array for the hash table

2) Requires doubling the table periodically

3) May be either "linear" or "quadratic"

4) Crashes if the load factor becomes greater than 1

5) Requires computing th ehash function multiple times when doing an insertion

Explanation / Answer

1.) Chaining requires additional memory as it creates additional data structure to acoomodate the collision data.

2.) The table resizing is only useful when working with probing.

3.) Probing can be linear or quadratic pertaining to how we issue to find new places for collisioned hashes.

4.) Load factor can be more than 1 for chaining as we can always add new nodes. But, for open address hashing, the number of keys to be inserted should always be less than number of slots in table as we can not extend the table in open addressing and if load factor>1, it crashes since there will be no new space for the incoming hash key.

5.) Open address/ probing techniques.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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