Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.
Dictionary data types and HashTables. Readings: KernighanPike Section 2.9.
In lecture, I got open addressing and closed addressing backwards. Open addressing refers to skipping down through the table to find an open spot. Closed addressing or chaining refers to using an auxiliary data structure like a linked list to store multiple elements at each position in the array.