create hash function for STL hash map?

[existence19]

Hi
I have to create a hash map with key as string and data as string. i have to create a custom hash function for the hash map, but i don't know how to do that.. can somebody explain and give an example from which i could understand?

[coolbeanbob]

Did your instructor say what your hash function should do?

[vijayan121]

First read up on what a good hash function should do, and choose a hash algorithm.
http://en.wikipedia.org/wiki/Hash_table#Hash_function

Then implement the hash function keeping in mind what C++ requires of the hash function.
For example, if you have opted for the UNIX 32-bit ELF hash,

#include <functional>
#include <string>

//  C++ requirements:
//  must be a function object type that is default_constructible, copy_assignable and swappable
//  must have the nested types 'argument_type' and 'result_type' (std::size_t)
struct elf_hash_32bit : std::unary_function< const std::string&, std::size_t >
{
    // should not throw any exceptions
    std::size_t operator() ( const std::string& key ) const /* can add noexcept or throw() here */
    {
       std::size_t hash = 0U ;
       const std::size_t mask = 0xF0000000 ;

       for( std::string::size_type i = 0 ; i < key.length() ; ++i )
       {
          hash = ( hash << 4U ) + key[i] ;
          std::size_t x = hash & mask ;
          if( x != 0 ) hash ^= ( x >> 24 ) ;
          hash &= ~x ;
       }

       return hash;
    }
};

Instantiate the unordered_map<> with your hash function.

#include <unordered_map>
std::unordered_map< std::string, std::string, elf_hash_32bit > m ;

[existence19]

First read up on what a good hash function should do, and choose a hash algorithm.
http://en.wikipedia.org/wiki/Hash_table#Hash_function

Then implement the hash function keeping in mind what C++ requires of the hash function.
For example, if you have opted for the UNIX 32-bit ELF hash,

#include <functional>
#include <string>

//  C++ requirements:
//  must be a function object type that is default_constructible, copy_assignable and swappable
//  must have the nested types 'argument_type' and 'result_type' (std::size_t)
struct elf_hash_32bit : std::unary_function< const std::string&, std::size_t >
{
    // should not throw any exceptions
    std::size_t operator() ( const std::string& key ) const /* can add noexcept or throw() here */
    {
       std::size_t hash = 0U ;
       const std::size_t mask = 0xF0000000 ;

       for( std::string::size_type i = 0 ; i < key.length() ; ++i )
       {
          hash = ( hash << 4U ) + key[i] ;
          std::size_t x = hash & mask ;
          if( x != 0 ) hash ^= ( x >> 24 ) ;
          hash &= ~x ;
       }

       return hash;
    }
};

Instantiate the unordered_map<> with your hash function.

#include <unordered_map>
std::unordered_map< std::string, std::string, elf_hash_32bit > m ;

:)
Thanks a lot. I understood how it works now. I just didn't understand what this does

std::unary_function< const std::string&, std::size_t >

Thnaks

[chary8088]

stl has not hash map as I know, you can search some open source ,there are many excellent open source library for hash map

[vijayan121]

> I just didn't understand what this does
> std::unary_function< const std::string&, std::size_t >

Google for std::unary_function, perhaps?

Might, just might, throw up results like this: http://www.sgi.com/tech/stl/unary_function.html

[raptr_dflo]

stl has not hash map as I know, you can search some open source ,there are many excellent open source library for hash map

stl::map<> I think does pretty much exactly what anyone would need, with the exception of providing your own hashing function. There's a multimap<> container as well, which supports storing an arbitrary number of values per key (instead of the usual just-one-value).

[raptr_dflo]

[ignore me]

[existence19]

Well I know what a unwary function is. I don't know why we use it here. What if we don't use it?

[vijayan121]

> Well I know what a unwary function is.

Good.

> I don't know why we use it here. What if we don't use it?

Read the third post in this thread once again; this time paying attention to the comment at line number six of the code snippet. And thou shalt be enlightened.