tag

#resizing

2 pages tagged

Programming › Algorithm Cookbook › Chapter 5. Hashing and Maps ›

5.5 Rehashing

5.5 Rehashing Problem A hash table must occasionally change its capacity or internal layout. When this happens, existing entries cannot remain in their current positions because bucket indexes depend on the table size and probing rules. You need a method to rebuild the table so that all operations remain correct and performance is restored. Solution Reinsert all existing entries into a new table using the current hash function and the...

Programming › Algorithm Cookbook › Chapter 5. Hashing and Maps ›

5.4 Load Factor and Resizing

5.4 Load Factor and Resizing Problem As a hash table grows, collisions increase and operations slow down. If the table never expands, performance degrades toward linear time. If it expands too aggressively, memory is wasted and resizing costs dominate. You need a policy that keeps operations fast while controlling memory usage. Solution Track the load factor and resize the table when it crosses a threshold. load_factor = size / capacity...