Hashing

Question 1

How does chaining work in terms of hashing?

Answer 1

• Chaining is a Collision Resolution Policy (CRP)
• if a location is full, add items to a linked list.
• Performance degrades if load factor is high and the linked lists become long.
• Lookup time is, on average, 1 + λ (1 to find bucket, average of λ to go through linked list).
• Like a BST, performance can degrade to O(n), plus linked lists add list pointer data and will
  not balance distribution among buckets.
• Performance can be poor but implementation is simple and hash table can’t become full.

Question 2

List some Collision Resolution Policies

Answer 2

Chaining

Linear Probing / Open addressing

Quadratic Probing

Double hashing

Question 3

Disadvantage of linear probing?

Answer 3

■ One big disadvantage is that this leads to the formation of clusters with no empty
spaces.

■ Performance can degrade to a linear scan.

■ Hash table can become FULL.