无序多集的hash/crc算法

Question

比方说，我想要创建一个无序集合，该集合是无符号整数的无序多集。为此，我需要创建一个散列函数来计算无序多集的散列。事实上，它也必须对CRC有好处。

一个显而易见的解决方案是将这些项放入向量中，对它们进行排序，然后返回结果的散列。这似乎是有效的，但它是昂贵的。

另一种方法是对值进行xor运算，但很明显，如果一项有两次或没有一项，结果将是相同的-这是不好的。

有没有什么想法可以让我更便宜地实现这个功能--我有一个应用程序，它可以处理数千个集合，而且是相对较大的集合。

Answer 1

这是一个合理的std::unordered_multiset<int>哈希函数，如果计算是一个大素数就更好了，但这个想法是成立的。

#include <iostream>
#include <unordered_set>

namespace std {
    template<>
    struct hash<unordered_multiset<int>> {
        typedef unordered_multiset<int> argument_type;
        typedef std::size_t result_type;

        const result_type BASE = static_cast<result_type>(0xA67);

        result_type log_pow(result_type ex) const {
            result_type res = 1;
            result_type base = BASE;
            while (ex > 0) {
                if (ex % 2) {
                    res = res * base;
                }
                base *= base;
                ex /= 2;
            }
            return res;
        }

        result_type operator()(argument_type const & val) const {
            result_type h = 0;
            for (const int& el : val) {
                h += log_pow(el);
            }
            return h;
        }
    };
};

int main() {
    std::unordered_set<std::unordered_multiset<int>> mySet;
    std::unordered_multiset<int> set1{1,2,3,4};
    std::unordered_multiset<int> set2{1,1,2,2,3,3,4,4};
    std::cout << "Hash 1: " << std::hash<std::unordered_multiset<int>>()(set1) 
              << std::endl;
    std::cout << "Hash 2: " << std::hash<std::unordered_multiset<int>>()(set2) 
              << std::endl;
    return 0;
}

Output

Hash 1: 2290886192
Hash 2: 286805088

当它是素数p时，碰撞的数量与1/p成正比，我不确定2的幂的分析是什么。通过在插入/删除整数x时添加/减去基数^x，可以有效地更新散列。

Answer 2

将内部多集实现为value->count散列映射。

这将允许您避免偶数个元素通过xor以以下方式抵消的问题:不是对每个元素进行xor运算，而是从计数和值构造一个新的数字(例如，将它们相乘)，然后您可以使用xor构建完整的散列。