Computer Science 210
Data Structures
Fall 2017, Siena College
Lecture 35: Hashing; Java API; Wrapup and Looking Ahead
Date: Monday, December 11, 2017
Agenda
- Announcements
- you can even now still sign up for the party on reading day: see the
email from Dr. Flatland, send in your RSVP now, and be
there tomorrow
- Final exam review: 11:00 AM Wednesday 12/13 in RB 302
- one more reminder about course evaluations - Siena takes them
seriously. I take them seriously. So I appreciate your time in
taking them seriously.
- I will not run zyBook reports on recent assignments until
probably Wednesday, so you have a chance to finish up any you missed
- Programming Project 5: Best Of due tonight
- Lab 9: Trees due today, but no late penalty
before the final exam if you need the time
- Lab 10/Bonus: Huffman Trees due before the
final exam
- Hashing (a very brief look)
- map/dictionary structure idea
- hash functions: definition and some possibilities
- some hashCode examples from Java
- handling collisions with open addressing and external chaining
- Important Java API classes
- Class wrapup and look ahead
- Lecture 34 assignment recap (optional)
Terminology
- 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