2

The keys in my std::unordered_map are boost::uuids::uuids, thus 128 bit hashes considered unique. However, the compiler can't know that and therefore says this.

error C2338: The C++ Standard doesn't provide a hash for this type.

How can I make the map use the keys as hashes as they are? By the way, std::size_t is defined as unsigned int __w64 on my system, which I think refers to only 64 bits.

danijar
  • 32,406
  • 45
  • 166
  • 297

4 Answers4

2

You always need to provide a function object mapping the key to a hash value even if this mapping is the identity. You can either define a specialization for std::hash<boost::uuids::uuid> and have the std::unordered_map<K, V> pick this one up automatically or you can parameterize the unordered map with additional template parameter for the function object type. In addition to the hash an equality operation is also needed but the default, using operator==() is probably OK.

That said, the hash value won't accept a 128-bit integer unless your system has a built-in 128-bit integer type. The hash value needs to be a std::size_t to be usable with the standard unordered containers. The complete list of requirements for std::hash<T> specializations is listed in 20.8.12 [unord.hash]:

  1. std::hash<X> needs to be default constructible, copy constructible, and copy assignable.
  2. std::hash<X> needs to be swappable.
  3. It needs to provide two nested types argument_type for the key type and result_type for the type of the hashed value with the latter being the same as std::size_t.
  4. For the function the relation k1 == k2 => h(k1) == h(k2) needs to be true where h is the hashing function object.

So, you will need to define something along the lines of this:

namespace std {
    template <>
    struct hash<boost::uuids::uuid>
    {
        typedef boost::uuids::uuid argument_type;
        typedef std::size_t        result_type;
        std::size_t operator()(boost::uuid::uuid key) const {
            return transform_to_size_t(key);
        }
    };
}

where transform_to_size_t() is the actual transformation you'll need to provide. };

Dietmar Kühl
  • 150,225
  • 13
  • 225
  • 380
  • If guaranteed uniqueness is required, you would have to ensure size_t bits of the hash is also unique in your application. Clearly an n->1 transform cannot preserve uniqueness. – OllieB Aug 31 '13 at 14:12
  • @OllieB: I'm not sure what you refer to. If you refer to the requirement that the hash of equivalent keys has to be equivalent, you should not that logic operation is an implication: clearly, the reverse isn't true: `h(k1) == h(k2)` does not imply that `k1 == k2`. – Dietmar Kühl Aug 31 '13 at 15:57
  • 2
    Kuhl: I was referring to your transform_to_size_t function. This potentially breaks the uniqueness of the hash. For instance, a 128 hash converted to a 32 bit hash gives 2^(128-32) collisions from the original 128 bit UUID space. These may or may not be significant. – OllieB Aug 31 '13 at 23:37
  • You could of course just take the lowest 32 bits for instance, but then you would have to ensure that those bits of the original 128 bit hash are unique, which may not be the case. – OllieB Aug 31 '13 at 23:39
  • 1
    @OllieB: Correct: the hashes won't be unique but the unordered container won't use that many buckets anyway. In addition to the hash value you always also need an equivalence function. – Dietmar Kühl Aug 31 '13 at 23:40
  • Kuhl: You are assuming that the 128 bit hashes of the data set are uniformly distributed. They may not be, and the collisions over even quite a large data set may be intolerable, unless you can guarantee properties of boost::uuid – OllieB Sep 01 '13 at 11:14
1

you need to provide a hash function for type boost::uuids::uuid. Since it is unique, you can just use stl identity.

Here is the declaration of unordered_map.

template < class Key,                                    // unordered_map::key_type
           class T,                                      // unordered_map::mapped_type
           class Hash = hash<Key>,                       // unordered_map::hasher
           class Pred = equal_to<Key>,                   // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
           > class unordered_map;
CS Pei
  • 10,869
  • 1
  • 27
  • 46
0

I think the simplest way is to implement an specialization of std::hash for that types, which returns the same input:

namespace std
{
    template<>
    struct hash<Foo>
    {
        Foo operator(const Foo& foo)
        {
            return foo;
        }
    };
}

Supposing that the type, Foo in the example, is implicitly convertible to std::size_t.

In your case, the type is a 128 bits GUID, and std::size_t uses 32 or 64 bits. You could split the 128 bits GUID in parts of 64/32 bits, and combine the values.

Manu343726
  • 13,969
  • 4
  • 40
  • 75
  • The type you called `Foo` actually is [`boost::uuids::uuid`](http://www.boost.org/doc/libs/1_54_0/libs/uuid/uuid.html) which holds a 128 bits [GUID](http://en.wikipedia.org/wiki/GUID). On my system, `std::size_t` only holds 64 bits, I think. – danijar Aug 31 '13 at 13:29
  • 1
    You could split the number in two parts of 64bits, and combine the bits in a hash manner. See the std::hash custom specialization example which the link to cppreference.com I have provided has. It uses two hash values from strings and combines them. – Manu343726 Aug 31 '13 at 13:32
  • Then I won't have to use 128 bit GUIDs at all. – danijar Aug 31 '13 at 13:41
  • 2
    @danijar: If the only reason you are using 128 bit GUIDs is to avoid hash collisions, then yes, you don't need to use 128 bit GUIDs at all. – Nemo Aug 31 '13 at 14:21
  • 1
    I think that declaration should be: Foo operator()(const Foo& foo) const noexcept {...}. That's what I needed to get g++ to accept a similar declaration without warnings or errors. – dewtell Jul 02 '17 at 20:56
0

I found no way to use UUIDs as keys for std::unordered_map since the UUID is 128 bits long while the hash for the map is std::size_t which only can hold 64 bits.

Instead, I dropped real 128 bits UUIDs for only 64 bit ids which can be stored in the uint64_t type and are natively supported by containers of the standard library.

danijar
  • 32,406
  • 45
  • 166
  • 297