Linear Hashing

Linear hashing is a dynamic hash table algorithm invented by Witold Litwin (1980), and later popularized by Paul Larson. Linear hashing allows for the expansion of the hash table one slot at a time. The frequent single slot expansion can very effectively control the length of the collision chain. The cost of hash table expansion is spread out across each hash table insertion operation, as opposed to being incurred all at once. Linear hashing is therefore well suited for interactive applications.

Bucket collisions can be handled in a variety of ways but it is typical to have space for two items in each bucket and to add more buckets whenever a bucket overflows. Wikipedia (opens new window)

b: bucket size d: initial size of table, according to how many binary combinations of size d there are.