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.

Improve this question

1 Answer 1

Reset to default
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.

Improve this answer
5
  • 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, 2012 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, 2012 at 0: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, 2012 at 3: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, 2012 at 5:43
  • Interesting, but that would probably do the trick. Thanks for the info!
    – clstroud
    Nov 27, 2012 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.