Computer Science 210
Data Structures

Fall 2016, Siena College

Home     Syllabus     Schedule     Examples     Style Guide

Agenda

• Announcements
  • don't forget to complete course evaluations
• Practice final exam out
• Lecture 35 assignment recap
• Quick Lab Practical recap
• Hashing
  • map/dictionary structure idea
  • hash functions: definition and some possibilities
  • some hashCode examples from Java
  • handling collisions with open addressing and external chaining

Lecture 37 Assignment

Due at the start of class, Tuesday, December 13.

Please submit answers to these questions by the start of class. zyBook activities should be done right in your zyBook, and all others should be submitted to Blackboard under "Lecture 37 Assignment" . We will discuss these questions at the start of class, so no late submissions can be accepted.

In addition to the questions below, you can complete the activities in your zyBook from Chapter 22 for up to 25 bonus lecture assignment points, any time before the end of the semester.

The questions below can also be submitted for bonus points any time before the end of reading day.

1. Bailey Problem (not Self Check!) 15.2, p. 399. (4 points)
2. Bailey Problem (not Self Check!) 15.6, p. 399. (4 points)

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