.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++ 转向时（我会定期使用自己的堆并编写内存本地化例程等），我就痴迷于这样做，但很快就发现我不需要这样做，也不需要 < em>可以 I.

例如，您可以在 trie 的底部有一个 MyPooledObject 数组，但是，如果这是一个引用类型，那么您只有一个数组参考文献，其中每个的实际内存位于其他地方 - 您无法控制（除非您为运行时调整自己的主机）。

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

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

如果您有太多对象无法容纳在内存中，则可以：

1) 获取更多内存

2) 使用数据库并缓存其本地段

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