Последнее изменение: 17 сентября 2010г.

Сравнение объектов: теория

– Это наша мама!
– Нет, это!
– А по-моему они одинаковые!

Цыплята из мультфильма

Думаю, нет смысла задаваться вопросом – а зачем нужно сравнение вообще и в программировании в частности? Ответа на этот вопрос нет. Так сложилось, что мы постоянно что-то сравниваем. Собственно, идентификация любого объекта есть его сравнение с эталоном. Другой вид сравнения – сравнение объектов между собой. Например, для упорядочивания по определенным критериям. В этой статье мы рассмотрим сравнения обоих типов, где какое сравнение применяется, их тонкости и подводные камни. А именно – речь пойдет о следующих темах:

Вступление закончилось, перейдем к делу.

Сравнение примитивов

Сравнение примитивных типов вопросов не вызывает. Будь то целочисленные (byte, char, short, int, long) или вещественные (float, double) типы – сравнивать мы их умеем еще со школьной скамьи. С типом boolean дело обстоит иначе. Переменные этого типа можно проверить на равенство. Но кто из них больше – эта операция не определена. С объектными же их оболочками ситуация следующая: в версиях до 5.0 они не были сравнимы (comparable, см. ниже). В версии 5.0 java.lang.Boolean реализует интерфейс java.lang.Comparable, причем таким образом, что false<true.

Есть, однако, нюанс, связаный со сравнением вещественных чисел. Ввиду ограниченной точности представления (и не только) возможны различные неожиданые эффекты. Об этом – во второй части: Сравнение объектов: практика -> Сравнение вещественных примитивов.

Следующая тема –

'==' против 'equals(Object)'

Пусть у нас есть две переменные. Скажем, типа int. Сравнение с помощью оператора '==' есть сравнение значений этих переменных, т.е., фактически, сравнение содержимого соответствующих переменным областей памяти.

Пусть теперь у нас переменные не примитивного типа, а объектного. Что это означает? Означает это, что в соответствующих этим переменным областях памяти хранятся ссылки на объекты. Вопрос: что означает сравнение этих переменных с помощью все того же оператора '=='?

А означает это ровно то же. Сравнение содержимого соответствующих областей памяти. Т.е. эта операция вернет true тогда и только тогда, когда содержимое совпадает, что означает, что переменные указывают на ОДИН И ТОТ ЖЕ объект.

Собственно говоря, это правильно. Сравнение объектов – операция скорее логическая, ибо объект – это сложное образование, которое не всегда можно разобрать и сравнить "в лоб". А потому – операция сравнения содержимого отделена от операции сравнения ссылок. И если вторую можно реализовать на уровне виртуальной машины, то первая должна быть реализована непосредственно разработчиком, т.к. только он может сформулировать правила сравнения. И делается это с помощью переопределения метода equals(Object) класса java.lang.Object.

Реализация этого метода должна подчиняться нескольким правилам:

  • Для любого x!=null вызов x.equals(x) должен вернуть true. Что, в общем-то, логично, ибо объект всегда равен самому себе. Это правило рефлексивности.
  • Для любых x!=null и y!=null вызов x.equals(y) должен вернуть true тогда и только тогда, когда вызов y.equals(x) возвращает true. Иначе говоря, если А==В, то В==А. Опять-таки совершенно логично. Это правило симметрии.
  • Для любых x, y и z, не равных null, таких, что x.equals(y)==true и y.equals(z)==true, выполняется также и x.equals(z)==true. Иначе говоря, если А==В и В==С, то А==С. Это правило транзитивности.
  • Для любых x и y, не равных null, многократные вызовы x.equals(y) согласованно возвращают true либо false, в случае если объекты не были измнены между вызовами. Это правило непротиворечивости.
  • Для любого x!=null вызов x.equals(null) должен вернуть false.

Строго говоря, последнее правило противоречит правилу симметрии. Если взять x!=null и y==null, то, согласно этому правилу, вызов x.equals(y) вернет false, тогда как вызов y.equals(x) (симметричный) приведет к исключению NullPointerException, а, следовательно, о симметричном результате речи не идет. Однако, многие классы из базовой библиотеки полагаются именно на описаное выше поведение, потому это правило учитывать необходимо.

