Suppose I need to make some kind of template container Map on a hash table. The container, naturally, can take on a key the value of any type - how, in that case, to write a hash function? How to cast an arbitrary type T (for which the cast operator may not be overloaded) to an integer type? It seems like a reinterpret_cast should help, which leads to a pointer, but the construction of the form

reinterpret_cast <size_t*> (key);

Fails to compile when key is a non-integer type.

If we bring the pointer to the pointer (as in the example on msdn)

 reinterpret_cast <size_t*> (&key);

then the hash of the table is lost - a search through it will not work, since a key with an identical value will have a different address, and the result of the hash function will also be different.

Is it possible to somehow forcibly interpret the bytes of an arbitrary object in memory as an integral type? Generally, which solution will be the right one? How is this problem solved in std::unordered_map or QMap ?

  • there is no arbitrary their number may not coincide with the size of an integer. That's how you trite a string of 100 characters just lead to the number. - pavel
  • Well, if this is a C string, which is a pointer to char (4 bytes in size), then I extract the first two bytes I need for the int, for example :) Well, that would be possible. But how, in this case, are containers of type std :: unordered_map or QMap, which accept keys of any type, implemented? In Java, emnip, each object has its own integer hash code, but in the pluses? - NikBond
  • and to sense from function hash by the first characters of a line? it's almost useless. The normal hash function will depend on all characters in the string. The containers most likely use the method of getting the hash of the object - the key, and just call it. And emnip is the same pointer can be said. - pavel
  • one
    violating the rules of the standard, you can simply do *(int *)(&key) but that’s the point ... - pavel
  • 2
    in std::unordered_map this problem is not solved. try for example to create std::unordered_map< pair<int,int> , int > - pavel

1 answer 1

Classes like unordered_set do not calculate the hash themselves, but use std::hash (and also allow the user to specify his own hashing implementation, if he is not satisfied with the standard or if it does not exist).

std::hash , in turn, also does not use any special magic, but simply has a template specialization for primitive types, strings and pointers (normal and "smart").

I think you should not reinvent the wheel, but use the same idea. Even easier, just use std::hash . Believe me, there are many difficulties in writing a container besides this one.

So just use

 size_t hash_value = std::hash<T>()(t);