Overloading default hash function

I copied this into my hash table header file so I can use a different string hash function, but it causes a redefinition error. My teacher said I could just put the code below in the header file, but it obviously doesn't work since it causes a redefinition of the default string hash function. What do I have to change for the code below to override the default string hash function?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <>
class hash<string>
{
	public:

	size_t operator()( const string & key )
	{

		size_t hashVal = 0;

		for( char ch : key )
			hashVal = 37 * hashVal + ch;

		return hashVal;
	}
};
Last edited on
You can't specialize std::hash<std::string> because it has already been specialized. If you want to create your own hash function you should use a different name.

1
2
3
4
5
6
7
8
9
10
11
class my_string_hash
{
public:
	size_t operator()( const string & key ) const // <-- don't forget const
	{
		size_t hashVal = 0;
		for( char ch : key )
			hashVal = 37 * hashVal + ch;
		return hashVal;
	}
};


If you want to use your hash function in a std::unordered_set or std::unordered_map you just pass the type of your hasher as a template argument.

 
std::unordered_set<std::string, my_string_hash> my_set;

If you think the name becomes too long to type you can always create a type alias using typedef.

1
2
typedef std::unordered_set<std::string, my_string_hash> MyStrSet;
MyStrSet my_set;
Last edited on
The problem with using a different name is that your table's hash method is no longer general, and the hash method now needs to identify when a key is a string and when it is not. Which really creates a lot of work to recode everything. Is there another method?
The problem with using a different name is that your table's hash method is no longer general...

The problem with the general method is that you don't want the default behavior, so specificity is in order.



...and the hash method now needs to identify when a key is a string and when it is not.

The compiler already needed to identify the type of the key to generate the hash function. You're not introducing any inefficiency in the form of extra overhead here.



Which really creates a lot of work to recode everything.

Not really.



Is there another method?

You could create your own type with a specialized hash function and store that type in lieu of a string. Of course, that really does create more work for you.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <string>
#include <functional>
#include <unordered_set>
#include <type_traits>

struct my_string_hash
{
    static constexpr std::size_t MULTIPLIER = 37 ;

    std::size_t operator() ( const std::string & key ) const noexcept // *** const ***
    {
        std::size_t hash_value = 0 ;
        for( unsigned char ch : key )
            hash_value = hash_value * MULTIPLIER + ch ;
        return hash_value ;
    }
};

template < typename T >
using my_hash = typename std::conditional< std::is_same< typename std::decay<T>::type, std::string >::value,
                                           my_string_hash, std::hash<T> >::type ;

template < typename T >
using my_unordered_set = std::unordered_set< T, my_hash<T> > ;

int main()
{
    my_unordered_set<int> int_set ;
    static_assert( std::is_same< decltype(int_set)::hasher, std::hash<int> >::value, "unexpected hash function" ) ;
    
    my_unordered_set<std::string> str_set ;
    static_assert( std::is_same< decltype(str_set)::hasher, my_string_hash >::value, "unexpected hash function" ) ;
}

http://coliru.stacked-crooked.com/a/47b0ce78f8335149
http://rextester.com/FET76402
Topic archived. No new replies allowed.