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
Top comments (5)
Hi! what's the example use case for such container? can you merge vec into a single long string?
Thanks for the comment!. The use case was to keep unique permutations of some set and then compare them pairwise or something like that. I like the idea of a long string, I'll try to apply it.
so rather than storing a full set you can store ids for the permutation like a vector of idsr: 1, 2, 3, 4, 5: and then another vector with 5, 4, 1, 2, 3... etc.
Good idea, thanks!
happy to see results, if that's faster and how :)