c++ - 动态 equal_to 函数 unordered_map boost

Question

我有一个到 int 的无序映射字符串，它使用定义为的自定义 equal_to 函数:

bool hashEqual::operator ()(const string &a, const string &b) const
{
    if (a.size() != b.size())
        return false;

    return std::inner_product(
        a.begin(), a.end(), b.begin(),
        0, std::plus<unsigned int>(),
        std::not2(std::equal_to<std::string::value_type>())
        ) <= 8;  
}           

基本上，如果两个键的汉明距离等于或小于 8，则它的作用是相同的键。

问题是我希望距离阈值是动态的，以便让用户通过命令行设置它。不是 8，而是变量 threshold 或类似的东西。

我不是在寻找像全局变量这样的 hack(除非它是实现此目的的唯一方法)，而是在寻找“好方法”。

Answer 1

为什么 `unordered_map` 不能可靠地工作

一个好的通用散列函数以可重复但看似随机的方式将键映射到桶，我的意思是，如果键有一点变化，那么桶在统计上应该是不相关的——就好像你随机选择了另一个。因此，假设您有一个包含一些现有元素的哈希表:

[ bucket 0 - "abcde fghij" ]
[ bucket 1 - <empty> ]
[ bucket 2 - <empty> ]
[ bucket 3 - "01234 56789", "77777 QQQQQ" ]  (2 colliding values for this bucket)
[ bucket 4 - "XXXXX YYYYY" ]
[ bucket 5 - <empty> ]

如果你过来插入说 "Abcde fghij"那么你可以散列到这些桶中的任何一个 - 你应该没有比其他任何桶更多的桶 0 的机会，但如果那个桶 不是 桶 0​​ 那么您甚至永远不会尝试与“abcde fghij”进行汉明距离感知相等性比较。

---

为什么 `multimap` 不能可靠地工作

假设我们有一个 multimap在其中包含一些现有字符串(S1 到 S6，按字典顺序递增 - 每个元素与其他元素的汉明距离大于 8)，实际的平衡二叉树可能看起来有点像:

            S4
          /    \
        S2       S6
       /  \     /  \
      S1   S3  S5

现在，假设 S1 恰好是 "Abcde fghij" , S4 是 "ZZZZZ ZZZZZ"然后我们去插入 "abcde fghij" :

• 即使使用汉明距离比较，"ZZZZZ ZZZZZ" < "abcde fghij" (记住 'Z' < 'a' 是 ASCII 顺序)所以 multimap期待 "abcde fghij"存储在树的右侧...

• "abcde fghij"然后与 S6 进行比较，如果少于 S5，则会相应地插入，但关键是永远不会与 S1 进行任何比较

---

这让我回到我之前的评论:

I don't think there's any simple and correct way to do the comparisons other than brute force (try every combination). And results vary for same data in another order.