Hash tables：練習問題

A hash table has 10 slots (indexed 0 to 9) and uses the hash function \(h(k) = k \text{ mod } 10\). If linear probing is used for collision resolution, where will the key 25 be stored if keys 5, 15, and 35 are already in the table in that order?

A hash table is implemented using chaining with linked lists to resolve collisions. The hash function is \( h(k) = k \text{ mod } 10 \). If the keys 14, 24, 34, and 44 are inserted into an empty table, what is the time complexity to search for the key 44 in the resulting data structure in the worst-case scenario, assuming the list at each index is not ordered?

A hash table with 100 slots uses linear probing. After many insertions and deletions, the table suffers from primary clustering. Which of the following best describes the impact of primary clustering on the table's performance and the most effective way to mitigate it using the syllabus concepts?

A hash table is used to store data. If the table currently contains the values 11, 22, and 33 at their hashed indices, and a new value is being inserted that hashes to an index already occupied by 22, what is the term for this occurrence, and which technique involves finding the next available slot?

A hash table uses a hash function \(h(k)\). If the load factor \(\alpha\) is defined as \(\frac{n}{m}\) (where \(n\) is the number of entries and \(m\) is the number of slots), which statement regarding collisions is most accurate?

A hash table uses the function \( h(k) = k \text{ mod } 11 \). If the keys 12 and 23 are already present, what specific term is used to describe the situation when attempting to insert the key 34?

A hash table is designed to store exactly 100 items. Explain the specific risk of using a static hash table versus a dynamic hash table in a system where the number of entries frequently exceeds initial estimates.

Consider a hash table using chaining with linked lists. If the hash function \( h(k) \) maps all keys to the same index, explain the resulting effect on the efficiency of data retrieval.

A company is designing a new file storage system. They decide to use a hash table of size 13 (indices 0 to 12) with the hash function \( h(k) = k \text{ mod } 13 \).

(a) The following keys are inserted in this order: 25, 38, and 12. State the index for each key.
(b) A fourth key, 51, is now inserted. Explain why a collision occurs and, using linear probing, determine the final index where 51 will be stored.
(c) The developers are considering rehashing. Explain the circumstances under which rehashing would be triggered and how the process is performed.

A hash table of size 11 (indices 0 to 10) uses the hash function \(h(k) = k \text{ mod } 11\). The table currently contains the following keys:
Index 1: 12
Index 5: 16
Index 6: 28

(a) A new key, 39, is to be inserted. Calculate its initial hash index and describe the collision that occurs.
(b) Using linear probing, determine the final index where 39 will be stored.
(c) Explain the difference between linear probing and chaining as collision resolution strategies.