3

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

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

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

我想问：使用像番石榴这样的库在多地图中插入 Ips 会不会对性能造成太大影响？还是有更好的方法来做到这一点？

4

1 回答 1

3

使用经过测试记录和维护良好的内置库通常是一种好习惯。
它还将帮助您了解有关番石榴的更多信息。一旦你开始“只为一件事”使用它，你很可能会意识到还有很多东西可以让你的生活变得更轻松。

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

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

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

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

  • 哈希表-HashMap在 java 中实现。您的类型将是HashMap<Key,List<Value>>. 它允许O(1)平均情况查询，但可能衰减到O(n)最坏情况。它也不允许有效的范围查询。
  • trie或其更节省空间的版本 -基数树。允许O(1)访问每个密钥，但通常空间效率低于其他选项。使用这种方法，您将实现Map与 DS 的接口，您的类型将是Map<Key,List<Value>>
  • B+ 树，它更适合磁盘 - 如果您的数据太大而无法放入 RAM。
于 2012-12-11T19:26:29.210 回答