Java中不使用Java8、基于自定义规则查找唯一实例的高效方法

最优方案（时间复杂度O(n)，适合数据量较大的场景） #

该方案利用HashSet的O(1)平均查找效率实现快速去重，需要你补充和isIdentical逻辑匹配的哈希计算规则：

1. 首先定义MyItem包装类，重写equals和hashCode方法适配自定义匹配规则

private static class MyItemWrapper {
    private final MyItem item;

    public MyItemWrapper(MyItem item) {
        this.item = item;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        MyItemWrapper that = (MyItemWrapper) o;
        return isIdentical(this.item, that.item);
    }

    @Override
    public int hashCode() {
        // 必须保证：当isIdentical(a,b)返回true时，a和b对应的MyItemWrapper的hashCode相等
        // 示例：若匹配规则为id和name相等，则按以下方式计算：
        // int hash = item.getId();
        // hash = 31 * hash + (item.getName() == null ? 0 : item.getName().hashCode());
        // return hash;
        // 未实现匹配的hashCode前不要使用该方案，会导致去重错误
    }

    public MyItem getItem() {
        return item;
    }
}

2. 实现去重方法

List<MyItem> findUniqueItems(List<MyItem> allItems) {
    Set<MyItemWrapper> uniqueWrapperSet = new HashSet<MyItemWrapper>();
    List<MyItem> uniqueItems = new ArrayList<MyItem>();

    for (MyItem item : allItems) {
        MyItemWrapper wrapper = new MyItemWrapper(item);
        if (!uniqueWrapperSet.contains(wrapper)) {
            uniqueWrapperSet.add(wrapper);
            uniqueItems.add(item);
        }
    }
    return uniqueItems;
}

兼容方案（时间复杂度O(n²)，适合数据量较小的场景） #

如果无法实现和isIdentical匹配的hashCode逻辑，可以用双重迭代的方式实现，无需修改其他额外代码：

List<MyItem> findUniqueItems(List<MyItem> allItems) {
    List<MyItem> uniqueItems = new ArrayList<MyItem>();

    for (MyItem currentItem : allItems) {
        boolean existed = false;
        for (MyItem uniqueItem : uniqueItems) {
            if (isIdentical(currentItem, uniqueItem)) {
                existed = true;
                break;
            }
        }
        if (!existed) {
            uniqueItems.add(currentItem);
        }
    }
    return uniqueItems;
}

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