ITPEC FE Morning October 2019 Question 7
In a table search, which of the following is a characteristic of the search technique known as hashing?
Explanation
A function of the key gives the storage location — that defines hashing.
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 (c)
Why not others:
- •(a) — hashing does not avoid collisions; different keys can map to the same address, and the method needs a way to resolve them
- •(b) — 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
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.