Computer Science 15-111 (Sections A & B), Spring 2007

Class Notes: 06-Apr-2007

Logistics:

1. Quiz 7 is Wednesday
Covers Trees, Binary Trees, Binary Search Trees, Expression Trees, Maps, HashMaps, TreeMaps, Sets, HashSets, TreeSets,

2. Test 2 is Wednesday April 18^th (12 days from today). It is comprehensive.

3. Call for hw8 Partners (email me asap)

4. Reminder: Read your email for hw8 Q&A’s!!!

Topics:

1. Review previous class topics on Trees

2. Hashing

a. Definition of a hashtable (using linear chaining)

i. Buckets of linked lists of unsorted nodes

ii. Index = hashCode() % hashtableSize;

b. Use of Object.hashCode()

i. What makes a good hash function?

c. When to rehash

d. Cost of operations (assuming worst-case length of linked lists is constant)

i. Insert = O(1)

ii. Remove = O(1)

iii. What about resizing?

1. O(N), but occurs ~1/N times, so does not change amortized cost.

e. HashMap versus HashSet

i. Implement HashMap

ii. For HashSet, just use a HashMap where the keys are important, mapped values are irrelevant.

3. hw8 hints and discussion