Exercise 12. Hashing.

This exercise is supposed to demonstrate the proper way to write hash functions for your own user-defined types.

Exercise 12a. Hashing const char*.

Open this wandbox (b, b). It contains some code that attempts to use std::unordered_map<const char*, int> but which doesn't currently work — because the default std::hash<const char *> hashes the pointer values instead of the pointed-to strings. (It doesn't even assume that the pointers point to C-style null-terminated strings. Which makes sense, in general.)

1. Open "CStringHash.h" and implement the one-argument operator()(const char *). You can write your own hash function, or you can delegate all the hard work to std::hash<std::string_view>.

If you delegate to std::hash, remember that the syntax is std::hash<std::string_view>{}(s). You are default-constructing an instance of type std::hash<std::string_view> and then invoking its operator() with one argument; you are not calling a function named std::hash with one argument.

2. Run the code. Even if you have implemented your hash function correctly, you will see that the map still has 4 key-value pairs, not 2! Recall that std::unordered_map takes five template parameters:

    unordered_map<KeyType, ValueType, Hash, KeyEqual, Allocator>
The fourth template parameter defaults to std::equal_to<KeyType>. You have implemented a correct Hash operation, so that hello1 and hello2 hash into the same hash bucket. However, because of the default equal_to comparator, these two pointer values still ultimately compare unequal and result in two separate entries within the same bucket.

3. Change the comparator parameter in the declaration of m away from the default, so that hello1 and hello2 will not only hash into the same bucket, but also compare equal. Now you should see the expected output from main()!

Exercise 12b (optional). Transparent comparators

1. (Optional) Open this wandbox (b, b, b). The last line of main() is attempting to use std::set::count() with an argument of a type that is not convertible to my::Person.

Implement the missing parts of the comparator object PersonLessThan, so that main() compiles and runs as expected. You do not need to modify struct Person at all.

2. (Optional) Can you implement similar heterogeneous-count() behavior for an unordered_set of Person? Why or why not? (Check the cppreference entry for unordered_set::count().)

3. If you were to implement your own hash-table class template, my::unordered_set, could you implement support for heterogeneous comparators? Would you require that Hash::is_transparent, KeyEqual::is_transparent, both, or neither? Would you allow Hash and KeyEqual to be different types in the first place? Why or why not?


You're done with this set of exercises! Sit back and relax, or optionally, browse the following blog posts.