c# - 用于模糊查找的字典哈希函数

Question

当需要对字符串进行近似比较时，基本 Levenshtein Distance可以帮助。它测量要等于另一个字符串所需的字符串修改量:

"aaaa" vs "aaab" => 1
"abba" vs "aabb" => 2
"aaaa" vs "a"    => 3

当使用Dictionary<T, U>时可提供定制IEqualityComparer<T> 。人们可以将编辑距离实现为 IEqualityComparer<string> :

public class LevenshteinStringComparer : IEqualityComparer<string>
{
    private readonly int _maximumDistance;

    public LevenshteinStringComparer(int maximumDistance)
        => _maximumDistance = maximumDistance;

    public bool Equals(string x, string y)
        => ComputeLevenshteinDistance(x, y) <= _maximumDistance;

    public int GetHashCode(string obj)
        => 0;

    private static int ComputeLevenshteinDistance(string s, string t)
    {
        // Omitted for simplicity
        // Example can be found here: https://www.dotnetperls.com/levenshtein
    }
}

所以我们可以使用模糊字典:

var dict = new Dictionary<string, int>(new LevenshteinStringComparer(2));
dict["aaa"] = 1;
dict["aab"] = 2; // Modify existing value under "aaa" key

// Only one key was created:
dict.Keys => { "aaa" }

完成所有这些设置后，您可能已经注意到我们没有实现适当的 GetHashCode在 LevenshteinStringComparer字典将不胜感激。作为有关哈希码的一些经验法则，我会使用:

• 不同的对象不应具有相同的哈希码
• 相等的对象必须具有相同的哈希码

我能想到的遵循这些规则的唯一可能的哈希函数是一个常数，就像在给定代码中实现的那样。但这并不是最佳选择，但是当我们开始采用字符串的默认哈希值时，则 aaa和aab即使它们被平等地处理，最终也会得到不同的哈希值。进一步思考，这意味着所有可能的字符串都必须具有相同的哈希值。

我对吗？为什么当我使用带有哈希冲突的默认字符串哈希函数作为比较器时，字典的性能会变得更好？ 这不应该使字典内的哈希桶无效吗？

public int GetHashCode(string obj)
    => obj.GetHashCode();

Answer 1

我认为没有适合您的情况的哈希函数。

问题是你必须只根据一个signle值来分配bucket，而你无法知道之前添加了什么。但是被散列的项目的编辑距离可以是从 0 到“无穷大”的任何值，唯一重要的是它与什么进行比较。因此，您无法满足哈希函数的第二个条件(相同的对象具有相同的哈希码)。

另一个论点“伪证明”是当你想要最大距离为2并且你已经字典中有两个项目时的情况>，相互距离为 3。如果您添加一个与第一个项目的距离为 2、与第二个项目的距离为 1 的字符串，您将如何决定它应该匹配哪个项目？它满足了这两项的最大值，但它可能应该与第二项而不是第一项匹配。但是不了解字典的内容，您就无法知道如何正确地对其进行哈希处理。

对于第二个问题 - 使用默认的 string.GetHashCode() 方法确实可以提高性能，但它会破坏相等比较器的功能。如果您在示例代码上测试此解决方案，您可以看到 dict 现在将包含两个键。这是因为 GetHashCode 返回了两个不同的哈希码，因此没有冲突，并且 dict 现在有两个存储桶，并且您的 Equals 方法甚至没有执行.