麻省理工学院：《算法导论》（英文版） Lecture 14 Prof charles e. leiserson

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

Example of a dynamic table 1 INSERT 2.Ⅰ NSERT 2 3. INSERT overflow c 2001 by Charles E Leiserson Introduction to Agorithms Day 24 L14.6

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 24 L14.6 Example of a dynamic table 1. INSERT 2. INSERT 11 22 3. INSERT overflow

Example of a dynamic table 1 INSERT 2.Ⅰ NSERT 2 3. INSERT overflow c 2001 by Charles E Leiserson Introduction to Agorithms Day24L14.7

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 24 L14.7 Example of a dynamic table 1. INSERT 2. INSERT 3. INSERT 2 1 overflow

Example of a dynamic table 1 INSERT 2.Ⅰ NSERT 2 3. INSERT c 2001 by Charles E Leiserson Introduction to Agorithms Day 24 L14.8

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 24 L14.8 Example of a dynamic table 1. INSERT 2. INSERT 3. INSERT 2 1

Example of a dynamic table 1 INSERT 2.Ⅰ NSERT 3. INSERT 234 4. INSERT c 2001 by Charles E Leiserson Introduction to Agorithms Day 24 L14.9

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 24 L14.9 Example of a dynamic table 1. INSERT 2. INSERT 3. INSERT 4. INSERT 4 3 2 1

Example of a dynamic table 1 INSERT 2.Ⅰ NSERT 3. INSERT 234 4. INSERT 5 INSERT overflow c 2001 by Charles E Leiserson Introduction to Agorithms Day24L14.10

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 24 L14.10 Example of a dynamic table 1. INSERT 2. INSERT 3. INSERT 4. INSERT 5. INSERT 4 3 2 1 overflow