I use 32bit FNV-1a personally (there's also 64/128bit versions if you do get too many collisions) because it hasn't given me any collisions yet and when I tested it on a dictionary, it had almost perfect distribution over the 32-bit range of numbers.

If you are worried about collisions, just do what a normal hash table would do and store files which map to the same hash value in a linked list (or something) and do a simple linear search on those. The vast majority of filenames will hash to different values, but you'll still be covered for the rare case of a hash collision.

Quote:Original post by WaterCrane
Thank you for the responses everybody. The reason why I have to be careful with collisions is that the filename itself is not stored in the "File Hash Table" (FHT for short, as it is so named), so if two filenames collide to give the exact same hash, it is impossible to distinguish between them.

It's impossible to create a hash function that can hash arbitraryily-long strings into a fixed bit pattern without collision. It's called the pigeon-hole principle.

So no matter what hashing algorithm you choose, there will always be the possibilty of a collisions. The question is, what do you do about it? Is the any particular reason you don't want to store the file name in the archive? Maybe a simple obfuscation routine can hide the names from prying eyes?

Personally, I'd use a cryptographic hash created using XTEA with the Davies-Meyer algorithm for converting a block cipher into a secure hash. Using XTea means it should be fast and the algorithm is very simple. Using XTea would give you a 64-bit hash, but if you wanted only 32 bits, you could just xor the two values together.
with XTea(Key, Data),
Hash' = Hash xor XTea(Text, Hash);

Make sure you use the Merkle-Damgard construction to finalize the hash value after iterating the above algorithm.

Quote:Original post by WaterCrane
[...]I like the suggestions that are coming in; thanks guys. I'm considering running some benchmarks on a number of hash algorithms. Cryptographic security is not an issue in this case, just good speed and distribution across the range.

I didn't mention it because of security concerns, but simply because using that algorithm is very simple to understand and implement, it should be quick with XTEA, and because it is supposed to be secure, it should have all the properties you want in a hash function.

Another possibility if you're working with file names that can be taken from a limited character set (say lowercase a-z, 0-9, and a single delimiter such as ' ' or '-') then you can just store the filename directly in a few bits. With the example character set, there are 26+10+1=37 characters, and log37(2^64) = 12.285, which means you could store a 12-character file name in 64 bits and still have 1 bit left for a flag of some kind. The way to store the file names in this manner is a 12-digit base-37 number. For example 'filename.ext' would be f*37^11 + i*37^10 + l*37^9 + e*37^8 + ... x*37^1 + t*37^0 where f would be 5 ('f'-'a') and i would be 8 ('i'-'a') and so on. You can actually use up to a 40-symbol alphabet and still fit 12 characters in 64 bits (or 6 characters in 32 bits).

A final possibility, if your archives never need to be modified (and are entirely fixed once they're created from a set of files that is entirely known at creation time) is using a perfect hash generator that will create a unique hash algorithm for specifically the names used in the archive. You'd need to figure out a way to store the hash algorithm in the archive itself (obviously not in a file in the archive - it'd have to be a header etc), but it would ensure that no collisions happen.