В остальном – реализация оставлена на усмотрение разработчика. Единственный момент – есть нюансы, связаные со сравнением родительских и дочерних объектов. Эти нюансы будут рассмотрены ниже.

Движемся дальше.

Коллекции java.util.Map и метод hashCode

Пожалуй, чаще всего со сравнением объектов приходится сталкиваться при использовании коллекций. В особенности, если коллекция подразумевает уникальность элементов. К примеру, в java.util.Map каждому ключу сопоставлено значение, а, следовательно, ключи должны быть уникальны. Для поиска объекта по ключу их необходимо сравнивать. Вопрос: как это сделать эффективнее всего?

Простой перебор всех ключей – занятие весьма и весьма дорогостоящее. Между тем, процесс поиска объекта можно ускорить, и довольно хорошо. Представьте себе, что каждому объекту сопоставлено некоторое число. Неважно, какое именно, важно, что оно одинаковое для равных объектов. Организуем множество объектов в виде набора подмножеств. Пусть их для примера будет 10. Тогда в первое подмножество попадут элементы, у которых остаток от деления сопоставленного им числа на 10 равен 0, во второе – с остатком 1, в третье – с остатком 2 и т.д. Таким образом, для поиска объекта нужно будет определить остаток от деления и перебрать элементы подмножества, которых, в среднем, в 10 раз меньше.

Число, про которое я говорю, называется хеш-код. И возвращается оно для каждого объекта через вызов функции hashCode(). Есть правило, что при переопределении метода equals(Object) необходимо переопределять и hashCode(). Потому как его использование в коллекциях основывается на предположении, о котором я говорил выше – для любых равных объектов (не идентичных, двух ссылок на один объект, а равных, с точки зрения equals(Object)) хеш-коды должны быть равны. Между тем, по умолчанию реализация в качестве хеш-кода выдает адрес объекта в памяти. Почему так? Сейчас объясню.

При использовании 10 подмножеств скорость поиска теоретически может вырасти в 10 раз. Почему теоретически? Потому что это произойдет только в том случае, если хеш-коды распределены равномерно. Иначе говоря, если в половине случаев метод hashCode() будет возвращать 0, то где-то половина объектов попадет в одно подмножество. Что сильно снижает эффективность поиска. Именно потому реализация по умолчанию выдает адрес области памяти – во-первых, это обеспечивает для равных объектов (в реализации по умолчанию – равных ссылок) равные значения хеш-кодов, во-вторых – это обеспечивает более-менее равномерное распределение значения.

При реализации hashCode используется несколько простых правил. Прежде всего, при вычислении хеш-кода следует использовать те же поля, которые сравниваются в equals. Это, во-первых, даст равенство хеш-кодов для равных обектов, во-вторых, распределено полученное значение будет точно так же, как и исходные данные. Теоретически, можно сделать так, чтобы хеш-код всегда был равен 0, и это будет абсолютно легальная реализация. Другое дело, что ее ценность будет равна тому же самому нулю.

Далее. Несмотря на то, что хеш-коды равных объектов должны быть равны, обратное неверно! Два неравных объекта могут иметь равные хеш-коды. Решающее значение имеет не уникальность, а скорость вычисления, потому как это приходится делать очень часто. Потому, в некоторых случаях имеет смысл посчитать хеш-код заранее и просто выдавать его по запросу. Прежде всего это стоит делать тогда, когда вычисление трудоемко, а объект неизменен.

Простейшая реализация hashCode и equals может выглядеть где-то так (все несущественные методы опущены):

public class PhoneBookEntry{

    private String ownerName;
    private int countryCode;
    private int areaCode;
    private int number;

    public boolean equals(Object obj){
        if (!(obj instanceof PhoneBookEntry))
            return false;
        PhoneBookEntry entry = (PhoneBookEntry)obj;
        return ownerName.equals(entry.ownerName) &&
               countryCode == entry.countryCode &&
               areaCode == entry.areaCode &&
               number == entry.number;
    }

    public int hashCode(){
        int hash = 37;
        hash = hash*17 + ownerName.hashCode();
        hash = hash*17 + countryCode;
        hash = hash*17 + areaCode;
        hash = hash*17 + number;
        return hash;
    }

}

