C++ Hashing Functions

[tatteredpotato]

A couple weeks ago I did an assignment that involved making a phone book out of a BST. Now the assignement is to modify that program to take use a hash table, and we have to make that hash table. The small part he gave us has it as a template class that takes two data types, a KeyType and a DataType (this is the same way our BST was defined). So in the phonebook, the KeyType is int (phone number) and the DataType is a struct containing things like Address and Name etc.

My question is mainly about the hashing function, and how to get it to work properly with this data type. I'm aware of how my classmates are doing it, and they're pretty much all doing index = phone_number % table_capacity, and sure that gets the job done, but if you would try to reuse this class, and define KeyType as anything but int it's not going to compile. So is there a good way of implementing a hashing function that will work for any generic type?

 

[degibson]

The 'key' problem (pun intended) is that whatever type T is, you need to be able to run the modulo on it eventually for safety anyway. For that, you need to 'convert arbitrary type to int'. If you can guarantee that your KeyType will compare to int (which is a pretty big assumption in its own right), you can 'guess' its key-equivalent value with binary search in log2(32) or log2(64) time.

 

[tatteredpotato]

I'm not too familiar with function pointers, but would it be possible to pass a custom hashing function to the hash table constructor that the hash table could store and use? Then you could use some exotic data-types for a key and still be able to have the hashing function work.

EDIT to clarify, I know python lets you do something like:

def f(x):

then:

a = f

so then a(x) would be the same as f(x). I want to 'save' the function passed within the class.

 

[Ken g6]

Sounds like you want to pass in a function pointer. I believe the standard C sorting function (qsort? It's been awhile.) does that for a comparison function.

 

[degibson]

A function pointer would work, but it would require the user of the data structure to provide the hash function... which defeats half the purpose of the template. Too bad everything in C++ isn't hashable.

 

[Ken g6]

The other way to do it is to have a method in the datatype to hash that datatype. Java does it for all Objects, for instance.

Come to think of it, if Java didn't have that, one could implement it with an Interface. To make a String hashable, again assuming Java didn't already have that method, Java syntax would be roughly to create a new:

public class HashableString extends String implements Hashable {
public int hashCode() { [ hashing code ] }
}

Interface isn't a keyword in C++, but you can make one anyway. How's that sound as a solution?

 

[tatteredpotato]

Actually I find that passing a function pointer in the constructor suits me pretty well. I have a default hashing function that will work on any numeric keys, and that gets used if one isn't specified. The only limitation I found was my hash function then could only have access to the public data members, but it's something to play with.

This is really above and beyond the scope of the assignment, he gave us a "Working constructor" which writes a '-1' to every key in the hash table, so that shows me right there he isn't expecting us to really extend this into a true template. His method might as well drop they KeyType from Hash<KeyType, DataType>, since it is limited to ints (I suppose floats and doubles too, and maybe strings with some work).

 

[degibson]

Actually, even better than a function pointer would be a hasher class, analogous to the comparator class the case of the STL prio_queue.
http://www.cplusplus.com/refer..._queue/priority_queue/

Using a class would allow the compiler to get the inlining right... no register-indirect branch