Generally speaking, the cost of inserting a key into a hash table increases as the occupancy rate of the hash table increases. The following two plots give the number of probes required to insert a key into a hash table as a function of the number of keys in the table. The keys were chosen from a uniform distribution of random numbers. A total of about 20,000 keys were used. Two types of collision resolution policy are shown:
Linear probing (Note the log scale on the Y axis)
Double hashing (Note the log scale on the Y axis)
Statistics for Linear probing and Double Hashing