I revised 0217/Driver.java, which we used to compare Cuckoo hashing
and Chaining.  The old driver created a set of random int keys, but
from a small range (N distinct keys in the range 0 to 2*N).  Later I
realized this would make our max bucket-size artificially small, which
ruins the motivation for Cuckoo hashing.

The revised Driver.java uses unbounded random int keys, and now
Chaining has a higher "max" probes stat (the maximum number of key
comparisons required to find any one key, we expect this to grow
slowly with N).  That motivates Cuckoo hashing, and other "perfect"
schemes, which bound their max probes by a constant.

Summary (N=500000 distinct int keys, max load 2 in chaining):
   cuckoo, either driver: max=2
   chaining, new driver:  max=12
   chaining, old driver:  max=4


For more detailed output, see below.
Again, the max load factor for chaining is 2 in these experiments.

cs323000@caribou:~/share/0217$ make cuckoo
javac -g Driver.java
java -ea Driver CuckooHash
Testing CuckooHash with N=500000 items, seed S=37
Constructed new CuckooHash()
Rebuild to 34 (size=15 m1=55 a1=9 m2=41 a2=3)
Rebuild to 68 (size=23 m1=9 a1=44 m2=75 a2=58)
Rebuild to 136 (size=43 m1=199 a1=111 m2=261 a2=55)
Rebuild to 272 (size=82 m1=453 a1=228 m2=189 a2=142)
Rebuild to 544 (size=124 m1=917 a1=462 m2=709 a2=26)
Rebuild to 1088 (size=248 m1=1229 a1=364 m2=1863 a2=1017)
Rebuild to 2176 (size=502 m1=2853 a1=471 m2=321 a2=1282)
Rebuild to 4352 (size=1071 m1=8391 a1=3705 m2=2243 a2=1119)
Rebuild to 8704 (size=1613 m1=10609 a1=3851 m2=7657 a2=783)
Rebuild to 17408 (size=2794 m1=13463 a1=4520 m2=33547 a2=15717)
Rebuild to 34816 (size=6011 m1=21569 a1=18338 m2=7001 a2=20419)
Rebuild to 69632 (size=10267 m1=66533 a1=31718 m2=45019 a2=45144)
Rebuild to 69633 (size=12953 m1=52859 a1=35442 m2=133915 a2=11519)
Rebuild to 139266 (size=32057 m1=244399 a1=74610 m2=180367 a2=104283)
Rebuild to 278532 (size=68532 m1=216737 a1=37703 m2=343615 a2=26268)
Rebuild to 557064 (size=138994 m1=630509 a1=232864 m2=70285 a2=108519)
Rebuild to 1114128 (size=284981 m1=1114123 a1=307244 m2=2203571 a2=467980)
Added 500000 Ints (with 29 duplicates on the way):
 used 497623 .equals calls, 5552877 .hashCode calls, 0.206 seconds
Hit probe stats over all 500000 items: mean=1.2689, sigma=0.4434, max=2
Removed 250000 Ints (with 6 false tries on the way):
 used 329984 .equals calls, 329984 .hashCode calls, 0.022 seconds
Hit probe stats over all 250000 items: mean=1.1296, sigma=0.3358, max=2

cs323000@caribou:~/share/0217$ make chaining
java -ea Driver ChainingHash
Testing ChainingHash with N=500000 items, seed S=37
Constructed new ChainingHash()
Rebuild to 16 (size=17)
Rebuild to 32 (size=33)
Rebuild to 64 (size=65)
Rebuild to 128 (size=129)
Rebuild to 256 (size=257)
Rebuild to 512 (size=513)
Rebuild to 1024 (size=1025)
Rebuild to 2048 (size=2049)
Rebuild to 4096 (size=4097)
Rebuild to 8192 (size=8193)
Rebuild to 16384 (size=16385)
Rebuild to 32768 (size=32769)
Rebuild to 65536 (size=65537)
Rebuild to 131072 (size=131073)
Rebuild to 262144 (size=262145)
Added 500000 Ints (with 29 duplicates on the way):
 used 738782 .equals calls, 1024316 .hashCode calls, 0.137 seconds
Hit probe stats over all 500000 items: mean=1.9536, sigma=1.1218, max=12
Removed 250000 Ints (with 6 false tries on the way):
 used 502827 .equals calls, 250006 .hashCode calls, 0.036 seconds
Hit probe stats over all 250000 items: mean=1.4778, sigma=0.7454, max=9

cs323000@caribou:~/share/0217$ make oldchaining  # use old driver
java -ea DriverOld ChainingHash
Testing ChainingHash with N=500000 items, seed S=17
Constructed new ChainingHash()
Rebuild to 16 (size=17)
Rebuild to 32 (size=33)
Rebuild to 64 (size=65)
Rebuild to 128 (size=129)
Rebuild to 256 (size=257)
Rebuild to 512 (size=513)
Rebuild to 1024 (size=1025)
Rebuild to 2048 (size=2049)
Rebuild to 4096 (size=4097)
Rebuild to 8192 (size=8193)
Rebuild to 16384 (size=16385)
Rebuild to 32768 (size=32769)
Rebuild to 65536 (size=65537)
Rebuild to 131072 (size=131073)
Rebuild to 262144 (size=262145)
Added 500000 Ints (with 193407 duplicates on the way):
 used 927679 .equals calls, 1217694 .hashCode calls, 0.111 seconds
Hit probe stats over all 500000 items: mean=1.7144, sigma=0.8104, max=4
Removed 250000 Ints (with 442535 false tries on the way):
 used 828944 .equals calls, 692535 .hashCode calls, 0.081 seconds
Hit probe stats over all 250000 items: mean=1.3575, sigma=0.5865, max=4
cs323000@caribou:~/share/0217$