ITPEC FE Morning October 2022 Question 9

A function of the key gives the storage location — that defines the hash method.

A hash function computes an address directly from the key, so a record is stored at, and later found at, the address h(key). No comparisons along a list or tree are needed, and search time stays roughly constant however large the table grows. Two keys can hash to the same address, a collision, which is handled by chaining or open addressing.

Answer (a)

Why not others:

• •(b) — hashing does not avoid collisions; different keys can map to the same address, and the method needs a way to resolve them
• •(c) — binary tree search stores keys in a tree ordered by value, a different method
• •(d) — time proportional to the table size describes linear search; hashing is close to constant time on average

Key rule: Hashing turns a key into an address by calculation, so search time does not depend on the number of entries, but collisions must be planned for.

Algorithm and Programming · AI-written, may contain errors