English
Menu

Data Structures and Algorithms

Keys 10, 17, 24 and 3 are stored in this order in a hash table of size 7 (positions 0 to 6) with the hash function h(k) = k mod 7. Collisions are resolved by linear probing, which moves forward one position at a time (wrapping from 6 to 0) to find a free slot. At which position is key 3 stored?

  1. APosition 3
  2. BPosition 4
  3. CPosition 6
Show answer and explanation

Answer: C. Position 6

All four keys leave a remainder of 3 when divided by 7, so each one first tries position 3. Key 10 goes into position 3; 17 finds position 3 taken and goes into position 4; 24 finds positions 3 and 4 taken and goes into position 5. Key 3 finds positions 3, 4 and 5 taken and is stored at position 6. As this shows, linear probing makes occupied positions bunch together (clustering), so keys that arrive later need more probes.

  • A. This is the hash value itself, but 10 is already there.
  • B. This is where 17 went. Position 5 after it is also taken by 24.
  • C. Correct. Positions 3, 4 and 5 are taken, so it goes into the free position 6.
Practice this topic Back to topic

Related calculators

Hash table calculatorShow the collisions and storage positions when keys are inserted into a hash table, with chaining, linear probing, quadratic probing and double hashing; also calculates the load factor and the average number of probesSorting algorithm visualizerWatch 7 sorting algorithms (bubble, selection, insertion, shell, merge, quick and heap) step by step as bar charts, and compare their comparison and write counts

Books on Data Structures and Algorithms Ad

As an Amazon Associate I earn from qualifying purchases.

More Data Structures and Algorithms questions

  1. Which correctly compares chaining (linking the elements at the same position into a linked list) and open addressing (finding another free position within the table) as ways to resolve hash table collisions? The load factor is the number of stored elements divided by the table size.
  2. Which is a prerequisite for using binary search, which compares the target with the middle element and halves the search range each time?
  3. A binary search is performed on 1,000 distinct values sorted in ascending order. If one comparison tells you whether the values are equal, smaller or larger, what is the maximum number of comparisons, counting both successful and unsuccessful searches?
  4. A binary search looks for 38 in the ascending array a[0] to a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60. The search range starts with lo = 0 and hi = 9, and the middle position is (lo + hi) ÷ 2 rounded down. Which lists, in order, the elements compared with 38?
  5. The array 5, 3, 8, 1, 4 is sorted in ascending order with bubble sort. What is the array after one pass, in which neighboring elements are compared from the front to the end and swapped whenever the left one is larger?