A good hash function for a vector

Crafting Effective Hash Functions for std::vector in C++

Explore various strategies for creating robust hash functions for std::vector in C++, covering common pitfalls, best practices, and performance considerations.

Hashing std::vector instances in C++ is a common requirement, especially when using them as keys in hash-based containers like std::unordered_map or std::unordered_set. Unlike primitive types or std::string, std::vector does not provide a default std::hash specialization that considers its contents. This means you need to implement a custom hash function. A good hash function is crucial for performance, as it minimizes collisions and ensures efficient lookup times. This article will guide you through creating effective hash functions for vectors, discussing different approaches and their implications.

The Need for Custom Hashing

By default, std::hash<std::vector<T>> is not defined in the C++ standard library. If you try to use std::vector<T> directly as a key in std::unordered_map, you'll encounter a compilation error. This is because the standard library cannot make assumptions about how you want to hash a sequence of elements. A simple pointer-based hash would only hash the vector's address, not its contents, leading to incorrect behavior where two vectors with the same elements but different memory locations would be considered unequal. Therefore, a custom hash function must iterate over the vector's elements and combine their individual hashes.

flowchart TD
    A[std::vector<T> as key] --> B{std::unordered_map/set?}
    B -- No default hash --> C[Compilation Error]
    B -- Custom hash needed --> D[Implement `std::hash` specialization]
    D --> E[Combine element hashes]
    E --> F[Efficient container usage]

Flowchart illustrating the necessity of custom hash functions for std::vector.

Combining Hashes: The Boost Approach

A widely adopted and robust method for combining hashes is inspired by Boost's hash_combine function. This technique iteratively updates a seed hash value by mixing it with the hash of each element. The general formula is seed ^= std::hash<T>()(element) + 0x9e3779b9 + (seed << 6) + (seed >> 2);. The constant 0x9e3779b9 is the golden ratio conjugate, often used in hash functions for its good distribution properties. The bit shifts help to mix the bits thoroughly, reducing collisions.

#include <vector>
#include <functional>
#include <numeric>

// Custom hash for std::vector<T>
namespace std {
    template <typename T>
    struct hash<std::vector<T>> {
        size_t operator()(const std::vector<T>& v) const {
            size_t seed = v.size();
            for (const T& i : v) {
                seed ^= hash<T>()(i) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
            }
            return seed;
        }
    };
}

// Example usage:
#include <iostream>
#include <unordered_map>

int main() {
    std::vector<int> vec1 = {1, 2, 3};
    std::vector<int> vec2 = {1, 2, 3};
    std::vector<int> vec3 = {3, 2, 1};

    std::unordered_map<std::vector<int>, std::string> myMap;
    myMap[vec1] = "Vector One";
    myMap[vec3] = "Vector Three";

    std::cout << "Hash of vec1: " << std::hash<std::vector<int>>{}(vec1) << std::endl;
    std::cout << "Hash of vec2: " << std::hash<std::vector<int>>{}(vec2) << std::endl;
    std::cout << "Hash of vec3: " << std::hash<std::vector<int>>{}(vec3) << std::endl;

    if (myMap.count(vec2)) {
        std::cout << "Found vec2 in map: " << myMap[vec2] << std::endl;
    }

    return 0;
}

Implementing std::hash specialization for std::vector<T> using the Boost-inspired hash_combine technique.

Considerations for Element Types

The effectiveness of your vector hash function heavily depends on the hash functions of its individual elements. If T itself is a custom type, you must ensure std::hash<T> is defined for it. This can be done by providing a std::hash specialization for T or by implementing a operator() for a custom hash struct. If T is a complex object, ensure its operator== and hash function are consistent: if a == b, then hash(a) must equal hash(b).