二叉搜索树和MultiMap的区别

Question

3

我需要解决的问题是需要将IP地址前缀及其相关数据存储在一棵树中，以便日后进行查询。我从文件中读取这些地址，文件可能包含多达1600万个记录，并且文件中可能会有重复项，我也需要将它们存储下来。

我编写了自己的二叉搜索树，但了解到Java中的TreeMap使用红黑树实现，但TreeMap不能包含重复项。

我希望查询时间为O(logn)。数据结构需要在内存中，因此我也不确定如何存储1600万个节点。

我想问一下：使用类似guava这样的库将IP插入Multi-map中是否会对性能造成太大影响？还是有更好的方法可以做到这一点？

- micc0

1

查阅Tries相关资料。它们被广泛用于IP路由。这个链接可能会有所帮助：http://www.drdobbs.com/windows/fast-ip-routing-with-lc-tries/184410638 - Vaibhav Desai

既不是TreeMap也不是Guava的Multimap允许使用前缀。无论它们是通过树还是哈希表实现的，它们都不允许像“查找1.2.3.4的最长包含前缀”这样的操作；至少不是直接的（NavigableMap可以在这里提供帮助）。 - maaartinus

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

使用内置的库通常是一个好习惯，因为它已经经过测试、记录和维护。这也将帮助您更多地了解guava。一旦您开始使用它“只是为了一件事”，您很可能会意识到还有更多可以用来使您的生活更加轻松的东西。

此外，作为Multimap的自定义实现，使用TreeMap<Key,List<MyClass>>而不是TreeMap<Key,MyClass>也是一种选择。

关于内存 - 你应该尽可能地减少数据量（使用高效的数据结构，例如对于存储IP地址，无需使用“浪费”的字符串String，有更便宜的替代品，可以利用它们。

还要注意 - 操作系统将能够通过使用虚拟内存为您提供比RAM更多的内存（对于64位机器而言，这很可能已经足够）。但是，它可能不如专门用于磁盘的DS（例如B+树）高效。

替代方案：
作为 TreeMap 的替代方案，您可能会对其他数据结构感兴趣（每种都有其优点和缺点）：

哈希表 - 在Java中实现为HashMap。您的类型将是HashMap<Key,List<Value>>。它允许O(1)的平均情况查询，但最坏情况可能会降至O(n)。它也不允许有效的范围查询。
Trie树或其更节省空间的版本 - 基数树。允许对每个键进行O(1)的访问，但通常比其他替代方案的空间效率低。使用此方法，您将使用DS实现Map接口，您的类型将是Map<Key,List<Value>>
B+树，如果您的数据太大而无法全部放入RAM，则更加优化了磁盘。