如何在我的Entry类中调用binarySearch()？

Question

我正在制作一个图书索引，其中我有一个名为 Entry 的内部类，它包含一个 String（单词本身）和一个 Integer TreeSet，用于保存单词出现的所有行号。

我有一个ListIndex类（存放Entry类），在这个类中我创建了一个类型为Entry的ArrayList。当我向列表中添加一个单词时，我需要通过使用binarySearch()来检查该单词是否已经在列表中。然而，我不能使用 Collections.binarySearch(myList, word)，因为 ArrayList 是 Entry 类型的。

我的 Entry 类实现了 Comparable，但我仍然不明白如何解决这个问题。任何帮助都将被感激!

Answer 1

你应该实现 Comparable 衔接 Entry 这样

static class Entry implements Comparable {

        String text;
        TreeSet<Integer> set;

        public Entry(String text, TreeSet<Integer> set) {
            this.text = text;
            this.set = set;
        }

        @Override
        public String toString() {
            return text;
        }

        @Override
        public int compareTo(Object obj) {
            if (obj instanceof String)
                return text.compareTo((String) obj);
            else {
                Entry otherEntry = (Entry) obj;
                return text.compareTo(otherEntry.text);
            }
        }
    }

    public static void main(String[] args) {
        List<Entry> entries = new ArrayList<>();
        entries.add(new Entry("bbbb", new TreeSet<>()));
        entries.add(new Entry("aaaa", new TreeSet<>()));
        entries.add(new Entry("cccc", new TreeSet<>()));
        entries.add(new Entry("hhhh", new TreeSet<>()));
        entries.add(new Entry("dddd", new TreeSet<>()));

        Collections.sort(entries);
        int index = Collections.binarySearch(entries, "cccc", (e1, e2) -> e1.compareTo(e2));
        System.out.println(index);
    }

产量

2

Answer 2

用假的 Entry 标的

假设你的实施在 Entry 对于 compareTo 的方法。Comparable 接口只是服从于它所包含的 String 对象的 compareTo 方法，并忽略 TreeSet 的行数...

只要实例化一个假的 Entry 对象与您的目标字符串。使用该 Entry 专用 Collections.binarySearch，然后丢弃。

Entry target = new Entry( "Widget" , new TreeSet<Integer>() ) ;
int index = Collections.binarySearch( myList , target ) ;  // Assuming the `compareTo` method compares only the `String` member field while ignoring the `TreeSet` member field.
if( entry < 0 ) { … no entry yet exists … }
else  // Else, entry found to exist.
{ 
    Entry entry = myList.get( index ) ;
    …
}
…
// As `target` goes out of scope, the object becomes a candidate for garbage collection, to be deleted from memory eventually.

要发送 target 对象的垃圾回收速度更快，重新分配了 target = null ; 二进制搜索后。

使用 Map 而不是 Entry 阶层

如果您的 Entry 课堂不过是 String 和a TreeSet那么我建议你完全跳过这个类的定义。使用 Map 而不是。关键是一个 String 的索引条目字，其值是一个 TreeSet.

Map< String , TreeSet< Integer > > entries = new TreeMap<>() ;

要搜索一个条目，使用 Map::containsKey 并传递索引条目字。

多图行为

然后你可以使用Java 8 computeIfAbsent 便捷法 多图 行为，方便访问行号集。展示在 本回答.

或者使用第三方的多图实现。例如 谷歌番石榴 图书馆