Computer Science 431
Algorithms

Spring 2015, The College of Saint Rose

Home     Syllabus     Schedule

Agenda

• Announcements
  • No class Monday!
  • Exam 2 comes out Wednesday!
  • Problem Set 7: Working with Map Data [HTML] [PDF] continues
• Lecture 19 assignment recap
• A couple more problem set recap items
• Hashing
  • map/dictionary structure idea
  • hash functions: definition and some possibilities
  • some hashCode examples from Java
  • handling collisions with open addressing and external chaining

No New Lecture Assignment

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

• HashCodes