Умножение на 17 применено для лучшего распределения значений. Иначе, например, в случае использования простой суммы, значения могут быть сосредоточены в очень небольшом диапазоне. При отсутствии в этом примере строки так и было бы – значения хеш-кода были бы в диапазоне 0-1001000, за очень редким исключением, при том, что диапазон значений int больше почти в 5000 раз.

На тонкостях реализации я останавливаться не буду, они очень хорошо описаны в книге Джошуа Блоха Java. Эффективное программирование, статья 8. Там же есть и рецепты по написанию хорошего метода hashCode().

Описаный мною выше способ ускорения поиска путем разбиения на подмножества – на самом деле есть реализация интерфейса java.util.Map – java.util.HashMap. Как следует из названия, эта реализация построена на использовании хеш-кода. И потому, если вы хотите реализовать объект, который собираетесь потом использовать в качестве ключа в HashMap – вам необходимо переопределить методы hashCode() и equals(Object). О том, что произойдет, если этого не сделать, читайте ниже.

Перейдем к следующему разделу.

Набор уникальных объектов – коллекции java.util.Set

В Java имеется интерфейс, определяющий коллекцию, содержащую уникальные элементы. Это интерфейс java.util.Set. Основная его реализация – java.util.HashSet. Хочу сказать пару слов об этой реализации. В ее основе лежит уже упомянутая выше коллекция HashMap. Элементы HashSet на самом деле являются ключами в HashMap, следовательно, к ним предъявляются те же требования, что и к ключам, а именно – переопределение hashCode() и equals(Object).

Особо хочу оговорить (и обратить ваше внимание!) вот какой момент: вышесказанное относится к реализациям java.util.Set, но не его наследника java.util.SortedSet. В какой-то степени это нарушение принципов ООП, ибо наследника всегда можно рассматривать как объект родительского класса, во всяком случае, можно ожидать соответствующего родителю поведения. Между тем, в данном случае это не совсем так. Подробнее я коснусь этого вопроса в разделе, посвященом упорядоченным коллекциям.

Однако, простое сравнение объектов – это не весь класс задач. Очень часто нам приходится не устанавливать идентичность объектов, а упорядочивать их. Т.е. от двоичной логики (равен/не равен) мы переходим к троичной – меньше/равен/больше. Об этом и пойдет речь.

Упорядочивание – интерфейс java.lang.Comparable

Подобно тому, как equals(Object) предназначен для унификации процедуры сравнения по содержимому, точно так же хочется иметь и метод, который бы унифицировал процесс упорядочивания по все тому же содержимому. Но, поскольку все объекты можно сравнить, но далеко не все объекты можно логически упорядочить, этот метод имеет смысл вынести в отдельный интерфейс, который можно было бы реализовать в случае необходимости. Именно так и появился интерфейс java.lang.Comparable.

Прежде всего он удобен для сортировки упорядоченных списков (java.util.List) и массивов объектов. Если список/массив содержит элементы, реализующие этот интерфейс, то они могут быть отсортированы автоматически методами java.util.Collections.sort(List)/Arrays.sort(Object[]).

С интерфейсом Comparable связано понятие натурального упорядочивания, потому как он устанавливает натуральный порядок следования экземпляров любого класса, реализующего этот интерфейс. Иначе говоря, порядок (x, y) соответствует выполнению условия x.compareTo(y) <= 0.

Правила реализации Comparable, а вернее, его метода compareTo(Object) следующие (x и y – экземпляры класса, реализующего Comparable):

  • x.compareTo(y) возвращает -1 или 1, если x должен находиться, соответственно, раньше или позже y. Если метод возвращает 0, то порядки (x, y) и (y, x) эквивалентны.
  • Если sign(a) – функция, возвращающая -1,0,1 для а, соответственно, меньше 0, равного 0 и больше 0, то должно выполняться равенство sign(x.compareTo(y))==-sign(y.compareTo(x)). Что логично: если x идет раньше y, то y должен идти позже x, и наоборот.
  • Если x.compareTo(y) > 0 и y.compareTo(z) > 0, то x.compareTo(z) > 0 – соотношение транзитивности неравенств.
  • Если x.compareTo(y) == 0, то sign(x.compare(z)) == sign(y.compareTo(z)), для любых z.
  • Вызов x.compareTo(null) должен бросать исключение NullPointerException. В этом есть расхождение с логикой реализации equals (напомню, x.equals(null) возвращает false).
  • Если y по своему типу не может быть сравнен с x, то вызов x.compareTo(y) должен бросать исключение ClassCastException.
  • (x.compareTo(y) == 0) == x.equals(y), т.е. вызов x.compareTo(y) должен возвращать 0 тогда и только тогда, когда x.equals(y) возвращает true. Это правило непротиворечивости, и его очень важно учитывать. О том, что будет, если этого не делать, я расскажу ниже. Хотя, теоретически это правило из разряда "очень желательно".

