java - 提高非重复并发 ArrayList 的性能

Question

我在实现 的数据结构时遇到了性能问题非重复 并发 ArrayList(或 ConcurrentLinkedQueue )。

public class NonDuplicateList implements Outputable {
    private Map<Term, Integer> map;
    private List<Term> terms;

    public NonDuplicateList() {
        this.map = new HashMap<>();
        this.terms = new ArrayList<>();
    }

    public synchronized int addTerm(Term term) { //bad performance :(
        Integer index = map.get(term);
        if (index == null) {
            index = terms.size();
            terms.add(term);
            map.put(term, index);
        }
        return index;
    }

    @Override
    public void output(DataOutputStream out) throws IOException {
        out.writeInt(terms.size());
        for (Term term : terms) {
            term.output(out);
        }
    }
}

请注意 Term和 NonDuplicateList都实现 Outputable接口(interface)输出。

为了保持 NonDuplicateList线程安全，我使用 synchronized守护方法 addTerm(Term)当前调用 addTerm 时，性能与预期一样差.

看来 ConcurrentHashMap不适合这种情况，因为它不能保持强大的数据一致性。知道如何提高 addTerm 的性能不失去其线程安全性？

编辑:
output方法，即迭代 NonDuplicateList , 可能不是线程安全的，因为在并发调用 addTerm 后只有一个线程会访问此方法, 但是 addTerm将术语添加到 NonDuplicateList 后必须立即返回索引值.

Answer 1

有可能重复使用ConcurrentHashMap如果您可以牺牲 addTerm 在您的实现中返回类型。您可以返回 boolean 而不是返回实际索引这表明添加是否成功或产生重复。这也将允许您删除方法同步并提高性能:

private ConcurrentMap<Term, Boolean> map;
private List<Term> terms;

public boolean addTerm(Term term) {
    Boolean previousValue = map.putIfAbsent(term, Boolean.TRUE);
    if (previousValue == null) {
        terms.add(term);
        return true;
    }
    return false;
}