1

我想实现一个算法Dictionary<Dictionary<char,int>, List<string>>来查找字典中的字谜单词。

由于我需要EqualityComparer为此字典实现我的自定义，访问时间仍然是 O(1) 即大 O (1) 吗？

第二个问题，作为其中的一部分，EqualityComparer我还需要实现GetHashCode(). GetHashCode()确定的有效方法是Dictionary<Dictionary<char,int>, List<string>>什么？

我只是想出了这个方法，有没有更好的选择？

public int GetHashCode(Dictionary<char, int> obj)
    {
        unchecked
        {
            int hashCode = 17;
            foreach (var item in obj)
            {
                hashCode += 23 * item.Key.GetHashCode();
            }
            return hashCode;
        }
    }

任何意见表示赞赏。谢谢！

4

3 回答 3

2

a 的访问时间Dictionary<TKey, TValue> 接近O(1)，但并非完全如此。在理想情况下（良好的分布/很少的冲突），您可以将其视为 O(1)。在由于 GetHashCode 值的低方差导致大量冲突的情况下，访问时间会降低并且可能接近 O(N)。

于 2012-01-15T00:00:17.220 回答
2

如何将单词“need”转换为字符串“d1e2n1”而不是使用字典作为键？为了构建此字符串，您可以使用二叉树。字符将用作键，字符数用作值。二叉树是按键自动排序的，字典不是这样。

您可以通过将其二进制表示与 XOR 操作相结合，从单个哈希值计算组合哈希值。使用 C#，您可以执行以下操作：

public override int GetHashCode()
{
    // Combine hashcode of a and b
    return a.GetHashCode() ^ b.GetHashCode();
}

在未排序的列表中查找条目是 O(n) 操作。如果使用二进制搜索，则在排序列表中查找条目是 O(log(n)) 操作。

在字典中的列表中查找单词是 O(1 + n) 操作，与 O(n) 操作相同，或者 O(1 + log(n)) 操作，与O(log(n)) 操作。

编辑：

这是一个可能的实现：

var anagrams = new Dictionary<string, List<string>>();
foreach (string word in words) {
    string key = GetFrequency(word);
    List<string> list;
    if (anagrams.TryGetValue(key, out list)) {
        list.Add(word);
    } else {
        list = new List<string> { word };
        anagrams.Add(key, list);
    }
}

它使用这种方法来获取密钥：

private string GetFrequency(string word)
{
    var dict = new SortedDictionary<char, int>(); // Implemented as binary tree
    foreach (char c in word.ToLower()) {
        int count;
        if (dict.TryGetValue(c, out count)) {
            dict[c] += 1;
        } else {
            dict[c] = 1;
        }
    }
    return dict.Aggregate(new StringBuilder(), (sb, item) => sb.Append(item.Key).Append(item.Value), sb => sb.ToString());
}

使用这个定义来描述......

var words = new List<string> { "need", "eden", "team", "meat", "meta", "Nat", "tan" };

这个测试...

foreach (var item in anagrams.OrderBy(x => x.Key)) {
    Console.WriteLine();
    Console.WriteLine(item.Key + ":");
    foreach (string word in item.Value.OrderBy(w => w)) {
        Console.WriteLine("    " + word);
    }
}

...产生这个输出

a1e1m1t1:
    meat
    meta
    team

a1n1t1:
    Nat
    tan

d1e2n1:
    eden
    need

编辑＃2：

这是 Ben Voigt 建议的频率计算

private string GetFrequencyByBenVoigt(string word)
{
    char[] chars = word.ToLower().ToCharArray();
    Array.Sort(chars);
    return new string(chars);
}

测试结果将是

aemt:
    meat
    meta
    team

ant:
    Nat
    tan

deen:
    eden
    need
于 2012-01-14T23:42:29.853 回答
1

基于容器内容的哈希码将在容器O(n)中的项目计数中。您可以将字典包装成另一种类型并缓存哈希码，因此只需要计算一次......但我可以想到几种比字典更有效的方法来存储该数据。

于 2012-01-14T23:56:54.850 回答