Не могу понять преимущество переопределенной реализации метода equals в ConcurrentHashMap

Большинство классов карт в Java переопределяют AbstractMap и используют его реализацию метода equals который проверяет:

  1. переданный объект имеет тип Map
  2. имеет такую же длину
  3. содержит все записи, присутствующие в this

    if (o == this)
        return true;
    
    //check that passed object is of type Map
    if (!(o instanceof Map))
        return false;
    Map<?,?> m = (Map<?,?>) o;
    
    //check that passed object has same length
    if (m.size() != size())
        return false;
    
    //passed object contains all the entries
    try {
        Iterator<Entry<K,V>> i = entrySet().iterator();
        while (i.hasNext()) {
            Entry<K,V> e = i.next();
            K key = e.getKey();
            V value = e.getValue();
            if (value == null) {
                if (!(m.get(key)==null && m.containsKey(key)))
                    return false;
            } else {
                if (!value.equals(m.get(key)))
                    return false;
            }
        }
    } catch (ClassCastException unused) {
        return false;
    } catch (NullPointerException unused) {
        return false;
    }
    
    return true;
    

Но ConcurrentHashMap использует другую реализацию, где вместо сопоставления длины обеих карт элементы, присутствующие в переданной карте, также повторяются и сопоставляются.

    if (o != this) {

        //check that passed object is of type Map
        if (!(o instanceof Map))
            return false;
        Map<?,?> m = (Map<?,?>) o;
        Node<K,V>[] t;
        int f = (t = table) == null ? 0 : t.length;
        Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);

        //passed object contains all the entries
        for (Node<K,V> p; (p = it.advance()) != null; ) {
            V val = p.val;
            Object v = m.get(p.key);
            if (v == null || (v != val && !v.equals(val)))
                return false;
        }

        //this contains all the entries of the passed object
        for (Map.Entry<?,?> e : m.entrySet()) {
            Object mk, mv, v;
            if ((mk = e.getKey()) == null ||
                (mv = e.getValue()) == null ||
                (v = get(mk)) == null ||
                (mv != v && !mv.equals(v)))
                return false;
        }
    }
    return true;

Так как метод equals не является потокобезопасным даже в ConcurrentHashMap кто-то может предложить, в чем преимущество пропуски проверки длины и вместо этого итерации и сопоставления записей с переданного объекта?

Как указано в ответах ниже, этот размер недоступен в качестве прямого поля, это equals реализация, которая, по моему мнению, более эффективна. Просьба уточнить проблемы в этом вопросе. В основном мы не занимаемся поиском в последнем цикле.

    if (o != this) {

        //check that passed object is of type Map
        if (!(o instanceof Map))
            return false;
        Map<?,?> m = (Map<?,?>) o;
        Node<K,V>[] t;
        int f = (t = table) == null ? 0 : t.length;
        Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
        int thisSize=0;

        //passed object contains all the entries
        for (Node<K,V> p; (p = it.advance()) != null; ) {
            V val = p.val;
            Object v = m.get(p.key);
            if (v == null || (v != val && !v.equals(val)))
                return false;
            thisSize++;
        }

        //passed object is of the same size, ignoring any modifications since invocation of equals
        int passedObjectSize=0;
        for (Map.Entry<?,?> e : m.entrySet()) {
            Object mk, mv, v;
            if ((mk = e.getKey()) == null ||
                (mv = e.getValue()) == null){
                return false;
            }
            //ignore checking that get(mk) is same as mv
            passedObjectSize++;
        }
        return thisSize==passedObjectSize;
    }
    return true;

Ответы

Ответ 1

Я думаю, что проверка размера была бы бесполезной, при вычислении размера Traverser вообще не используется, он использует специализацию LongAdder (называемый CounterCell), поэтому требуется время для вычисления размера и к тому времени, когда это будет сделано - CHM может полностью измениться до пересечения.

Даже вычисление size не гарантирует, что оно будет правильным, например, CHM может быть изменен при вычислении размера - так что число будет неточным.

Поэтому я предполагаю, что это можно рассматривать как оптимизацию: зачем вычислять размер, если в большинстве случаев это бесполезно.

Ответ 2

Реализация ConcurrentHashMap.size() сильно отличается от большинства других Map.

HashMap и TreeMap реализуют его, просто возвращая значение частного size поля, которое они поддерживают в любом случае.

ConcurrentHashMap не поддерживает такое поле. Это было бы трудно реализовать неблокируемым способом, при этом позволяя одновременным модификациям отдельных ведер вмешиваться как можно меньше друг в друга.

Версия Java 8, на которую я смотрю, имеет следующую реализацию

/**
 * {@inheritDoc}
 */
public int size() {
    long n = sumCount();
    return ((n < 0L) ? 0 :
            (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
            (int)n);
}

где sumCount() выполняет counterCells массива counterCells.

Это намного менее привлекательно, чем просто проверка, чем простой доступ к полям.