Hash Tables
 Consider chaining as a collision strategy. What is the best possible worst case behaviors for insertion and finding, respectively?

constant, linear

constant, constant

constant, linear

linear, linear

linear, quadratic

quadratic, linear
 Consider open addressing as a collision strategy. What is the best possible worst case behaviors for insertion and finding, respectively?

linear, linear

constant, linear

linear, constant

constant, constant

linear, quadratic

quadratic, linear
 Consider rehasing with a perfect hash as a collision strategy. possible worst case behaviors for insertion and finding, respectively?

linear, constant

constant, linear

constant, constant

linear, linear

linear, quadratic

quadratic, linear
lusth@cs.ua.edu