Dynamic Resizing
To keep the load factor under a certain limit, e.g. under 3/4, many table implementations expand the table when items are inserted. For example, in Java's HashMap class the default load factor threshold for table expansion is 0.75.
Since buckets are usually implemented on top of a dynamic array and any constant proportion for resizing greater than 1 will keep the load factor under the desired limit, the exact choice of the constant is determined by the same space-time tradeoff as for dynamic arrays.
Resizing is accompanied by a full or incremental table rehash whereby existing items are mapped to new bucket locations.
To limit the proportion of memory wasted due to empty buckets, some implementations also shrink the size of the table—followed by a rehash—when items are deleted. From the point of space-time tradeoffs, this operation is similar to the deallocation in dynamic arrays.
Read more about this topic: Hash Table
Famous quotes containing the word dynamic:
“We Americans have the chance to become someday a nation in which all radical stocks and classes can exist in their own selfhoods, but meet on a basis of respect and equality and live together, socially, economically, and politically. We can become a dynamic equilibrium, a harmony of many different elements, in which the whole will be greater than all its parts and greater than any society the world has seen before. It can still happen.”
—Shirley Chisholm (b. 1924)