Open addressing needs a fixed amount of memory, but:

• RETRIEVE is very inefficient when the key isn't in the table.

• Amount you can store is limited by the size of the table.

• As the load factor gets large, all operations degrade to linear-time.

Chaining: each position contains a collection of values of unlimited size.

To insert a value with key K, add it to the collection in position H(K).

When collections are implemented by linked lists, INSERT is constant time, but DELETE and RETRIEVE are linear in the number of values in the chain.

Collections can be implemented by more efficient data structures, e.g. B-trees.