首页 文章

使用二进制搜索从TreeSet返回元素

提问于
浏览 次
8

在TreeSet中有一个名为contains的方法，如果元素在集合中，则返回true . 我假设此方法使用二进制搜索，并不按升序迭代所有元素 . 我对吗？

我有一个TreeSet，它包含一个类的对象，该类使用两个String实例变量来区分它与同一个类的其他对象 . 我希望能够通过比较两个实例变量（当然使用get方法）和另外两个String变量来创建一个搜索TreeSet的方法，如果它们相等，则返回该元素 . 如果实例变量小于转到右子树中的第一个元素，或者如果它们在左子树中搜索更大等等，有没有办法做到这一点？

我知道我可以将对象存储在ArrayList中并使用二进制搜索来查找对象，但这不会像搜索TreeSet那么快 .

java arraylist binary-search treeset

5 回答

  • 6

    您可以将对象存储在 TreeMap<Foo, Foo> 或 TreeMap<FooKey, Foo> 中（如果每次要搜索时都无法轻松创建新的实际 Foo ），而不是使用 TreeSet . Set s并不是真正用于查找的 .

    对于 FooKey 示例， FooKey 将是一个简单的不可变类，它只包含两个 String 并且是 Comparable . 找到两个 String 的 Foo 的值将是 treeMap.get(new FooKey(firstString, secondString)) 的简单问题 . 这当然使用您想要查找值的树遍历 .

    回复于
  • 2
    set.tailSet(obj).first();

    做你想要的 .

    回复于
  • 14

    您应该在对象上实现Comparable，或者在构造TreeSet时创建一个单独的Comparator类 . 这允许您插入自定义条目比较逻辑，并让TreeSet执行其优化的存储/搜索事物 .

    回复于
  • 1

    我想知道的一件事是你为什么要搜索一个有序的集合？如果您希望能够按顺序迭代以及快速查找，则可以将对象存储在两个单独的数据结构中 . 一个像你的 SortedSet<Foo> ，然后也是一个类似于ColinD提到的 HashMap<FooKey,Foo> . 然后在TreeMap上获得常量时间查找而不是log（n） . 您必须写入两个结构的写入惩罚，以及具有两个数据结构的内存资源损失，但您已完全优化了对数据的访问 .

    此外，如果内存资源受到约束，并且您的字符串实际上是对象的区别，那么您可以在对象 Foo 上实现 hashcode() 和 equals() 然后只将它们用作键和值（如 HashMap<Foo,Foo> . 警告那就是你必须构造一个 Foo 来调用getter .

    回复于
  • 0

    你得到了关于使用可比较/比较器的答案，但我想我会补充说你是对的，contains（）进行二进制搜索，尽管你不需要知道这些细节

    回复于

相关问题