面试题：Java TreeMap自定义排序规则下的性能优化

1. 排序算法选择

避免复杂比较逻辑在每次比较时重复计算：对于复杂的自定义排序规则，如果其中涉及到复杂计算（如从外部配置文件获取规则后与对象多个属性综合运算），可以考虑在对象构建时就预先计算出一个“排序值”，将复杂的多步计算简化为一次简单的数值比较。这样在TreeMap排序时，直接比较这个预计算的值，大大减少比较的时间复杂度。例如：

class MyObject {
    private int prop1;
    private String prop2;
    // 预计算的排序值
    private double preCalculatedSortValue;

    public MyObject(int prop1, String prop2) {
        this.prop1 = prop1;
        this.prop2 = prop2;
        // 假设这里从外部配置文件获取一个系数k，根据prop1和prop2计算排序值
        double k = getCoefficientFromConfig();
        this.preCalculatedSortValue = prop1 * k + prop2.length();
    }

    public double getPreCalculatedSortValue() {
        return preCalculatedSortValue;
    }
}

采用稳定排序算法：TreeMap内部基于红黑树实现，红黑树的插入和查找平均时间复杂度为O(log n)。但是在构建TreeMap时，若能先对数据进行排序，可减少树的旋转次数，提高构建效率。选择稳定排序算法，如归并排序，其时间复杂度为O(n log n)，能保证相同排序值的元素在排序后相对顺序不变，有助于保持数据原有逻辑顺序，同时减少红黑树调整开销。

2. 数据结构调整

减少数据冗余：确保存储在TreeMap中的对象只包含必要的属性。对于不参与排序和业务逻辑的属性，可以考虑将其移除，以减少内存占用，提高缓存命中率。例如，如果对象中有一些临时计算结果或日志记录属性，在不影响功能的情况下可剔除。
批量插入：TreeMap每次插入操作都会调整红黑树结构。如果有大量数据需要插入，可以先将数据存储在一个List中，然后对List进行排序（使用上述稳定排序算法），最后通过putAll方法批量插入到TreeMap中。这样相比逐个插入，可显著减少红黑树调整次数，提高插入性能。

List<MyObject> objectList = new ArrayList<>();
// 填充objectList
Collections.sort(objectList, Comparator.comparingDouble(MyObject::getPreCalculatedSortValue));
TreeMap<MyObject, SomeValue> treeMap = new TreeMap<>(Comparator.comparingDouble(MyObject::getPreCalculatedSortValue));
treeMap.putAll(objectList.stream().collect(Collectors.toMap(o -> o, o -> new SomeValue())));

3. 内存使用优化

对象池技术：如果TreeMap中存储的对象创建开销较大，可以使用对象池技术。预先创建一定数量的对象并放入对象池中，需要时从池中获取，使用完毕后归还，避免频繁创建和销毁对象带来的内存碎片和性能开销。例如：

import java.util.ArrayList;
import java.util.List;

class MyObjectPool {
    private List<MyObject> pool;
    private int initialSize;

    public MyObjectPool(int initialSize) {
        this.initialSize = initialSize;
        pool = new ArrayList<>();
        for (int i = 0; i < initialSize; i++) {
            pool.add(new MyObject());
        }
    }

    public MyObject getObject() {
        if (pool.isEmpty()) {
            return new MyObject();
        }
        return pool.remove(pool.size() - 1);
    }

    public void returnObject(MyObject obj) {
        pool.add(obj);
    }
}

弱引用和软引用：如果TreeMap中的值对象在内存紧张时可以被回收，可以使用WeakHashMap或SoftHashMap（需自行实现类似功能）来替代TreeMap的值部分。WeakHashMap中的值对象若没有其他强引用指向它，在垃圾回收时会被回收；SoftHashMap会在内存不足时回收值对象，有助于避免内存溢出。

4. 缓存与预取

缓存外部配置文件数据：由于排序规则依赖外部配置文件，每次比较都读取配置文件会带来I/O开销。可以在程序启动时将配置文件内容读取到内存中，并缓存起来，在排序比较时直接从内存中获取配置信息，减少I/O操作。例如，使用Properties类读取配置文件并缓存：

import java.io.IOException;
import java.io.InputStream;
import java.util.Properties;

public class ConfigCache {
    private static Properties properties;

    static {
        properties = new Properties();
        try (InputStream inputStream = ConfigCache.class.getClassLoader().getResourceAsStream("config.properties")) {
            properties.load(inputStream);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static String getConfigValue(String key) {
        return properties.getProperty(key);
    }
}

预取相关数据：如果排序规则涉及到其他关联数据（如数据库中的其他表数据），可以在构建TreeMap前进行预取，将相关数据加载到内存中，减少在排序比较时的数据库查询次数，提高排序性能。

星途面试题库

面试题：Java TreeMap自定义排序规则下的性能优化

知识考点

面试题答案

1. 排序算法选择

2. 数据结构调整

3. 内存使用优化

4. 缓存与预取