Реализация Comparable для приведенного выше класса PhoneBookEntry может быть такой (упорядочение по имени, потом по коду страны, потом по коду города, потом по номеру):

public class PhoneBookEntry implements Comparable{

    private String ownerName;
    private int countryCode;
    private int areaCode;
    private int number;

    public boolean equals(Object obj){
        if (!(obj instanceof PhoneBookEntry))
            return false;
        PhoneBookEntry entry = (PhoneBookEntry)obj;
        return ownerName.equals(entry.ownerName) &&
               countryCode == entry.countryCode &&
               areaCode == entry.areaCode &&
               number == entry.number;
    }

    public int hashCode(){
        int hash = 37;
        hash = hash*17 + ownerName.hashCode();
        hash = hash*17 + countryCode;
        hash = hash*17 + areaCode;
        hash = hash*17 + number;
        return hash;
    }

    public int compareTo(Object obj){
        PhoneBookEntry entry = (PhoneBookEntry)obj;
        int result = ownerName.compareTo(entry.ownerName);
        if (result != 0) return result;
        result = countryCode – entry.countryCode;
        if (result != 0) return (int)(result/Math.abs(result));
        result = areaCode – entry.areaCode;
        if (result != 0) return (int)(result/Math.abs(result));
        result = number – entry.number;
        return (result != 0) ? (int)(result/Math.abs(result)) : 0;
    }

}

Кроме автоматической сортировки списков и массивов интерфейс Comparable используется в упорядоченных коллекциях. О них и поговорим.

Упорядоченные коллекции – java.util.SortedSet и java.util.SortedMap

Упорядочение этих коллекций означает только то, что итератор по элементам SortedSet или по ключам SortedMap будет возвращать элементы в порядке, определенном их реализацией интерфейса Comparable. Казалось бы, все просто. Внешне – да.

Однако тут зарыта огромная собака для тех, кто не любит читать документацию. Дело в том, что согласно ей (документации, не собаке!) натуральный порядок элементов SortedSet либо ключей SortedMap не должен находиться в противоречии с реализацией метода equals (который, напомню, вместе с hashCode должен быть переопределен, если вы хотите использовать объект в качестве ключа или помещать его в Set). Иначе говоря, обязано выполняться последнее из правил реализации Comparable. Как я и обещал, возможные проблемы в случае невыполнения этого правила я опишу ниже.

Еще один момент, который знать нелишне. Реализация SortedMap, TreeMap, в отличие от HashMap не использует hashCode(). Их внутренняя структура основана на красно-черном дереве. Соответственно, по сравнению с постоянным временем поиска HashMap в случае TreeMap время поиска зависит от количества элементов (log(n)). Во всяком случае, это верно для TreeMap/TreeSet, потому как TreeSet реализован на основе TreeMap.

Пойдем дальше. Может возникнуть вопрос – а что делать, если необходимо сортировать одни и те же объекты по-разному? Comparable предполагает единственный порядок сравнения. Между тем, в случае с PhoneBookEntry может быть необходимо отсортировать объекты сначала по коду страны и коду города, а уж потом по имени и номеру. И что делать?

Как говорил Гость с Юга из фильма "Чародеи" – "Выход есть! Есть выход!" Надо использовать ...

"Внешнее" сравнение – интерфейс java.util.Comparator

Термин "внешнее", на самом деле, – мой. Я называю это сравнение внешним, потому что его логика находится вне сравниваемых объектов. А суть его проста: нужно реализовать интерфейс java.util.Comparator. Его метод compare(x,y) в точности соответствует по своей сути вызову x.compareTo(y). Точно так же должны выполняться все правила, о которых я упоминал выше.

