我必须解决的问题是，我必须在树中输入IP地址前缀和与它们相关的数据，以便以后可以查询它们。我正在从一个文件中读取这些地址，该文件可能包含多达1600万条记录，并且该文件可能有重复项，我也必须存储这些记录。
我编写了自己的二进制搜索树，但了解到Java中的TreeMap是使用红黑树实现的，但TreeMap不能包含重复项。
我希望查询需要O(logn)时间。
数据结构需要在Ram中，所以我也不确定如何存储1600万个节点。
我想问：使用像番石榴这样的库在多映射中插入Ips会不会对性能造成太大影响？或者有更好的方法吗？
使用一个经过测试、记录和良好维护的内置库通常是的好做法。
它还将帮助你了解更多关于番石榴的知识。一旦你开始"只为一件事"使用它，你很可能会意识到还有更多的东西可以让你的生活变得更轻松。
此外，一种替代方案是使用TreeMap<Key,List<MyClass>>而不是TreeMap<Key,MyClass>作为Multimap的自定义实现。
关于内存-您应该尽量减少数据(使用高效的数据结构，不需要"浪费"的String，例如存储IP，有更便宜的替代方案，利用它们。
还要注意的是，操作系统将能够通过使用虚拟内存为您提供比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