二叉搜索树与MultiMap
二叉搜索树与MultiMap
提问于 2012-12-12 03:22:00
我必须解决的问题是，我必须在树中输入IP地址前缀和与其关联的数据，以便稍后可以查询它们。我正在从一个文件中读取这些地址，该文件可能包含多达1600万条记录，并且该文件可能有重复的记录，我也必须存储这些记录。
我编写了自己的二进制搜索树，但了解到在Java语言中TreeMap是使用红黑树实现的，但是TreeMap不能包含重复项。
我希望查询占用O(logn)时间。
数据结构需要在Ram中，所以我也不确定如何存储1600万个节点。
我想问:使用像guava这样的库在Multi-map中插入Ips会不会对性能造成太大的影响？或者有更好的方法来做这件事？
Stack Overflow用户
回答已采纳
发布于 2012-12-12 03:26:29
使用内置库通常是一个很好的实践，该库经过测试、记录和良好的维护。
它还将帮助您了解更多关于芭乐的知识。一旦你开始使用它“只为了一件事”，你很可能会意识到还有更多的东西可以让你的生活变得更容易。
此外，另一种方法是使用TreeMap<Key,List<MyClass>>而不是TreeMap<Key,MyClass>作为Multimap的自定义实现。
关于内存-你应该尽量减少你的数据(使用高效的数据结构，不需要“浪费”的String，例如用于存储IP，有更便宜的替代方案，利用它们。
还要注意-通过使用virtual memory，操作系统将能够提供比你拥有的内存更多的内存(实际上对于64位机器-它很可能超过足够的内存)。但是，它的效率很可能低于专用于磁盘的DS (例如B+ trees )。
替代方案：
作为TreeMap的替代方案-您可能会对其他数据结构感兴趣(每种结构都有其优缺点)：
- hash table -在java中实现为
HashMap。然后，您的类型将是HashMap<Key,List<Value>>。它允许O(1)平均情况查询，但可能会衰减到O(n)最坏情况。它也不允许高效的范围queries. - trie或其更节省空间的版本- radix tree。允许
O(1)访问每个密钥，但通常比其他方法的空间效率低。使用这种方法，您将使用DS实现Map接口，并且您的类型将是针对磁盘进行了更多优化的Map<Key,List<Value>> - B+ tree，--如果您的数据太大而无法放入
Map的话。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/13826998
复制相关文章
相似问题
腾讯云开发者
