c++ - 元组序列的哈希函数 - 重复消除

Question

我想消除元组序列的重复项。这些序列看起来像这样:

1. (1,1)(2,5,9)(2,3,10)(2,1)
2. (1,2)(3,2,1)(2,5,9)(2,1)
3. (1,1)(2,5,9)(2,3,10)(2,1)
4. (2,1)(2,3,10)(2,5,9)(1,1)
5. (2,1)(2,3,10)(1,1)
6. (1,1)(2,5,9)(2,3,10)(2,2)

每个元组的条目数随着每个序列的元组数而变化。由于我有很多序列，我最终想使用 CUDA 并行处理这些序列，因此我认为计算每个序列的哈希值将是识别重复序列的有效方法。

这样的hash函数是如何实现的？以及:两个不同序列产生相同最终哈希值的碰撞概率有多大？

我有两个要求，我不确定它们是否可以满足:

a) 这样的哈希可以即时计算吗？我想避免存储完整序列，因此我想做这样的事情:

h = 0; // init hash
...
h = h + hash(1,1);
...
h = h + hash(2,5,9);
...
h = h + hash(2,3,10)
... 
h = h + hash(2,1)

其中 + 是组合元组散列的任何运算符。

b) 这样的散列可以独立于序列的“方向”吗？在上面的示例序列 1. 和 4. 中包含相同的元组，但顺序相反，但我喜欢将它们标识为重复项。

Answer 1

对于哈希，您可以使用 std::hash<std::size_t>或您使用的任何(无符号)整数类型。碰撞概率在 1.0/std::numeric_limits<std::size_t>::max() 左右。 ，这是非常小的。为了提高可用性，您可以编写自己的元组哈希器:

namespace hash_tuple
{   
std::size_t hash_combine(std::size_t l, std::size_t r) noexcept
{
    constexpr static const double phi = 1.6180339887498949025257388711906969547271728515625;

    static const double val = std::pow(2ULL, 4ULL * sizeof(std::size_t));

    static const std::size_t magic_number = val / phi;

    l ^= r + magic_number + (l << 6) + (l >> 2);
    return l;
}

template <typename TT>
struct hash
{
    std::size_t operator()(TT const& tt) const noexcept
    {                                              
    return std::hash<TT>()(tt);                                 
    }                                              
};

namespace
{
    template <class TupleT, std::size_t Index = std::tuple_size<TupleT>::value - 1ULL>
    struct HashValueImpl
    {
    static std::size_t apply(std::size_t seed, TupleT const& tuple) noexcept
    {
        seed = HashValueImpl<TupleT, Index - 1ULL>::apply(seed, tuple);
        seed = hash_combine(seed, std::get<Index>(tuple));

        return seed;
    }
    };

    template <class TupleT>
    struct HashValueImpl<TupleT, 0ULL>
    {
    static std::size_t apply(size_t seed, TupleT const& tuple) noexcept
    {
        seed = hash_combine(seed, std::get<0>(tuple));
        return seed;
    }
    };
}

template <typename ... TT>
struct hash<std::tuple<TT...>> 
{
    std::size_t operator()(std::tuple<TT...> const& tt) const noexcept
    {                                              
    std::size_t seed = 0;                             
    seed = HashValueImpl<std::tuple<TT...> >::apply(seed, tt);    
    return seed;                                 
    }                                              
};
}

这样你就可以写出这样的代码

using hash_tuple::hash;
auto mytuple = std::make_tuple(3, 2, 1, 0);
auto hasher = hash<decltype(mytuple)>();

std::size_t mytuple_hash = hasher(mytuple);

满足你的约束b我们需要每个元组 2 个哈希值，正常哈希值和反向元组的哈希值。所以首先我们需要处理如何反转一个:

template<typename T, typename TT = typename std::remove_reference<T>::type, size_t... I>
auto reverse_impl(T&& t, std::index_sequence<I...>)
-> std::tuple<typename std::tuple_element<sizeof...(I) - 1 - I, TT>::type...>
{
    return std::make_tuple(std::get<sizeof...(I) - 1 - I>(std::forward<T>(t))...);
}

template<typename T, typename TT = typename std::remove_reference<T>::type>
auto reverse(T&& t)
-> decltype(reverse_impl(std::forward<T>(t),
                    std::make_index_sequence<std::tuple_size<TT>::value>()))
{
    return reverse_impl(std::forward<T>(t),
                    std::make_index_sequence<std::tuple_size<TT>::value>());
}

然后我们可以计算我们的哈希值

auto t0 = std::make_tuple(1, 2, 3, 4, 5, 6);
auto t1 = std::make_tuple(6, 5, 4, 3, 2, 1);

using hash_tuple::hash;
auto hasher = hash<decltype(t0)>();

std::size_t t0hash = hasher(t0);
std::size_t t1hash = hasher(t1);

std::size_t t0hsah = hasher(reverse(t0));
std::size_t t1hsah = hasher(reverse(t1));

如果hash_combine(t0hash, t1hash) == hash_combine(t1hsah, t0hsah)你找到了你想要的。您可以很容易地将此​​“内部元组哈希机制”应用于许多元组的哈希。玩这个 online !