by Frank Gerlach (frankgerlach.tai@gmx.de)
Pseudo-Random Number Generators (PRNGs) and Hash Functions for Hash Tables have quite similar functions: They take a number of bits of input and return a supposedly strongly randomized function of the input bits. This paper will perform experimental analysis of these functions using two-dimensional images. As shown in the previous paper, weak functions can be spotted easily.
A two-dimensional image is used to display the output of the functions. The function return values are split into 16 bit for each coordinate. The mapping on the image coordinates is performed using simple modulus operations. As input, a sequence of values from 0 to the number of image pixels is used.
An ideal PRNG or Hashing function will look on the image like random noise.
This is a LCG devised by the author "on the spot". It is not as good as the best LCGs. I would argue though, that even the best LCGs have the same systematic problem, namely a repeating structure of pixel clusters.
This LCG displays a more sophisticated pattern, but it is still highly repetitive, which is very bad as compared to the stated ideal of physical noise.
This is one of the best hash functions for use in hash tables and the resulting picture clearly reflects the good quality. It is used in the GNU Standard Library. I recommend to use it for all hash table has function use.
The Suchoi Hash function has been invented by the author for use in Hash Tables. It's good quality is reflected in random-looking image.
CRC32 is a widely used checksum function, which was originally invented to secure telecommunications data in transmission. It displays very good randomization in the image, but it is not the fastest function for hash table use.
The Adler32 function is being advertised as a "good" hash function on the internet. The resulting image is of very high structure, which means that Adler32 is a very low quality hash function.
SHA256 is a one of the Secure Hash Algorithms widely used in the current internet and IT spheres for information security. It's output is said to be indistinguishable from physical random noise. For use in Hashtables it is probably too slow to process, but it can nicely serve as a benchmark for Hash and PRNG functions in general. As expected, the image looks very much like physical noise.
The source code and bitmap files for all of the tests above can be downloaded here.