std::hash

[Christopher Pisz]

I want to use a custom structure for a key in an std::unordered_map. The compiler complains that C++ does not provide a hash function for that type. From what I can find in googling, I need to implement some manner of hash operator. Can someone help me with a small example?

Let's assume I have

struct MyClass
{
std::string m_id1;
int m_id2;
int m_id3;
};

where a combination of all 3 ids are unique, but none are unique on their own.

What do I need to do to use this as a key in std::unordered_map?

I see https://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-type-as-the-key

but I do not understand the actual hashing he is doing there.

[Marcel Mueller]

On 13.10.17 16.49, Christopher Pisz wrote:
> I want to use a custom structure for a key in an std::unordered_map. The compiler complains that C++ does not provide a hash function for that type. From what I can find in googling, I need to implement some manner of hash operator. Can someone help me with a small example?

[...]

> What do I need to do to use this as a key in std::unordered_map?
>
> I see https://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-type-as-the-key
>
> but I do not understand the actual hashing he is doing there.

The code in the first reply is exactly what yo need, i.e. the
specialization of std::hash for your type. A typical implementation
calls std::hash for each member and combines the result somehow.


Marcel

[Ben Bacarisse]

Christopher Pisz <christo...@gmail.com> writes:

> I want to use a custom structure for a key in an
> std::unordered_map. The compiler complains that C++ does not provide a
> hash function for that type. From what I can find in googling, I need
> to implement some manner of hash operator. Can someone help me with a
> small example?
>
> Let's assume I have
>
> struct MyClass
> {
> std::string m_id1;
> int m_id2;
> int m_id3;
> };
>
> where a combination of all 3 ids are unique, but none are unique on
> their own.
>
> What do I need to do to use this as a key in std::unordered_map?

A relatively minimal example would be:

struct MyClass
{
std::string m_id1;
int m_id2;
int m_id3;

bool operator==(const MyClass &mc) const {
return m_id1 == mc.m_id1 && m_id2 == mc.m_id2 && m_id3 == mc.m_id3;
}
};

struct MyClassHash {
std::size_t operator()(const MyClass &k) const
{
return std::hash<std::string>()(k.m_id1) ^
std::hash<int>()(k.m_id2) ^
std::hash<int>()(k.m_id3);
}
};

int main()
{
std::unordered_map<MyClass, std::string, MyClassHash> map = {
{ {"abc", 1, 2}, "ABC"},
{ {"def", 2, 3}, "DEF"}
};
}

You can even use the class itself as a hash functor (an object that
behaves like a function) by defining a member function

std::size_t operator()(const MyClass &k) const

in it rather than in a separate struct, but that mean you can never use
the () operator on your class for anything else.

<snip>
--
Ben.

[Christopher Pisz]

On Friday, October 13, 2017 at 10:07:27 AM UTC-5, Marcel Mueller wrote:
> On 13.10.17 16.49, Christopher Pisz wrote:
> > I want to use a custom structure for a key in an std::unordered_map. The compiler complains that C++ does not provide a hash function for that type. From what I can find in googling, I need to implement some manner of hash operator. Can someone help me with a small example?
> [...]
> > What do I need to do to use this as a key in std::unordered_map?
> >
> > I see https://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-type-as-the-key

SNIP

> The code in the first reply is exactly what yo need, i.e. the
> specialization of std::hash for your type. A typical implementation
> calls std::hash for each member and combines the result somehow.
>
>
> Marcel

So my attempt looks like this


#pragma once

// Standard Includes
#include <unordered_map>
#include <string>


//--------------------------------------------------------------------------------------------------
namespace MyNamespace
{
namespace Domain
{

//--------------------------------------------------------------------------------------------------
enum MyEnum
{
VAL_1,
VAL_2
};

//--------------------------------------------------------------------------------------------------
/// Contains information (that we care about) that identifies an XTend client.
/// These details are passed to the Mid Level when we make requests
struct __declspec(dllexport) MyClass
{
MyClass();
MyClass(const std::string & nonUniqueId
, bool isOn
, const MyEnum & myEnum);
~MyClass();

MyClass(const MyClass & rhs);
MyClass(const MyClass && rhs);

MyClass & operator = (const MyClass & rhs);
MyClass & operator = (const MyClass && rhs);

bool operator < (const MyClass & rhs) const;
bool operator == (const MyClass & rhs) const;


std::string m_nonUniqueId;
bool m_isOn;
MyEnum m_myEnum;
};

//--------------------------------------------------------------------------------------------------

} // End namespace
} // End namespace

//--------------------------------------------------------------------------------------------------
template<> struct std::hash<MyNamespace::Domain::MyClass>
{
typedef MyNamespace::Domain::MyClass argument_type;
typedef std::size_t result_type;
result_type operator()(argument_type const& s) const noexcept
{
result_type const h1(std::hash<std::string>{}(s.m_nonUniqueId));
result_type const h2(std::hash<bool>{}(s.m_isOn));
result_type const h3(std::hash<int>{}(s.m_myEnum));
return (h1 ^ (h2 << 1) ^ h3 << 2);
}
};


This line that I don't understand is
return (h1 ^ (h2 << 1) ^ h3 << 2);

^ is XOR and << is bit shift. Is this correct? If so, how does this contribute to my making a unique size_t or something that is close to unique? Can someone break that down a bit?

[Marcel Mueller]

On 13.10.17 18.09, Christopher Pisz wrote:
> This line that I don't understand is
> return (h1 ^ (h2 << 1) ^ h3 << 2);
>
> ^ is XOR and << is bit shift. Is this correct?
> If so, how does this contribute to my making a unique size_t or something that is close to unique? Can someone break that down a bit?

Well, the idea is to combine the hash values of the components in an
asymmetric way to avoid hash collisions when two components are swapped.

Using left shift is not that ideal because it discards bits. A bit
rotation would perform better. Unfortunately C++ misses this kind of
operator, although almost any existing hardware support it.

Better implementations use more complex polynomials. In fact writing
good hash functions is a rather challenging task.

For your purpose it is just fine since nether the boolean nor the enum
provide enough bits that anything gets lost.


Marcel

[asetof...@gmail.com]

Ben B. Wrote:
struct MyClassHash {
std::size_t operator()(const MyClass &k) const
{
return std::hash<std::string>()(k.m_id1) ^
std::hash<int>()(k.m_id2) ^
std::hash<int>()(k.m_id3);
}
};

-----
If size_t is the return type of hash<T>()const
if sizeof(size_t)>=sizeof(int)

why use one hash function and not just the value, in this case k.m_id3?

[asetof...@gmail.com]

Something as

struct MyClassHash {
std::size_t operator()(const MyClass &k) const
{

return std::hash<std::string>()(k.m_id1) ^ (k.m_id2) ^ (k.m_id3);
}
};