SE250:lab-5:sdal039
Sample Size: 10,000
Number of Keys: 100
Table Size: 1000
Sample size of 10,000 was chosen because it seemed to be the lowest order of magnitude that gave fairly similar results to any order of magnitude above, and different to orders of magnitude below. This would result in the fastest execution time for the level of accuracy we want.
Part 1
Low Entropy Source
<html>
| Function | Entropy | Chi sq | Mean | Monte Carlo | Series Correlation |
|---|---|---|---|---|---|
| Buzhash | 7.98550 | 99.00% | 125.825 | 1.26% | -0.000047 |
| Buzhashn | 7.98214 | 50.00% | 127.589 | 2.10% | 0.000600 |
| Hash CRC | 4.85247 | 0.01% | 99.261 | 26.10% | -0.285059 |
| Java Integer Hash | 4.11606 | 0.01% | 32.385 | 27.32% | -0.217081 |
| Java Object Hash | 2.00000 | 0.01% | 77.000 | 27.32% | -0.521556 |
| Java String Hash | 7.99347 | 99.99% | 127.343 | 0.19% | 0.017074 |
| Base 256 | 0.00000 | 0.01% | 97.000 | 27.32% | undefined |
| Random | 7.93533 | 0.01% | 112.054 | 10.82% | -0.066125 |
| High Random | 7.98463 | 97.50% | 128.035 | 0.04% | 0.011571 |
</html>
Typical Entropy Source
<html>
| Function | Entropy | Chi sq | Mean | Monte Carlo | Series Correlation |
|---|---|---|---|---|---|
| Buzhash | 7.97970 | 25.00% | 127.177 | 1.95% | -0.007153 |
| Buzhashn | 7.98214 | 50.00% | 127.589 | 2.10% | 0.000600 |
| Hash CRC | 7.77880 | 0.01% | 123.087 | 1.11% | -0.002250 |
| Java Integer Hash | 4.11606 | 0.01% | 32.385 | 27.32% | -0.217081 |
| Java Object Hash | 4.93157 | 0.01% | 116.582 | 25.87% | -0.506511 |
| Java String Hash | 7.89301 | 0.01% | 126.009 | 1.42% | -0.021360 |
| Base 256 | 3.90309 | 0.01% | 107.987 | 27.32% | 0.079032 |
| Random | 7.93533 | 0.01% | 112.054 | 10.82% | -0.066125 |
| High Random | 7.98463 | 97.50% | 128.035 | 0.04% | 0.011571 |
</html>
Best Hash Function
For low entropy source
1. Java String Hash
2. Buzhash
3. High Random
4. Buzhashn
5. Random
6. Hash CRC
7. Base 256
8. Java Object Hash
9. Java Integer Hash
For typical entropy source
1. Buzhashn
2. High Random
3. Buzhash
4. Random
5. Java String Hash
6. Hash CRC
7. Java Object Hash
8. Java Integer Hash
9. Base 256
Best in both cases: buzhashn and buzhash
Part 2
Low Entropy Source
<html>
| Function | llps | expected |
|---|---|---|
| Buzhash | 2 | 2.13803 |
| Hash CRC | 2 | 2.13803 |
| Base 256 | 100 | 2.13803 |
| Java String Hash | 1 | 2.13803 |
| Java Object Hash | 100 | 2.13803 |
</html>
Typical Entropy Source
<html>
| Function | llps | expected |
|---|---|---|
| Buzhash | 1 | 2.13803 |
| Hash CRC | 3 | 2.13803 |
| Base 256 | 4 | 2.13803 |
| Java String Hash | 2 | 2.13803 |
| Java Object Hash | 3 | 2.13803 |
</html>
In actual use, buzhash produced a hash table with the lowest linked-list length.
For low entropy source base 256 and Java object hash both performed very badly, putting every cell into the same place in the array. While better in the typical entropy source, they still performed the worst out of the hash functions.