The national park booking service stores campsite availability in a hash table with 101 buckets. A booking record contains a reservation code, arrival date,...
Question 1 Report
The national park booking service stores campsite availability in a hash table with 101 buckets. A booking record contains a reservation code, arrival date, number of nights and payment status. The hash function is based on the numeric part of the reservation code. During a holiday period, many codes map to the same bucket and the response time of the search command has become variable. The programmer is considering separate chaining, open addressing and resizing the table. The service must keep all confirmed bookings and must not lose a record if two codes have the same hash value.
(a) Explain what is meant by a collision in this hash table. [2]
(b) When separate chaining is used, explain how a search for one reservation code is carried out. [3]
(c) Explain two effects of a high load factor on this system. [3]
(d) When the table is resized, explain why every existing record normally has to be processed again. [2]
(e) Explain one reason that a booking record should include payment status as a field rather than using a separate unrelated list. [2]
Answer Details
(a) A collision occurs when two different reservation codes produce the same hash-table index. Both records must then be stored without one overwriting the other. [2]
(b) To search using separate chaining:
- Calculate the hash index for the required reservation code.
- Go to the linked list, or chain, stored at that bucket.
- Compare reservation codes along the chain until the required code is found or the chain ends.
[3]
(c) A high load factor means there are many records relative to the number of buckets. This causes more collisions and makes chains or probing sequences longer. Consequently, searches and insertions take longer or have less predictable response times. [3]
(d) Resizing changes the table size. Each existing key must be hashed again because its resulting index may change in the new table. [2]
(e) Including payment status in the booking record keeps it associated with the correct reservation. The whole booking can be retrieved and updated together, reducing the risk of mismatches with a separate unrelated list. [2]
Download The App On Google Playstore
Everything you need to excel in your exams
