SE250:lab-5:bvic005
This lab was quite hard, as a lot of the code we where provided was past our level of expertise, and it used statistical measures that where not explained, and we where not familiar with. However, after almost hour of blank staring, and a lot of question asking, i managed to come up with this code to test the provided function, and i had a general idea as to what the output meant:
The Code
int main( ) {
int sample_size = 100000;
int n_keys = 1000;
int table_size = 500;
ent_test( "Buzhash low ", low_entropy_src, sample_size, &rt_add_buzhash );
ent_test( "Buzhashn low ", low_entropy_src, sample_size, &rt_add_buzhashn );
ent_test( "Hash CRC low ", low_entropy_src, sample_size, &rt_add_hash_CRC );
ent_test( "Base256 low ", low_entropy_src, sample_size, &rt_add_base256 );
ent_test( "Java Integer low", low_entropy_src, sample_size, &rt_add_Java_Integer );
ent_test( "Java Object low ", low_entropy_src, sample_size, &rt_add_Java_Object );
ent_test( "Java String low ", low_entropy_src, sample_size, &rt_add_Java_String );
ent_test( "Random low ", low_entropy_src, sample_size, &rt_add_rand );
ent_test( "High Random low ", low_entropy_src, sample_size, &rt_add_high_rand );
printf("\n");
ent_test( "Buzhash ", typical_entropy_src, sample_size, &rt_add_buzhash );
ent_test( "Buzhashn ", typical_entropy_src, sample_size, &rt_add_buzhashn );
ent_test( "Hash CRC ", typical_entropy_src, sample_size, &rt_add_hash_CRC );
ent_test( "Base256 ", typical_entropy_src, sample_size, &rt_add_base256 );
ent_test( "Java Integer", typical_entropy_src, sample_size, &rt_add_Java_Integer );
ent_test( "Java Object ", typical_entropy_src, sample_size, &rt_add_Java_Object );
ent_test( "Java String ", typical_entropy_src, sample_size, &rt_add_Java_String );
ent_test( "Random ", typical_entropy_src, sample_size, &rt_add_rand );
ent_test( "High Random ", typical_entropy_src, sample_size, &rt_add_high_rand );
printf("\n");
printf( "Buzhashn %d/%d: llps = %d, expecting %g\n",
n_keys, table_size,
llps_i( n_keys, table_size, buzhashn ),
expected_llps( n_keys, table_size ) );
printf( "Java Integer %d/%d: llps = %d, expecting %g\n",
n_keys, table_size,
llps_i( n_keys, table_size, Java_Integer_hash ),
expected_llps( n_keys, table_size ) );
printf("\n");
printf( "Buzhash low %d/%d: llps = %d, expecting %g\n",
n_keys, table_size,
llps( n_keys, low_entropy_src, table_size, buzhash ),
expected_llps( n_keys, table_size ) );
printf( "Hash CRC low %d/%d: llps = %d, expecting %g\n",
n_keys, table_size,
llps( n_keys, low_entropy_src, table_size, hash_CRC ),
expected_llps( n_keys, table_size ) );
printf( "Base256 low %d/%d: llps = %d, expecting %g\n",
n_keys, table_size,
llps( n_keys, low_entropy_src, table_size, base256 ),
expected_llps( n_keys, table_size ) );
printf( "Java Object low %d/%d: llps = %d, expecting %g\n",
n_keys, table_size,
llps( n_keys, low_entropy_src, table_size, Java_Object_hash ),
expected_llps( n_keys, table_size ) );
printf( "Java String low %d/%d: llps = %d, expecting %g\n",
n_keys, table_size,
llps( n_keys, low_entropy_src, table_size, Java_String_hash ),
expected_llps( n_keys, table_size ) );
printf("\n");
printf( "Buzhash %d/%d: llps = %d, expecting %g\n",
n_keys, table_size,
llps( n_keys, typical_entropy_src, table_size, buzhash ),
expected_llps( n_keys, table_size ) );
printf( "Hash CRC %d/%d: llps = %d, expecting %g\n",
n_keys, table_size,
llps( n_keys, typical_entropy_src, table_size, hash_CRC ),
expected_llps( n_keys, table_size ) );
printf( "Base256 %d/%d: llps = %d, expecting %g\n",
n_keys, table_size,
llps( n_keys, typical_entropy_src, table_size, base256 ),
expected_llps( n_keys, table_size ) );
printf( "Java Object %d/%d: llps = %d, expecting %g\n",
n_keys, table_size,
llps( n_keys, typical_entropy_src, table_size, Java_Object_hash ),
expected_llps( n_keys, table_size ) );
printf( "Java String %d/%d: llps = %d, expecting %g\n",
n_keys, table_size,
llps( n_keys, typical_entropy_src, table_size, Java_String_hash ),
expected_llps( n_keys, table_size ) );
return 0;
}
Code Explanation
Basically, my code tests the functions in two main parts.
First, it tests the theoretical randomness of hash values generated by the functions, from a "low entropy", and then from a "typical entropy" source list of keys. For this test, i used a sample size(number of hash keys generated) of 100,000, because it is a generic "large" number, to hopefully give the functions a fair shot at being random, and it is not to large, so the tests are preformed quickly.
Secondly, it tests the actual length of linked lists, when a set amount of keys are inserted in a hash table. Particularly, it looks at the longest list, compared to the statistically expected longest list. First, two integer hash functions are tested, and then the string hash functions are tested for "low entropy" and "typical entropy" keys.
The Results
Here are some results:
Buzhash low 7.99830 75.00% 127.578 0.71% 0.000327 Buzhashn low 7.99824 50.00% 127.494 0.13% -0.003092 Hash CRC low 5.59831 0.01% 81.783 24.53% 0.028545 Base256 low 0.00000 0.01% 97.000 27.32% undefined Java Integer low 4.82824 0.01% 43.883 27.32% -0.092002 Java Object low 2.00000 0.01% 77.000 27.32% -0.521556 Java String low 7.99959 99.99% 127.438 0.22% -0.000646 Random low 7.95308 0.01% 111.441 11.17% -0.051837 High Random low 7.99821 50.00% 127.402 0.59% -0.001222 Buzhash 7.99783 2.50% 127.374 0.77% -0.000076 Buzhashn 7.99824 50.00% 127.494 0.13% -0.003092 Hash CRC 7.84046 0.01% 122.862 1.98% 0.018518 Base256 4.02297 0.01% 107.853 27.32% 0.034082 Java Integer 4.82824 0.01% 43.883 27.32% -0.092002 Java Object 5.68903 0.01% 88.695 22.13% -0.136024 Java String 7.94554 0.01% 126.139 0.27% 0.021181 Random 7.95316 0.01% 111.468 11.13% -0.048905 High Random 7.99807 50.00% 127.406 0.07% -0.002226 Buzhashn 1000/500: llps = 5, expecting 7.45883 Java Integer 1000/500: llps = 2, expecting 7.45883 Buzhash low 1000/500: llps = 8, expecting 7.45883 Hash CRC low 1000/500: llps = 11, expecting 7.45883 Base256 low 1000/500: llps = 1000, expecting 7.45883 Java Object low 1000/500: llps = 1000, expecting 7.45883 Java String low 1000/500: llps = 4, expecting 7.45883 Buzhash 1000/500: llps = 10, expecting 7.45883 Hash CRC 1000/500: llps = 8, expecting 7.45883 Base256 1000/500: llps = 83, expecting 7.45883 Java Object 1000/500: llps = 13, expecting 7.45883 Java String 1000/500: llps = 8, expecting 7.45883
Theoretical Randomness Analysis
When looking at the results for randomness, the first colunm shows the entropy of the keys generated, or how many bytes on average where significant in making the hash unique(i think). As the hash key size is 8 bytes, the maximum and optimum entropy is 8. The buzhash, random and Java String functions worked well here, as did Hash CRC, in the typical entropy tests.
The second column is Chi Squared percentages. The optimum here is 50%, with buzhashn and high random doing well, but the values where very variably with sample size, so i am not sure we can draw anything significant from these values.
Third column is the mean value, with optimum randomness being a mean of 127.5. Once again, the best results come from the hash functions, the randoms, and the Java String. Hash CRC has a significantly "more random" mean with the typical entropy tests, once again(again).
The forth column is the error in a Monte Carlo calculation for pi, where why is estimated based on the samples. A perfectly random sample would theoretically generate pi exactly. Once again, the winners are Buzhash, Java String, and random.
Finally, we have the "Serial correlation coefficient", which has an optimum value of 0. The same winners once again, though the Java String typical entropy value is not that great.
From these results, it seems that Buzhash is the winner for theoretical randomness, though Java String seems to be a close second.
Practical Length Assessment
Next we need to look at the list length results. Note that i went for twice as many entries as the table length, to "stress" it a bit. For these values, a longest list of 7.4 is theoretically expected, so this or smaller would be good.
For the integer hash functions, Buzhash performs quite well with a longest list of 5, and very surprisingly, based on its randomness results, Java Integer performs perfectly, with a longest list of 2. there must be something special about the Java Integer function that allows it to distribute hash keys perfectly, without relying on randomness to do so.
For the string functions, Buzhash and Hash CRC perform well, with longest lengths around 8-10. Java String gets a similar 8 for typical entropy, but outperforms them with a 4 for low entropy keys.
Base 256 and Java object get perfectly bad longest lists of 1000 for the low entropy keys, though this is apparently an anomaly caused by how the low entropy keys are generated. Java object recovers quite well for a 13 in typical entropy, whereas Base 256 gets a still bad 83.
Conclusion
Basically, it seems that in out best test of real life performance, the typical entropy longest length, either of the integer key hash functions will do nicely, though the Java Integer one seems to magically get wonderful results, despite a lack of randomness. For string key hash functions, both Buzhash and Java String are very good. Hash CRC also could be a possibility, though its lower randomness may mean that it is not quite as consistent as the others.
Bvic005 02:18, 9 April 2008 (NZST)