5

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.

Community
  • 1
clstroud
  • 53
  • 4

1 Answers1

1

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.

Michael Rutherfurd
  • 281
  • 2
  • 4
  • Michael, thanks, but I have already read through that comment a few times now. I don't think it's very revealing unless I'm missing something obvious? – clstroud Nov 26 '12 at 23:28
  • Ian basically mapped the generated hash into an array, folded it to display to result, and rather than just colour it black/white he changed the black into different colours depending how far down the array he was. – Michael Rutherfurd Nov 27 '12 at 00:07
  • I think that makes more sense now that you've explained it that way. I think I was just thinking of it in terms of a hash table after compression. Even still, how would he pre-compute a maximum bound for his array? – clstroud Nov 27 '12 at 03:30
  • @clstroud At a guess he was just basing it directly on the number of hashes he was generating... probably table size = hashes * 2 to ensure 50% whitespace – Michael Rutherfurd Nov 27 '12 at 05:43
  • Interesting, but that would probably do the trick. Thanks for the info! – clstroud Nov 27 '12 at 13:58