.net - .net 的高效 trie 实现

Question

我正在寻找.net 的 trie 实现。

我打算将它用作我的内存对象池的索引结构。它不需要是线程安全的（因为只有一个线程会更新它），但应该能够优雅地处理至少 2000 万个项目并保持稳定的性能。

我在网上找到的似乎是示例代码或玩具项目。所以，我真的在寻找生产质量的实施。商业图书馆也可以，如果有的话。

PS：我选择了尝试，因为我看到的哈希表实现似乎使用了太多内存，并且由于它们基于数组而容易导致内存碎片。任何具有 O(1) 查找特性和大量项目的良性内存使用特性的容器也可以。

谢谢，

Answer 1

看看这个库：TrieNet

using Gma.DataStructures.StringSearch;

...

var trie = new SuffixTrie<int>(3);

trie.Add("hello", 1);
trie.Add("world", 2);
trie.Add("hell", 3);

var result = trie.Retrieve("hel");

Answer 2

在我个人看来，我不推荐尝试对 .Net 自己的内存管理进行事后猜测。您根本无法像在本机场景中那样对内存分配进行控制，但同样您也不需要这样做。当我第一次从 C++（我会定期使用自己的堆并编写内存本地化例程等）迁移到 C++ 时，我一直渴望这样做，但很快就发现我不需要，也不能一世。

例如，你可以MyPooledObject在你的 trie 的底部有一个数组，但是，如果那是一个引用类型，那么你就得到了一个引用数组，每个引用的实际内存都在其他地方——你可以' t 控制（除非您为运行时调整自己的主机）。

剩下的就是使用值类型——但这些根本不适合在池化场景中使用，因为自定义值类型应该是不可变的（我可以安全地说，无需证明它是正确的——只需谷歌“不可变”和“结构”定位站点:stackoverflow.com 查看更多），因此被视为可重用对象没有好处。

如果您需要 .Net 中的对象的索引集合，其中每个对象都可以使用具有散列功能的键识别，那么请使用字典。

如果您有太多对象无法放入内存，那么：

1）获取更多内存

2）使用数据库并缓存它的本地段

或者两者兼而有之：您可以考虑查看AppFabric 及其缓存功能，这样您就可以构建一个机器群，专门用于运行数百万个对象的内存缓存。硬件成本可能低于为 .Net 开发自己的内存管理解决方案的成本:)