unordered_map: vector< string > as key

Vardan — Wed, 14 Apr 2021 19:25:56 +0000

I recently ran into a problem that required storing
vector< string > in unordered_map as a key.
I have searched on the web for a solution but haven't found one. So I've decided to use what I already know to solve this.
I just would like to share my solution and hope that for somebody it can be useful.

struct hasher {
        long long operator()(const vector<string>& v) const {            
            int prime = 31;
            long long mod = 1e9 + 9;
            long long hash = 0;
            for(string s: v) {
                long long string_hash{};
                long long pow = 1;
                for(int i = 0; i < s.length(); ++i) {
                    string_hash = (string_hash + (s[i] - '0' + 1) * pow) % mod;
                    pow = (prime * pow) % mod;
                }
                hash = (hash + string_hash + (prime * hash) % mod) % mod;
            }
            return hash;
        }
    };
unordered_map<vector<string>, int, hasher> mp{};
// can be used just like any other unordered_map

In this approach, I've used rolling hash algo to calculate the hash of each string, and then I've added them to the resulting hash. The total complexity of the function is O(N * max_n), where N is the size of the input vector and max_n is the length of the string with max length into the input vector.
I would be glad for any suggestions about optimization/improvements of this code :)

References:

cp-algorithms - https://cp-algorithms.com/string/string-hashing.html
CodeNCode - https://www.youtube.com/watch?v=zURFD55lGBI

DEV Community: Vardan

unordered_map: vector< string > as key