Comparator может использоваться в любом месте, где нужна сортировка. При этом, во-первых, появляется необходимая гибкость – возможность реализации нескольких правил сортировки. А во-вторых, сортируемые объекты могут не реализовывать интерфейс Comparable. В случае, если они его все-таки реализуют, Comparator имеет приоритет.

Реализация Comparator для приведенного выше случая сортировки (код страны -> код города -> имя -> номер) выглядит так:

public class PhoneBookEntryComparator implements Comparator{

    public int compare(Object obj1, Object obj2){
        PhoneBookEntry entry1 = (PhoneBookEntry)obj1;
        PhoneBookEntry entry2 = (PhoneBookEntry)obj2;
        int result = entry1.getCountryCode() – entry2.getCountryCode();
        if (result != 0) return (int)(result/Math.abs(result));
        result = entry1.getAreaCode() – entry2.getAreaCode();
        if (result != 0) return (int)(result/Math.abs(result));
        result = entry1.getOwnerName().compareTo(entry2.getOwnerName());
        if (result != 0) return (int)(result/Math.abs(result));
        result = entry1.getNumber() – entry2.getNumber();
        return (result != 0) ? (int)(result/Math.abs(result)) : 0;
    }

}

Замечание 1. В реализации используются методы getXXX, которые возвращают значения соответствующих полей класса и просто были опущены для краткости.

Замечание 2. Интерфейс Comparator определяет еще и метод equals(Object), как это ни парадоксально. Этот метод служит для сравнения самих экземпляров интерфейса Comparator и должен возвращать true только в том случае, если сравниваемые объекты обеспечивают одинаковый порядок сортировки. Однако всегда безопасно оставлять исходную реализацию Object.equals(Object) нетронутой, именно потому метод не был реализован.

Замечание 3. В Java 5.0 Comparator имеет параметризуемый тип. Потому, в этом случае реализация будет несколько проще:

public class PhoneBookEntryComparator implements Comparator<PhoneBookEntry>{

    public int compare(PhoneBookEntry entry1, PhoneBookEntry entry2){
        // приведения типа не нужны, в остальном реализация та же
    }

}

Следующий вопрос, который я хотел бы рассмотреть –

Сравнение, упорядочивание и наследование

Пусть у нас есть класс "точка" – всего лишь две координаты. Его код будет таким:

public class Point{

    private int x;
    private int y;

    public Point(int x, int y){
        this.x = x;
        this.y = y;
    }

    public boolean equals(Object obj){
        if (!(obj instanceof Point)) // !!!
            return false;
        Point p = (Point)obj;
        return x==p.x && y==p.y;
    }

    public int hashCode(){
        return (17+x)*37+y;
    }

    public int getX(){
        return x;
    }

    public int getY(){
        return y;
    }

}

Второй класс, который мы определим – "цветная точка":

public class ColoredPoint extends Point{

    private Color color;

    public ColoredPoint(int x, int y, Color color){
        super(x,y);
        this.color = color;
    }

    public Color gerColor(){
        return color;
    }

    public int hashCode(){
        return super.hashCode()*37 + color.hashCode();
    }

    public boolean equals(Object obj){
        if (!super.equals(obj))
            return false;
        if (!(obj instanceof ColoredPoint))  // !!!
            return false;
        ColoredPoint cp = (ColoredPoint)obj;
        return color.equals(cp.color);
    }

}

Пока вроде все логично. Мы можем сравнивать объекты только одного класса, потому в строках с комментарием в конце "// !!!" стоит проверка на принадлежность объекта к определенному типу.

Вот тут, собственно, и находятся грабли. Большие и увесистые. Вспомним про правило симметрии: если x.equals(y), то y.equals(x). Посмотрим на следующий код:

public class Tester{

    public static void main(String args[]){
        Point p = new Point(0,0);
        ColoredPoint cp = new ColoredPoint(0,0,Color.red);
        System.out.println("p.equals(cp): "+p.equals(cp));
        System.out.println("сp.equals(p): "+сp.equals(p));
    }

}

Каков будет результат:

p.equals(cp): true
cp.equals(p): false

Вопрос. Почему?

