What is an advantage of hashing with buckets, compared to ordinary hashing?

  • A: faster Big O
  • B: don't need to expand the table
  • C: simpler code: no collisions
  • D: A and B
  • E: B and C

    Answer: E

    Hashing with buckets uses an an array of pointers to an extra structure, such as a linked list, to store all entries that hash to a given value.

    The extra structure means we don't have to worry about collisions (there are none) or expanding the table. The Big O, formally, may be worse: O(n) instead of O(1) because it takes O(n) time to search down the linked list; with a fairly large table to hash into, though, this can be made small in practice.

    Contents    Page-10    Prev    Next    Page+10    Index