Introduction to algorithms 6.046J/18,401J/SMA5503 Lecture 14 Prof charles e. leiserson
Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 14 Prof. Charles E. Leiserson
How large should a hash table be? Goal: Make the table as small as possible but large enough so that it wont overflow(or otherwise become inefficient Problem: what if we don 't know the proper size In advance ? Solution: Dynamic tables IDEA: Whenever the table overflows, grow'it by allocating(via malloc or new )a new, larger table. Move all items from the old table into the new one, and free the storage for the old table c 2001 by Charles E Leiserson Introduction to Agorithms Day 24 L14.2
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 24 L14.2 How large should a hash table be? Problem: What if we don’t know the proper size in advance? Goal: Make the table as small as possible, but large enough so that it won’t overflow (or otherwise become inefficient). IDEA: Whenever the table overflows, “grow” it by allocating (via malloc or new) a new, larger table. Move all items from the old table into the new one, and free the storage for the old table. Solution: Dynamic tables
Example of a dynamic table 1.Ⅰ NSErT 2.Ⅰ NSERT overflow c 2001 by Charles E Leiserson Introduction to Agorithms Day 24 L14.3
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 24 L14.3 Example of a dynamic table 1. INSERT 1 2. INSERT overflow
Example of a dynamic table 1.Ⅰ NSErT 2.Ⅰ NSERT overflow c 2001 by Charles E Leiserson Introduction to Agorithms Day 24 L14.4
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 24 L14.4 11 Example of a dynamic table 1. INSERT 2. INSERT overflow
Example of a dynamic table 1.Ⅰ NSErT 2.Ⅰ NSERT 2 c 2001 by Charles E Leiserson Introduction to Agorithms Day 24 L14.5
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 24 L14.5 11 2 Example of a dynamic table 1. INSERT 2. INSERT