Hashing – Visualizing Randomness in Hash Algorithms

hashingrandomvisualization

I'm curious if anyone here has any idea how the images were generated as shown in this response: Which hashing algorithm is best for uniqueness and speed?

Ian posted a very well-received response but I can't seem to understand how he went about making the images. I hate to make a new question dedicated to this, but I can't find any means to ask him more directly. On the other hand, perhaps someone has an alternative perspective.

The best I can personally come up with would be to have it almost like a bar graph, which would illustrate how evenly the buckets of the hash table are being generated. I have a working Cocoa program that does this, but it can't generate anything like what he showed there.

So the question is two fold I suppose:

A) How does one truly interpret the data he shows? Is it more than "less whitespace = better"?

B) How does one generate such an image based on some set of inputs, a hash, and an index?

Perhaps I'm misunderstanding entirely, but I really would like to know more about this particular visualization technique. Or maybe I'm mis-applying this to hash tables rather than just hashes in general, but in that case I don't know how it would be "bounded" for the image.

Best Answer

From the comment by Ian in the answer

Development tool is Delphi. i assume you mean the images though. For "linear" map i created a square bitmap of size nxn, (where n = Ceil(sqrt(hashTable.Capacity))). Rather than simply black for list entry is occupied and white for list entry is empty, i used an HSLtoRGB function, where the hue ranged from 0 (red) to 300 (magenta). White is still an "empty list cell". For the Hilbert map i had to hunt wikipedia for the algorithm that turns an index into an (x,y) coordinate.

Basically, less visually identifiable "pattern" is better as it means the hash is more truly random. Big holes (white space) would indicate that the hash is not spreading the values particularly well.

Related Topic