Hashing

Questions 1 to 5 of 8

1. 1. A hash table holds 20 keys in 29 buckets. What is its load factor, rounded to two decimal places?

   1.450.690.5020.00
2. 2. The toy table in example 1 puts cat, act and tac into bucket 2, in that order. How many comparisons does get("tac") make?

   1 comparison2 comparisons0 comparisons3 comparisons
3. 3. What does this program print? ``cpp #include <functional> #include <iostream> #include <string> #include <unordered_set> struct Code { std::string text; bool operator==(const Code&) const = default; }; namespace std { template <> struct hash<Code> { std::size_t operator()(const Code& c) const noexcept { return std::hash<std::string>{}(c.text); } }; } // namespace std int main() { std::unordered_set<Code> s; s.insert(Code{"ab"}); s.insert(Code{"ab"}); s.insert(Code{"ba"}); std::cout << s.size() << ' ' << s.contains(Code{"ba"}) << ' ' << s.contains(Code{"AB"}) << '\n'; } ``

   2 1 02 1 13 1 01 0 0
4. 4. What does this program print? ``cpp #include <functional> #include <iostream> #include <unordered_map> struct Point { int x; int y; bool operator==(const Point&) const = default; }; namespace std { template <> struct hash<Point> { std::size_t operator()(const Point& p) const noexcept { return std::hash<int>{}(p.x) * 7 + std::hash<int>{}(p.y); } }; } // namespace std int main() { std::unordered_map<Point, int> m; m[Point{1, 2}] += 5; m[Point{2, 1}] = 3; m[Point{1, 2}] += 10; std::cout << m.size() << '\n'; std::cout << m[Point{1, 2}] << '\n'; } ``

   3, then 152, then 52, then 151, then 15
5. 5. The key type below is meant to work in an unordered_set. What is wrong with it? ``cpp struct Point { int x; int y; bool operator==(const Point& o) const { return x == o.x; } }; namespace std { template <> struct hash<Point> { std::size_t operator()(const Point& p) const noexcept { return std::hash<int>{}(p.x) * 31 + std::hash<int>{}(p.y); } }; } // namespace std ``

   The hash should return int, not std::size_toperator== compares only x, but the hash uses y too, so Point{1, 2} and Point{1, 3} count as equal and can still hash differentlyoperator() must not be marked noexceptPoint needs a constructor that takes two ints