1.  Why use hashing, considering that instead we can just place all the elements in an array?  Be brief, but as precise as possible.

2.  What are the three properties of a good hash function?

3a.  Two ways to deal with collisions are chaining and probing.  Briefly explain how each works.

3b.  Which of these two methods is preferable for a heavily-populated hash table, and why?

4a.  What is quadratic probing?

4b.  What is the problem with linear probing which is at least partly fixed by quadratic probing?

5.  Assume that N words are inserted into a data structure.  Then, assume we check if a word is in the data structure M times, and that M/2 of those times it is in the data structure, and M/2 of those times it is not in the data structure.  Give the average expected cost -- in Big-O notation -- for the total N+M operations for the following data structures:

5a.  Hash table (assume an optimal hash function with chaining).
5b.  Unsorted linked list
5c.  Sorted linked list
5d.  Unsorted array
5e.  Sorted array

Good luck!