https://wiki.kram.nz/index.php?action=history&feed=atom&title=SE250%3Alab-5%3Asdal039
SE250:lab-5:sdal039 - Revision history
2026-04-29T01:15:37Z
Revision history for this page on the wiki
MediaWiki 1.45.3
https://wiki.kram.nz/index.php?title=SE250:lab-5:sdal039&diff=6786&oldid=prev
Mark: 21 revision(s)
2008-11-03T05:19:54Z
<p>21 revision(s)</p>
<p><b>New page</b></p><div>Sample Size: 10,000<br />
<br />
Number of Keys: 100<br />
<br />
Table Size: 1000<br />
<br />
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.<br />
<br />
===Part 1===<br />
<br />
Low Entropy Source<br />
<html><table><tr><th>Function</th><th>Entropy</th><th>Chi sq</th><th>Mean</th><th>Monte Carlo</th><th>Series Correlation</th></tr><tr><td>Buzhash</td><td>7.98550</td><td>99.00%</td><td>125.825</td><td>1.26%</td><td>-0.000047</td></tr><tr><td>Buzhashn</td><td>7.98214</td><td>50.00%</td><td>127.589</td><td>2.10%</td><td>0.000600</td></tr><tr><td>Hash CRC</td><td>4.85247</td><td>0.01%</td><td>99.261</td><td>26.10%</td><td>-0.285059</td></tr><tr><td>Java Integer Hash</td><td>4.11606</td><td>0.01%</td><td>32.385</td><td>27.32%</td><td>-0.217081</td></tr><tr><td>Java <br />
Object Hash</td><td>2.00000</td><td>0.01%</td><td>77.000</td><td>27.32%</td><td>-0.521556</td></tr><tr><td>Java String Hash</td><td>7.99347</td><td>99.99%</td><td>127.343</td><td>0.19%</td><td>0.017074</td></tr><tr><td>Base 256</td><td>0.00000</td><td>0.01%</td><td>97.000</td><td>27.32%</td><td>undefined</td></tr><br />
<tr><td>Random</td><td>7.93533</td><td>0.01%</td><td>112.054</td><td>10.82%</td><td>-0.066125</td></tr><tr><td>High Random</td><td>7.98463</td><td>97.50%</td><td>128.035</td><td>0.04%</td><td>0.011571</td></tr></table></html><br />
<br />
<br />
Typical Entropy Source<br />
<html><table><tr><th>Function</th><th>Entropy</th><th>Chi sq</th><th>Mean</th><th>Monte Carlo</th><th>Series Correlation</th></tr><tr><td>Buzhash</td><td>7.97970</td><td>25.00%</td><td>127.177</td><td>1.95%</td><td>-0.007153</td></tr><tr><td>Buzhashn</td><td>7.98214</td><td>50.00%</td><td>127.589</td><td>2.10%</td><td>0.000600</td></tr><tr><td>Hash CRC</td><td>7.77880</td><td>0.01%</td><td>123.087</td><td>1.11%</td><td>-0.002250</td></tr><tr><td>Java Integer Hash</td><td>4.11606</td><td>0.01%</td><td>32.385</td><td>27.32%</td><td>-0.217081</td></tr><tr><td>Java Object Hash</td><td>4.93157</td><td>0.01%</td><td>116.582</td><td>25.87%</td><td>-0.506511</td></tr><tr><td>Java String Hash</td><td>7.89301</td><td>0.01%</td><td>126.009</td><td>1.42%</td><td>-0.021360</td></tr><tr><td>Base 256</td><td>3.90309</td><td>0.01%</td><td>107.987</td><td>27.32%</td><td>0.079032</td></tr><br />
<tr><td>Random</td><td>7.93533</td><td>0.01%</td><td>112.054</td><td>10.82%</td><td>-0.066125</td></tr><tr><td>High Random</td><td>7.98463</td><td>97.50%</td><td>128.035</td><td>0.04%</td><td>0.011571</td></tr></table></html><br />
<br />
<br />
<br />
'''Best Hash Function'''<br />
<br />
For low entropy source<br />
<br />
1. Java String Hash<br />
<br />
2. Buzhash<br />
<br />
3. High Random<br />
<br />
4. Buzhashn<br />
<br />
5. Random<br />
<br />
6. Hash CRC<br />
<br />
7. Base 256<br />
<br />
8. Java Object Hash<br />
<br />
9. Java Integer Hash<br />
<br />
<br />
<br />
For typical entropy source<br />
<br />
1. Buzhashn<br />
<br />
2. High Random<br />
<br />
3. Buzhash<br />
<br />
4. Random<br />
<br />
5. Java String Hash<br />
<br />
6. Hash CRC<br />
<br />
7. Java Object Hash<br />
<br />
8. Java Integer Hash<br />
<br />
9. Base 256<br />
<br />
<br />
Best in both cases: '''buzhashn''' and '''buzhash'''<br />
<br />
===Part 2===<br />
<br />
Low Entropy Source<br />
<html><table><tr><th>Function</th><th>llps</th><th>expected</th></tr><br />
<tr><td>Buzhash</td><td>2</td><td>2.13803</td></tr><br />
<tr><td>Hash CRC</td><td>2</td><td>2.13803</td></tr><br />
<tr><td>Base 256</td><td>100</td><td>2.13803</td></tr><br />
<tr><td>Java String Hash</td><td>1</td><td>2.13803</td></tr><br />
<tr><td>Java Object Hash</td><td>100</td><td>2.13803</td></tr><br />
</table></html><br />
<br />
<br />
Typical Entropy Source<br />
<html><table><tr><th>Function</th><th>llps</th><th>expected</th></tr><br />
<tr><td>Buzhash</td><td>1</td><td>2.13803</td></tr><br />
<tr><td>Hash CRC</td><td>3</td><td>2.13803</td></tr><br />
<tr><td>Base 256</td><td>4</td><td>2.13803</td></tr><br />
<tr><td>Java String Hash</td><td>2</td><td>2.13803</td></tr><br />
<tr><td>Java Object Hash</td><td>3</td><td>2.13803</td></tr><br />
</table></html><br />
<br />
<br />
In actual use, buzhash produced a hash table with the lowest linked-list length.<br />
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.</div>
Mark