In this lecture, we will continue our discussion started Tuesday , regarding hash tables.  In particular, running times for several of the hashing methods will be discussed.  Also, linear and quadratic probing will be discussed briefly.  For the remainder of the lecture, Skip Lists will be discussed.

Here are the sections of the textbook:

• 1st edition book:

• 2nd edition book

Additional Material:

• Random Numbers with Java: (written by Professor Franck van Breugel)

• PseudoRandomNumberGenerator.java
• Math.random()
• java.util.Random
• Implementation of a dictionary by means of a skip list (PDF format) (written by Professor Franck van Breugel)

• Skip List Source Code (written by Professor Franck van Breugel):

• Order
• IntegerOrder
• SkipListNode
• SkipListDictionary