Keeping the load factor (fullness) λ < 0.7 in a hash table:

  • A: means there usually are no collisions
  • B: keeps the number of collisions fairly small on average
  • C: wastes between 1 / 3 and 1 / 2 the table space
  • D: requires use of quadratic probing
  • E: B and C

    Answer: E

    With λ < 0.7 there will be some collisions (about 1 on average), but this can be considered to be constant-time. Keeping the table less than 0.7 full means we are wasting 0.3 of the space at least, basically between 1 / 3 and 1 / 2.

    Contents    Page-10    Prev    Next    Page+10    Index