1

我需要存储大量独特的路径，例如："C:\MyDir\MySubDir\myfile.txt".

我希望能够快速检查我的集合中是否包含路径，以及以上，以尽可能少地使用内存。

什么是最适合这项任务的集合？

是否可以存储一个代表唯一路径的值，而不是字符串本身，以使用更少的内存？

4

6 回答 6

3

看看Trie我们用 2000 万条路径做得非常有效

于 2012-05-29T16:07:21.007 回答
2

一个哈希集，如果您需要快速访问数据，即如果您想在 O(1) 时间内知道集合中是否存在某些东西。

在 .NET 4 中，使用HashSet. 它就像一个哈希表，但只存储值，而不是键/值对。

HashSet<string> myStrings = new HashSet<string>();
myStrings.Add(@"c:\foo\bar.txt");
myStrings.Add(@"c:\foo\baz.gif");
myStrings.Add(@"c:\foo\bat.bin");
于 2012-05-29T16:05:35.770 回答
2

这最适合TRIE。这是一个示例：在 c# 中实现一个 trie。

要回答您的问题，是的，TRIE 存储唯一路径而不是字符串本身。

尝试对您的任务非常有效，无论是内存消耗还是执行速度。

编辑： 并不是说一个比另一个好，TRIE 是为这种类型的存储/检索问题而发明的，并且非常有效。 散列也很快。如果您想知道哪一个最适合您的需求，请同时实施。无论哪种方式，都不应该花很长时间。 测量，测量，测量。

于 2012-05-29T16:08:44.280 回答
2

正如其他人所回答的那样，aTrie并且HashSet会提供快速的获取时间。
请注意，虽然 aTrie需要的内存少于 a HashSet，但两者都需要比普通的旧内存更多的内存List（请参阅this）。

我不知道这是否真的有必要，但如果内存是一个真正的问题，您可以优化Trie实现，使用文件夹名称作为节点而不是字母（因为通常文件夹名称长于一个字母）。这样，您将使用路径的树结构。

于 2012-05-29T16:28:25.480 回答
0

通常用于存储唯一数据点的数据结构是集合。您可以为此使用 .NETHashSet<T>类。使用 HashSet，您不必在添加值之前检查值是否存在，并且您也可以快速查找。

于 2012-05-29T16:09:13.500 回答
0

您为什么不使用 Dictionary/HashTable 来实现快速查找集合的目的。

“可以存储一个表示唯一路径的值..” - 想想这个，每次你必须检查集合中是否存在某个值时，你必须加密/解密你的字符串。不好的做法

编辑： 如果速度不是问题，为什么不将所有键存储在数据库中，然后您可以在表中快速循环以查看路径是否存在？

于 2012-05-29T16:08:29.273 回答