Representing Tables

Heaps: good for insertion, but terrible for retrieval.

Better choices: BST (especially if balanced), or B-tree, giving O(logN) insertion, deletion, and retrieval.

Hashing attempts to make these operations constant time.

Arrays provide constant time access to any position. If a key can be used as an index, we get constant time access to the data.

This is the basic idea behind a Hash Table.

Problem: using SIN as the key for student information. SINs are 9 digits long, so we need an array of size 10**9, even though there might be only 100 students.

Practical constraints:

• the set of possible keys is very large.
• the set of actual keys is quite small.
• we must use an array to get constant time operations.