Welcome back, nothing new (reminder, hw2 due Tuesday).

Today we continue with hashing (Section 3.4), we left
off in the lecture notes last time around page 25.

Also, some points outside the slides:
  book, p 471: how to delete in a linear probing table
  book, p 472: visualization of "clusters" in linear probing
  book, p 474: array resizing (like "array doubling"),
               amortized cost of resizing is O(1) per op.

If we have time, we'll consider some variations on hashing.  In
particular we would like "perfect hashing", where means all searches
take O(1) probes in the worst case (not just expected).  That may be
the subject of our next homework project.

More hashing practice: scripting languages, filesystems, databases.

We can actually run the FileIndex.java example (and just for
comparison, see python version ../book/fileindex.py):

$ cd ../book
$ java -cp '.:*' FileIndex *.java
Indexing files
  AcyclicLP.java
  [... long list of files suppressed ...]
  Whitelist.java
UF
  BoruvkaMST.java
  KruskalMST.java
  LazyPrimMST.java
  PrimMST.java
  UF.java
hash
  Date.java
  LinearProbingHashST.java
  RabinKarp.java
  SeparateChainingHashST.java
  Transaction.java
PQ
  CollisionSystem.java
  IndexMaxPQ.java
  IndexMinPQ.java
  TopM.java
^D
$