Simple hashing question

[stkarnivor]

What does it mean for a hash function to be 32 and 64 bit?

http://www.isthe.com/chongo/tech/comp/fnv/index.html

[gusano79]

I would take that to mean that the hash function has two operating modes, one that produces a 32-bit hash, and another that produces a 64-bit hash. The FNV hash you linked actually has six different hash lengths.

Better terminology might be that you have a family of hash functions that represent the same basic hashing technique, and the individual hash functions are variations that produce different hash sizes.

[stkarnivor]

Just to clarify (sorry if this seems stupid), if I have a new linked list element I would like to hash into my array, my hash array size must be 2^(Bit size of hash)?

[gusano79]

if I have a new linked list element I would like to hash into my array, my hash array size must be 2^(Bit size of hash)?

Conceptually, yes... your hash table should be able to accommodate every possible hash value.

In practice, though, you wouldn't normally allocate the entire hash table at once. This can work for short hash functions, but (for example) a 32-bit hash table storing 32-bit pointers would need (2^32)*4 bytes = 16 GB of storage. Hash tables are typically implemented using some kind of dynamic array.

--smg

[stkarnivor]

Excellent, I just have one more question.

The readme on the fnv hash page lists an example usage:

//For example to perform a 64 bit FNV-1 hash:

	#include "fnv.h"

	Fnv64_t hash_val;
	hash_val = fnv_64_str("a string", FNV1_64_INIT);
	hash_val = fnv_64_str("more string", hash_val);

// Produces the same final hash value as:

	hash_val = fnv_64_str("a stringmore string", FNV1_64_INIT);

How would I, once I have the hashed an element (say by a string) of my linked list, find an element based off of that string once it is already placed in the table. I ask this because upon studying very basic hash techniques I have not encountered anything that explains why you would send the previous hash value to calculate the next.

[gusano79]

The readme on the fnv hash page lists an example usage:

//For example to perform a 64 bit FNV-1 hash:

	#include "fnv.h"

	Fnv64_t hash_val;
	hash_val = fnv_64_str("a string", FNV1_64_INIT);
	hash_val = fnv_64_str("more string", hash_val);

// Produces the same final hash value as:

	hash_val = fnv_64_str("a stringmore string", FNV1_64_INIT);

...

I have not encountered anything that explains why you would send the previous hash value to calculate the next.

I'm not familiar with the specifics of the FNV hash, but looking at the code you quoted, here's what I think is going on:

In your example code, the fnv_64_str function takes two parameters; first, the string to hash, and second, an initialization value. This appears to be representative of the internal state of the FNV hash function, which also the result that is returned from the hash.

The first call to fnv_64_str starts with an internal hash value of FNV1_64_INIT , which you can consider a sort of "null hash"--I would expect this value to be returned if you tried to hash the empty string ( "" ). Then for each character in the string to be hashed, it updates the internal hash value, until it reaches the end of the string, then it returns the internal hash value.

So the two-line example is just a way to show you can "interrupt" the hash and finish it later. This might be useful, for example, if you're hashing some sort of input stream as it comes across a network connection, and you only get a little bit at a time.

How would I, once I have the hashed an element (say by a string) of my linked list, find an element based off of that string once it is already placed in the table.

Remember that your hash table is an associative array, using hash values as keys, and objects (or more likely pointers to objects) as values.

To get the object again, hash the string and look up its hash value in the table--the value associated with the string's hash should be the object you're looking for.

[stkarnivor]

I think thats it for my questions, thanks again for the help :)