6

我想使用由 boost's 实现的缓存，unordered_map从 adynamic_bitset到 a dynamic_bitset。当然，问题在于 bitset 中没有默认的散列函数。这似乎不是一个概念问题，但我不知道如何解决技术问题。我该怎么做？

4

5 回答 5

6

我找到了一个意想不到的解决方案。事实证明，boost 可以选择#define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS. 定义后，包括私有成员在内的私有成员将m_bits变为公共成员（我认为它可以处理旧的编译器或其他东西）。

所以现在我可以使用@KennyTM 的答案，稍微改变一下：

namespace boost {
    template <typename B, typename A>
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) {            
        return boost::hash_value(bs.m_bits);
    }
}
于 2010-10-09T17:58:36.347 回答
3

有一个to_block_range功能可以将 bitset 包含的单词复制到某个缓冲区中。为避免实际复制，您可以定义自己的“输出迭代器”，它只处理单个单词并从中计算哈希值。关于。如何计算哈希：参见例如 FNV 哈希函数。

不幸的是，dynamic_bitset恕我直言，它的设计是脑残，因为它不能让您直接访问底层缓冲区（甚至不作为const）。

于 2010-10-09T16:32:10.423 回答
3

这是一个功能请求。

可以通过将位集转换为临时向量来实现效率不高的唯一哈希：

namespace boost {
    template <typename B, typename A>
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) {
        std::vector<B, A> v;
        boost::to_block_range(bs, std::back_inserter(v));
        return boost::hash_value(v);
    }
}
于 2010-10-09T16:32:36.627 回答
2

我们不能直接计算哈希，因为里面的底层数据dynamic_bitset是私有的（m_bits）

但是我们可以很容易地绕过（颠覆！）c++ 访问规范系统，而无需任何一个

  • 破解代码或
  • 假装你的编译器不合格（BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS）

关键是模板函数to_block_range，它是一个friendto dynamic_bitset。因此，此功能的专业化也可以访问其私有数据（即m_bits）。

生成的代码再简单不过了

namespace boost {


// specialise dynamic bitset for size_t& to return the hash of the underlying data
template <>
inline void
to_block_range(const dynamic_bitset<>& b, size_t& hash_result)
{
    hash_result = boost::hash_value(bs.m_bits);
}

std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) 
{            
    size_t hash_result;
    to_block_range(bs, hash_result);
    return hash_result;
}
}
于 2011-11-28T14:29:27.993 回答
0

建议的解决方案在以下情况下生成相同的哈希。

#define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS

namespace boost {
    template <typename B, typename A>
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) {            
        return boost::hash_value(bs.m_bits);
    }
}

boost::dynamic_biset<> test(1,false);

auto hash1 = boost::hash_value(test);

test.push_back(false);

auto hash2 = boost::hash_value(test);

// keep continue...

test.push_back(false);

auto hash31 = boost::hash_value(test);

// magically all hash1 to hash31 are the same!

建议的解决方案有时不适用于哈希映射。

我阅读了 dynamic_bitset 的源代码为什么会发生这种情况，并意识到 dynamic_bitset 每个值存储一位与vector<bool>. 例如，您调用dynamic_bitset<> test(1, false)，然后 dynamic_bitset 最初分配 4 个全为零的字节，它保存位的大小（在这种情况下，大小为 1）。请注意，如果位的大小大于 32，则它会再次分配 4 个字节并将其推回dynamic_bitsets<>::m_bits（因此 m_bits 是 4 个字节块的向量）。

如果我调用test.push_back(x)，它会将第二位设置为 x 并将位的大小增加到 2。如果x为假，则m_bits[0]根本不会改变！为了正确计算哈希，我们需要在哈希计算中使用 m_num_bits。

那么，问题是如何？

1：使用boost::hash_combine 这种方法简单直接。我没有检查这个编译与否。

namespace boost {
    template <typename B, typename A>
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) { 
        size_t tmp = 0;
        boost::hash_combine(tmp,bs.m_num_bits);           
        boost::hash_combine(tmp,bs.m_bits);
        return tmp;
    }
}

2：翻转 m_num_bits % bits_per_block th 位。根据位大小翻转位。我相信这种方法比 1 更快。

namespace boost {
    template <typename B, typename A>
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) {
        // you may need more sophisticated bit shift approach.
        auto bit = 1u << (bs.m_num_bits % bs.bits_per_block);
        auto return_val = boost::hash_value(bs.m_bits);

       // sorry this was wrong
       //return (return_val & bit) ? return_val | bit : return_val & (~bit);
       return (return_val & bit) ? return_val & (~bit) : return_val | bit;
    }
}
于 2016-07-13T14:43:34.083 回答