Chapter 19 - Worked Exercises 3

Exercise 1 - Hash Sets

Part 0

1. What is a hash function?

2. What is a sparse array?

3. What is the role of a hash function and a sparse array in a hash set?

Part 1

1. Describe the steps involved in inserting a key into a hash set

2. Describe the steps involved in finding a key in a hash set

Part 2

1. What is meant by hash collision?

2. What is one solution to this problem?

Part 3

How does the performance of hash sets compare to binary search trees in terms of:

1. Performance of insertion and finding

2. Memory requirements

Review the implementation of hash sets from the previous lesson in preparation of the next lesson