Computer Science 210
Data Structures
Fall 2018, Siena College
Lecture 35: Heapsort; Hashing
Date: Friday, December 7, 2018
Agenda
- Announcements
- Reminder: zyBook Chapters 17 and 18 by tonight
- Lab 9: Trees submit now if you have not already
- Problem Set 6 grading in progress
- Problem Set 7 due Monday: no late submissions!
- RSVP for and come to the Reading Day party
- vote in the poll for a final exam review time if you are interested in attending
- please complete course evaluations for the lecture sections: quiz bonus points for everyone if we get to 95% participation
- Final exam sample questions and study guide out
- Quick thoughts on last Lab 10: More Trees questions
- Quiz 5 recap
- Heapsort
- Hashing (a very brief look)
- hash functions: definition and some possibilities
- some hashCode examples from Java
- handling collisions with open addressing and external chaining
Terminology
- heapsort
- hashing
- perfect hashing function
- hashing function
- home address
- hash collision
- open addressing/closed hashing
- external chaining/open hashing/separate chaining
- rehashing
- linear probing
- clustering: primary and secondary
- quadratic rehashing
- double hashing
- load factor
Examples