Java中避免二分搜索前重复排序的高效解决方案咨询

我有一个包含name和surname属性的Foo类，用ArrayList存储其实例。实际场景中类结构庞大，且存在频繁的add操作，需要高效执行查询——有时按name字段、有时按surname字段查询，想避免每次搜索前都执行排序操作。

现有临时方案 #

• 方案1：保留现有代码，每次二分搜索前执行排序，承担排序开销
• 方案2：占用额外内存维护两个分别按name、surname排序的ArrayList，同时保留原插入顺序，避免每次搜索前排序

希望得到更高效的解决方案。

示例代码 #

package Memory;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class MemTest2 {
    static ArrayList<Foo> al = new ArrayList<Foo>();
    public static void main(String[] args) {

        add("John","colins");
        add("Andrew","tate");
        add("Zoe","prelevits");
        add("jonh","adam");


        BinarySearchName();
        BinarySearchSurname();
    }

    public static void add(String name,String surname){
        al.add(new Foo(name,surname));
    }

    public static void BinarySearchName(){
        Comparator<Foo> c = new Comparator<Foo>() {
            public int compare(Foo u1, Foo u2)
            {
                return u1.getName().compareTo(u2.getName());
            }
        };
        Collections.sort(al, Comparator.comparing(Foo::getName));
        int index = Collections.binarySearch(al, new Foo("Zoe","prelevits"), c);
    }

    public static void BinarySearchSurname(){
        Comparator<Foo> c = new Comparator<Foo>() {
            public int compare(Foo u1, Foo u2)
            {
                return u1.getSurname().compareTo(u2.getSurname());
            }
        };
        Collections.sort(al, Comparator.comparing(Foo::getSurname));
        int index = Collections.binarySearch(al, new Foo("john","adam"), c);
    }

    private static class Foo{
        private String name;
        private String surname;

        public Foo(String name, String surname) {
            this.name = name;
            this.surname = surname;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public String getSurname() {
            return surname;
        }

        public void setSurname(String surname) {
            this.surname = surname;
        }
    }
}

1. 用TreeSet维护排序集合（需处理重复元素） #

针对每个查询字段，维护一个TreeSet并指定对应比较器。TreeSet本身是有序结构，插入时自动完成排序（时间复杂度O(log n)），查询操作也是O(log n)，远优于每次排序的O(n log n)开销。如果需要保留原插入顺序，可以同时维护一个ArrayList存储原始数据，TreeSet仅存储Foo实例的引用作为索引。

示例代码片段：

// 按name排序的TreeSet
private static TreeSet<Foo> nameSortedSet = new TreeSet<>(Comparator.comparing(Foo::getName));
// 按surname排序的TreeSet
private static TreeSet<Foo> surnameSortedSet = new TreeSet<>(Comparator.comparing(Foo::getSurname));
// 保留插入顺序的原始列表
private static ArrayList<Foo> originalList = new ArrayList<>();

public static void add(String name, String surname) {
    Foo foo = new Foo(name, surname);
    originalList.add(foo);
    nameSortedSet.add(foo);
    surnameSortedSet.add(foo);
}

// 按name查询匹配元素
public static Foo searchByName(String targetName) {
    // 创建仅含目标name的虚拟Foo实例用于匹配
    Foo dummy = new Foo(targetName, null);
    return nameSortedSet.ceiling(dummy); // 可根据需求选择ceiling/floor/contains等方法
}

// 按surname查询匹配元素
public static Foo searchBySurname(String targetSurname) {
    Foo dummy = new Foo(null, targetSurname);
    return surnameSortedSet.ceiling(dummy);
}

注意：如果存在name或surname重复的Foo实例，默认TreeSet会去重。若需保留重复元素，需自定义比较器——先比较目标字段，再比较对象哈希值或唯一标识，确保重复元素能被插入。

2. 维护排序索引（存储元素索引而非实例） #

如果不想维护多个完整的Foo集合，可以维护两个ArrayList，分别存储按name、surname排序后的原列表索引。插入新元素时，通过二分查找确定索引在两个列表中的插入位置并插入（时间复杂度O(n)，因为ArrayList插入中间元素需要移动后续元素），查询时直接用索引列表做二分查找，找到后从原列表取出对应元素。

这种方式比维护两个完整Foo列表更节省内存，因为存储的是整数索引而非对象引用。

示例代码片段：

private static ArrayList<Foo> originalList = new ArrayList<>();
private static ArrayList<Integer> nameIndexList = new ArrayList<>();
private static ArrayList<Integer> surnameIndexList = new ArrayList<>();

public static void add(String name, String surname) {
    Foo foo = new Foo(name, surname);
    originalList.add(foo);
    int newIndex = originalList.size() - 1;

    // 插入到name索引列表的对应位置
    int insertPosName = Collections.binarySearch(nameIndexList, newIndex, (i1, i2) -> 
        originalList.get(i1).getName().compareTo(originalList.get(i2).getName())
    );
    if (insertPosName < 0) insertPosName = -insertPosName - 1;
    nameIndexList.add(insertPosName, newIndex);

    // 插入到surname索引列表的对应位置
    int insertPosSurname = Collections.binarySearch(surnameIndexList, newIndex, (i1, i2) -> 
        originalList.get(i1).getSurname().compareTo(originalList.get(i2).getSurname())
    );
    if (insertPosSurname < 0) insertPosSurname = -insertPosSurname - 1;
    surnameIndexList.add(insertPosSurname, newIndex);
}

// 按name查询
public static Foo searchByName(String targetName) {
    int result = Collections.binarySearch(nameIndexList, -1, (idx, dummy) -> 
        originalList.get(idx).getName().compareTo(targetName)
    );
    if (result >= 0) {
        return originalList.get(nameIndexList.get(result));
    }
    return null;
}

这种方式插入开销略高于TreeSet，但内存占用更低，适合元素数量不是极端庞大的场景。

3. 用第三方库的索引结构 #

比如Guava的TreeMultimap，支持按键排序并存储多个值，适合存在重复键的查询场景。例如通过TreeMultimap.create(Comparator.comparing(Foo::getName), Ordering.natural())创建结构，可快速查询所有匹配目标字段的元素。

内容的提问来源于stack exchange，提问作者Mixalis Navridis