std::unordered_map<\/h2>\n
The declaration of the hash table std::unordered_map<\/span> reveals a lot of exciting details.<\/p>\n <\/p>\n <\/p>\n Let’s have a closer look at the template parameters. The std::unordered_map<\/span> associates the key (Key<\/span>) with its value (Val<\/span>). The remaining three template parameters are derived from the key and the value type. This statement holds for the hash function (Hash<\/span>), the equality function (KeyEqual<\/span>), and the allocator (Allocator<\/span>). Therefore, it’s quite easy to instantiate a std::unordered_map char2int.<\/span><\/p>\n <\/p>\n Now it gets more interesting. By default, the hash function std::hash<Key><\/span> and the equality function std::equal_to<Key><\/span> are used. Therefore, you can instantiate a std::unordered_map<\/span> with a unique hash or equality function. But stop. Why do we need an equality function? The hash function maps the key to the hash value. The hash value determines the bucket. This mapping can cause a collision. That means different keys go into the same bucket. The std::unorderd_map<\/span> has to deal with these collisions. To do that, it uses the equality function only for completeness reasons. You can adjust the allocation strategy of the container with the Allocator.<\/span><\/p>\n Which requirements have the key and the value of an unordered associative container to fulfill?<\/p>\n The key has to be<\/p>\n The value has to be<\/p>\n {module title=”Mentoring”}<\/p>\n A hash function is good if their mapping from the keys to the values produces few collisions and the hash values are uniformly distributed among the buckets. Because the execution time of the hash function is constant, the access time of the elements can also be constant. Instead of that, the access time in the bucket is linear. Therefore, the overall access time of a value depends on the number of collisions in the bucket, respectively.<\/p>\n The hash function<\/p>\n By applying the theory to my own data types, which I want to use as the key of an unordered associative container, my data type must fulfill two requirements: a hash function and an equality function.<\/p>\n <\/p>\n <\/p>\n <\/p>\n My analysis of the program starts with the main<\/span> function. The easiest way to get the program is to examine the output closely. I create in line 44 the hash function hasVal<\/span> and use them to calculate the hash values in line 48. hasVal<\/span> returns a hash value of type std::size_t. std::size_t<\/span> stands for a sufficiently big enough unsigned integer. MyIntMap<\/span> in line 53 defines a new name for a type. This type uses MyInt<\/span> (lines 7 – 13) as a key. Now, MyIntMap<\/span> needs a hash function and an equality function. It uses MyHash<\/span> (lines 15 -20) as a hash function. The hash function uses the hash function of the data type MyAbsMap<\/span> follows a different strategy. According to its name, MyAbsMap<\/span> creates its hash value based on the absolute value of the integer (line 25). I use the class MyEq<\/span> with the overloaded call operator as an equality function. MyEq<\/span> is only interested in the absolute value of the integer. The output shows that the hash function of MyAbsMap<\/span> returns the same hash value for different keys. The result is that the hash value for MyInt(-2)<\/span> (line 70) is identical to the hash value of MyInt(2)<\/span>. This holds although I didn’t initialize MyAbsMap<\/span> with the pair (MyInt(2),2)<\/span>.<\/p>\n <\/p>\n <\/p>\n One piece of the puzzle is still missing to understand hash tables better. The hash function maps the key onto the value. Therefore, the hash functions map the key of type int<\/span> or std::string<\/span> to its bucket. How is that possible? On the one hand, we have an almost infinite number of keys but only a finite number of buckets. But that is not the only question I have. How many elements go into one bucket? Or to say it differently. How often does a collision occur? Question to which the next post<\/span><\/a> will answer.<\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" The hash function is responsible for the unordered associative containers’ constant access time (best cast). As ever, C++ offers many ways to adjust the behavior of the hash functions. On the one hand, C++ has a lot of different hash functions; on the other hand, you can define your hash function. You can even adjust […]<\/p>\n","protected":false},"author":21,"featured_media":5048,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[364],"tags":[472],"class_list":["post-5049","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-embedded","tag-associative-containers"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5049","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/comments?post=5049"}],"version-history":[{"count":1,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5049\/revisions"}],"predecessor-version":[{"id":6921,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5049\/revisions\/6921"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/5048"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=5049"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=5049"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=5049"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}template<\/span><\r\n class<\/span> Key<\/span>,\r\n class<\/span> Val<\/span>,\r\n class<\/span> Hash<\/span> = std::hash<Key>,\r\n class<\/span> KeyEqual<\/span> = std::equal_to<Key>,\r\n class<\/span> Allocator<\/span> = std::allocator< std::pair<const<\/span> Key, Val> >\r\n> class<\/span> unordered_map<\/span>;<\/pre>\n<\/div>\nstd::unordered_map<char<\/span>,int<\/span>> char2int;<\/pre>\n<\/div>\n\n
\n
The hash function<\/h2>\n
\n
\n\n
\n \n 1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10\r\n11\r\n12\r\n13\r\n14\r\n15\r\n16\r\n17\r\n18\r\n19\r\n20\r\n21\r\n22\r\n23\r\n24\r\n25\r\n26\r\n27\r\n28\r\n29\r\n30\r\n31\r\n32\r\n33\r\n34\r\n35\r\n36\r\n37\r\n38\r\n39\r\n40\r\n41\r\n42\r\n43\r\n44\r\n45\r\n46\r\n47\r\n48\r\n49\r\n50\r\n51\r\n52\r\n53\r\n54\r\n55\r\n56\r\n57\r\n58\r\n59\r\n60\r\n61\r\n62\r\n63\r\n64\r\n65\r\n66\r\n67\r\n68\r\n69\r\n70\r\n71\r\n72\r\n73\r\n74\r\n75\r\n76<\/pre>\n<\/td>\n
\n \/\/ hashFunction.cpp<\/span>\r\n\r\n#include <iostream><\/span>\r\n#include <ostream><\/span>\r\n#include <unordered_map><\/span>\r\n\r\nstruct<\/span> MyInt{\r\n MyInt(int<\/span> v):val(v){}\r\n bool<\/span> operator<\/span>== (const<\/span> MyInt& other) const<\/span> {\r\n return<\/span> val == other.val;\r\n }\r\n int<\/span> val;\r\n};\r\n\r\nstruct<\/span> MyHash{\r\n std::size_t<\/span> operator<\/span>()(MyInt m) const<\/span> {\r\n std::hash<int<\/span>> hashVal;\r\n return<\/span> hashVal(m.val);\r\n }\r\n};\r\n\r\nstruct<\/span> MyAbsHash{\r\n std::size_t<\/span> operator<\/span>()(MyInt m) const<\/span> {\r\n std::hash<int<\/span>> hashVal;\r\n return<\/span> hashVal(abs(m.val));\r\n }\r\n};\r\n\r\nstruct<\/span> MyEq{\r\n bool<\/span> operator<\/span>() (const<\/span> MyInt& l, const<\/span> MyInt& r) const<\/span> {\r\n return<\/span> abs(l.val) == abs(r.val);\r\n }\r\n};\r\n\r\nstd::ostream& operator<\/span> << (std::ostream& strm, const<\/span> MyInt& myIn){\r\n strm << \"MyInt(\"<\/span> << myIn.val << \")\"<\/span>;\r\n return<\/span> strm;\r\n}\r\n\r\nint<\/span> main(){\r\n\r\n std::cout << std::endl;\r\n\r\n std::hash<int<\/span>> hashVal;\r\n\r\n \/\/ a few hash values<\/span>\r\n for<\/span> ( int<\/span> i= -2; i <= 1 ; ++i){\r\n std::cout << \"hashVal(\"<\/span> << i << \"): \"<\/span> << hashVal(i) << std::endl;\r\n }\r\n\r\n std::cout << std::endl;\r\n\r\n typedef<\/span> std::unordered_map<MyInt,int<\/span>,MyHash> MyIntMap;\r\n\r\n std::cout << \"MyIntMap: \"<\/span>;\r\n MyIntMap myMap{{MyInt(-2),-2},{MyInt(-1),-1},{MyInt(0),0},{MyInt(1),1}};\r\n\r\n for<\/span>(auto<\/span> m : myMap) std::cout << '{'<\/span> << m.first << ','<\/span> << m.second << '}'<\/span>;\r\n\r\n std::cout << std::endl << std::endl;\r\n\r\n typedef<\/span> std::unordered_map<MyInt,int<\/span>,MyAbsHash,MyEq> MyAbsMap;\r\n std::cout << \"MyAbsMap: \"<\/span>;\r\n MyAbsMap myAbsMap{{MyInt(-2),-2},{MyInt(-1),-1},{MyInt(0),0},{MyInt(1),1}};\r\n\r\n for<\/span>(auto<\/span> m : myAbsMap) std::cout << '{'<\/span> << m.first << ','<\/span> << m.second << '}'<\/span>;\r\n\r\n std::cout << std::endl << std::endl;\r\n\r\n std::cout << \"myAbsMap[MyInt(-2)]: \"<\/span> << myAbsMap[MyInt(-2)] << std::endl;\r\n std::cout << \"myAbsMap[MyInt(2)]: \"<\/span> << myAbsMap[MyInt(2)] << std::endl;\r\n std::cout << \"myAbsMap[MyInt(3)]: \"<\/span> << myAbsMap[MyInt(3)] << std::endl;\r\n\r\n std::cout << std::endl;\r\n\r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\nint<\/code> internally. I already overload the equality function for MyInt.<\/p>\n![\"hashfunction\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2016\/11\/hashfunction.png\")
<\/p>\nWhat’s next?<\/h2>\n