java - 二叉搜索树与 MultiMap

Question

我要解决的问题是我必须在树中输入 IP 地址前缀和与它们关联的数据，以便以后可以查询它们。我正在从一个文件中读取这些地址，该文件可能包含多达 1600 万条记录，并且该文件可能有重复项，我也必须存储这些记录。

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

我希望查询花费 O(logn) 时间。
数据结构需要在Ram中，所以我也不确定我将如何存储1600万个节点。

我想问:使用像 guava 这样的库在多 map 中插入 Ips 会不会对性能造成太大影响？或者有更好的方法吗？

Answer 1

使用经过测试、记录和维护良好的内置库通常是一种很好的做法。
它也将帮助您更多地了解 Guava 。一旦您开始“只为一件事”使用它，您很可能会意识到您可以使用更多东西来让您的生活更轻松。

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

---

关于内存 - 你应该尽量减少你的数据(使用高效的数据结构，不需要“浪费” String ，例如存储IP，有更便宜的选择，利用它们。

另请注意 - 通过使用 virtual memory，操作系统将能够为您提供比您拥有的 RAM 更多的内存。 (实际上对于 64 位机器 - 它很可能已经足够了)。但是，它的效率很可能不如专用于磁盘的 DS(例如 B+ trees)。

---

备选方案:
作为TreeMap的替代品- 您可能对其他数据结构感兴趣(各有优缺点):

• hash table - 实现为 HashMap 在 java 。您的类型将是 HashMap<Key,List<Value>> .它允许 O(1)平均案例查询，但可能会衰减到 O(n)最坏的情况下。它还不允许有效的范围查询。
• trie或其更节省空间的版本 - radix tree .允许O(1)访问每个 key ，但通常空间效率低于替代方案。使用这种方法，您将实现 Map 与 DS 的接口(interface)，您的类型将是 Map<Key,List<Value>>
• B+ tree ，它针对磁盘进行了更优化 - 如果您的数据毕竟太大而无法放入 RAM。