使用哈希表在字符串中查找字符

Question

我决定解决在字符串中查找给定字符的问题，并且我用了两种方法解决：

第一种方法（使用哈希表来保持我们想要查找的字符的ASCII值）：

static void Hash(string text, char[] charsToFind)
{
    Dictionary<int,char> chars = new Dictionary<int,char>();
    foreach (var letter in charsToFind)
    {
        chars[(int)letter] = letter;
    }

    foreach (var letter in text)
    {
        if (chars.ContainsKey((int)letter))
        {
            if (letter == chars[(int)letter])
            {
                Console.WriteLine("Element found at: {0}, value: {1}", (int)letter, letter);
            }
        }
    }
}

第二种方法（朴素的）是：

static void Naive(string text, char[] charsToFind)
{
    foreach (var letter in text)
    {
        foreach (var character in charsToFind)
        {
            if ((int)letter == (int)character)
            {
                Console.WriteLine("Element found at: {0}, value: {1}", (int)letter, letter);
            }
        }
    }
}

一切都运行良好！我想问的问题是哪种方法更好，是否有更好的解决方案？

提前感谢！

- Tsvetan

---

是否存在“仅限.NET 2.0”的限制，还是可以自由使用3.5或4.0？ - abatishchev

你可以使用任何版本的.NET。 - Tsvetan

你的第一个方法是错误的。它应该是一个Dict<char,int>，并且你应该使用for(int i = text.Length - 1; i > -1; i--) chars[text[i]] = text[i];来填充它。 - Alxandr

Answer 1

使用LINQ：

string input = "abc";
char[] charsToFind = new[] { 'a', '1', 'b' };
IEnumerable<int> ids = charsToFind.Select(ch => input.IndexOf(ch)); // { 0, -1, 1 }

---

使用泛型哈希表Hashset<T>：

HashSet<char> set = new HashSet<char>(input.ToCharArray());
...

- abatishchev

---

谢谢！但是我的哈希表算法更有效率和更好吗？ - Tsvetan

+1. @Tsvetan，你可以尝试使用样本输入并检查执行时间。 - Sandeep G B

我知道，但我想问的是哪一个在编程实践方面更好。 - Tsvetan

Answer 2

第一个方法更好，但对于少量字符而言，第二个可能会更快。

对于第一个方法的一些评论。 在第一个方法中，使用字典涉及计算哈希和执行查找的成本。如果你知道字符是ASCII码，则可以使用数组来加速查找。

可以使用“TryGetValue”而不是“ContainsKey”来进行一次查找。

- Nick Randell

---

我知道这些字符是ASCII码，但我读到使用哈希表是更好的方法。所以，我决定在这里问一下... - Tsvetan

是的，但哈希表速度较慢，因为它需要做更多的工作。 - Nick Randell

我发现有趣的事情是，朴素算法是最快的(~0010000ms)。然后是哈希，之后是LINQ。这些测试是在30,7KB的文本上进行的。我也会尝试你的方法，看看会发生什么... - Tsvetan