Все просто. Именно так и должно быть. Потому как цветная точка безусловно является точкой. И проверку на принадлежность к типу Point объект класса ColoredPoint пройдет. А поскольку координаты равны, объекты будут считаться равными.

Обратное же неверно – точка не является цветной точкой, потому проверку на принадлежность к типу ColoredPoint объект класса Point не пройдет. Со всеми вытекающими последствиями.

Печально то, что эта проблема фундаментальна. Она не имеет корректного решения. Можно в сравнении ограничиться, к примеру, только объектами данного класса, исключив наследников – сравнивать придется не через instanceof, а с помощью this.getClass().equals(obj.getClass()). Однако это можно расценивать как нарушение основного принципа наследования – любой объект дочернего класса может по праву считаться объектом родительского класса.

Точно та же картина и с реализацией compareTo, с одним исключением – сравнение cp.compareTo(p) будет бросать исключение ClassCastException, т.е. объект класса Point нельзя привести к типу ColoredPoint.

Вообще, честно говоря, с проблемой этой приходится сталкиваться не так часто. Если вообще приходится. Мне не довелось ни разу. Однако знать о ней необходимо, чтобы при реализации проявлять осторожность. Можно, к примеру, вместо наследования создать класс, который содержит внутри себя точку и цвет, т.е., применить композицию. В некоторых случаях это может дать преимущества. Советую на эту тему почитать уже упомянутую книгу Блоха Java. Эффективное программирование, статьи 7 и 14.

Вот мы и подошли к последнему разделу. Тут мы поговорим о том, что будет, если делать не так, как положено.

Несовместимость в реализациях equals, hashCode, compareTo и её последствия

Начнем с простого. Что будет, если переопределить equals, но не переопределить hashCode? Будем расуждать логически. Пусть у нас есть два равных с точки зрения equals объекта. Если не переопределить hashCode, то вероятность того, что эти два объекта попадут в одно подмножество в HashSet, – эта вероятность крайне низка. Ненулевая, но все же низкая. А это значит, что два равных с вашей точки зрения объекта попадут в HashSet с очень большой вероятностью. Если же эти объекты использовать в качестве ключей в HashMap (используя один объект как ключ, положить значение, используя другой – искать его), то значение, проассоциированное с ключом, найдено не будет. Опять-таки, с большой вероятностью. И это хуже всего. Если бы вероятность была 100% – ошибку искать было бы намного проще.

Все вышесказаное верно и для случая, когда hashCode переопределен, но неверно – так, что для двух объектов, равных с точки зрения equals, hashCode возвращает разные значения.

Пойдем дальше. Обратная ситуация: переопределен hashCode, но не переопределен equals. Тут ситуация проще. В том плане что, поскольку именно возвращаемое значение equals является критерием равенства в неупорядоченных коллекциях, – два равных по содержимому объекта гарантированно не будут признаны равными ни в HashSet, ни при поиске по ключу в HashMap. А, следовательно, ошибку найти проще.

Перейдем теперь к реализации compareTo. Пусть equals у двух объектов возвращает true, а compareTo – не 0. Положим оба объекта в SortedSet (в TreeSet для простоты). Поскольку сравнение в SortedSet идет ТОЛЬКО с использованием compareTo, оба объекта благополучно окажутся в коллекции. А теперь переложим все элементы в HashSet. Тут критерием равенства будет equals, а потому – во вторую коллекцию попадет только один элемент. Что вызывает вполне понятное недоумение у людей, не знакомых с предметом.

Рассмотрим обратную ситуацию – compareTo возвращает 0, а equals – false. Положим объекты в HashSet. Они все окажутся в коллекции, спасибо методу equals. Переложим их в TreeSet, с помощью метода addAll. Увы, во второй коллекции окажется только один объект.

Кстати говоря, ошибки в реализации compareTo встречаются довольно часто. Обусловлено это желанием отсортировать объекты по определенному признаку, во-первых, и незнанием правил реализации, во-вторых. Если же вам действительно надо отсортировать объекты только по некоторым из полей, использующихся в equals, – могу посоветовать положить их в List и использовать Collections.sort(List, Comparator).

Уф-ф-ф! Финиш!

* * *

С теорией вроде закончили. Во второй части мы поговорим о сравнении уже на практике, там тоже немало интересного. Вот она: Сравнение объектов: практика. Читайте!



В начало