Stupid old brain question, how to measure a hash function's quality
14 views
Skip to first unread message
Earl_Colby_Pottinger
unread,
Feb 8, 2012, 10:38:45 PM2/8/12
Delete
You do not have permission to delete messages in this group
Copy link
Report message
Show original message
Either email addresses are anonymous for this group or you need the view member email addresses permission to view the original message
to
Okay, after a long time I am starting my work on a compressing VIRTUAL-
RAM-DRIVE again.
The main reason is to test BFS ability to handle large hard drives and
large files (ie. Drives/Files 4TB and larger).
The non-compressing version I presently am using uses a sparse model
that only needs memory when a data_track has data written into it.
However, my 4GB machine is starting to have problems once the virtual
drive is greater than 2TB. I need to compress the data_tracks in
memory to model larger drives.
To do that I have looked at a number of compression schemes, but I
have gotten interested in the compression schemes that are modeling
disk drives and in-memory compression in particular. See:
Anyway the question: How do I test the quality of a hash function? The
way I am thinking of doing it is to feed the 149GB test image (this is
my base work image I use to test functions) into the hash function and
then increment each hashed position by one. Presently I am using a
2^24 hash_table. If the hash function works well like I hope
(unlikely) there should be a count of 149*2^30/2^24 = 149*2^6 = 9536
in each hash cell.
What I think I need to do to get a simple value as a measure is to add
up the absolute difference between values in the cells vs the expected
average value (in this case 9536). This will probably be a very large
number so I would divide it by the number of cells in the hash_table.
Good idea?
I also tried reading http://burtleburtle.net/bob/hash/doobs.html and
while I understand the code of the hash functions, I just can't seem
to understand how his testing score work. Can someone give me a clue?