Overview

• Preliminaries.
  • Admin.
  • Questions on the exam.
• An introduction to hash tables.
• Hash functions.
• An exercise.
• Hashing in Java.
• Handling collisions.
• Handling removal.

Preliminaries

Admin

• I'm returning the exam redos. I'm not sure that it was worth allowing you to redo the exam. It looks like those who did so spent a lot of time on it, and it didn't make a big difference in grades. It also took a lot of my time and mental energy.
• Further thoughts on unit tests: A good unit test does two things.
  • It tells you that your code does not work correctly.
  • It gives you enough information to help diagnose the problem.
• Congrats to DG.
• Upcoming extra credit opportunities:
  • "Data Sovereignty: The Challenge of Geolocating Data in the Cloud", November 25, 4:15 JRC 101 TODAY!
  • "Gold Fever" by Andrew Sherburne '01 or so, 7:00 p.m., Monday, November 25, ARH 302 TODAY!
  • Tuesday, November 26, 4:15 p.m., JRC 209 a gaming event with the game [d0x3d!]
  • Any self-care week activity (after Turkey break)

Questions on the Exam

Do you want more errata?

No. There's way too much as it is. And yes, you are up to one letter grade of extra credit. (I will, however, be capping scaled grades at A+.)

Are you going to penalize the bozos who turned in the prologue Friday, but after 5pm?

Why do you folks put me in these situations? What do you think I should do? The class decides that we should paint a big red P (for procrastinator) on their forehead.

If we borrow code from a homework assignment, should we cite our colleagues?

Yes.

Can you give me some hints on problem 1?

See the white board.

_Can we record you?

Only if you promise not to post to the InterWeb.

_What should we do if the thing to be removed is the last value?

Should be covered in case 01 or case 02.

An introduction to hash tables

• Reminder: Implementing dictionaries
  • Unordered arrays/lists of key/value pairs
  • Ordered arrays of key/value pairs - Binary search for get
  • Binary search tree
• Can we do even better? Can we get O(1) for put/get?
• Stacks and queues allow O(1) put/get, but that's not for anything?
• Indexed collections with O(1) put and get? Yes! Arrays!
• Key idea: Convert each key to an integer in the range 0...length-1
• put: Convert to integer. A[function(key)] = (Key,Value)
• get: return A[function(key)].value
• Assumption: The array is big enough to hold all of the key/value pairs we want to put in
• put: Convert to integer. A[function(key) % A.length] = (Key,Value)
• get: return A[function(key) % A.length].value

Hash functions

• Goal 1: If A equals B, then the function converts A and B to the same integer
• Goal 2: If A does not equal B, then the function probably gives different integers

An exercise

Hash your first name (in a table of size 30)

A: 1   F: 6   K: 11  P: 16  U: 21  Z: 26
B: 2   G: 7   L: 12  Q: 17  V: 22
C: 3   H: 8   M: 13  R: 18  W: 23
D: 4   I: 9   N: 14  S: 19  X: 24
E: 5   J: 10  O: 15  T: 20  Y: 25

SAMUEL: 19 + 1 + 13 + 21 + 5 + 12 = 71 => 11
WILLIAM: 23 + 9 + 12 + 12 + 9 + 1 + 13 = 79 => 19
FRED: 6 + 18 + 5 + 4 = 33 => 3

0:                  10:
1:                  11:
2:                  12:             22:
3:                  13:             23:
4:
5:
6:
7:
8:
9:

Hashing in Java

Handling collisions

Handling removal