English
Menu

Data Structures and Algorithms

Which is the correct description of a collision in a hash table?

  1. ABeing able to work out the original key from its hash value
  2. BDifferent keys producing the same hash value (storage position)
  3. CThe same key producing a different hash value each time the program runs
Show answer and explanation

Answer: B. Different keys producing the same hash value (storage position)

A hash table computes a storage position from the key with a hash function, allowing search, insertion and deletion in O(1) on average. Because there are far more possible keys than table slots, different keys landing on the same position (a collision) cannot be avoided. Collisions are therefore handled by methods such as chaining, which links the elements at the same position into a list, or open addressing, which looks for another free position. The same key must always produce the same hash value or lookups would fail, and whether the key can be recovered from the hash value is a property that matters for cryptographic use, not collisions.

  • A. Not being able to recover the input (one-wayness) is a property of cryptographic hash functions, which is a separate matter from collisions.
  • B. Correct. Different keys mapping to the same position is a collision, and it must always be handled somehow.
  • C. If the same key gave different values, data could not be found, so hash functions are designed not to do this.
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. 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?
  2. 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.
  3. Which is a prerequisite for using binary search, which compares the target with the middle element and halves the search range each time?
  4. 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?
  5. 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?