Лучшие практики для переопределения isEqual: и hash - PullRequest
Новая
       51

Лучшие практики для переопределения isEqual: и hash

263 голосов
/ 31 октября 2008

Как правильно переопределить isEqual: в Objective-C? «Подвох», по-видимому, заключается в том, что если два объекта равны (как определено методом isEqual:), они должны иметь одинаковое значение хеш-функции.

Раздел Introspection Руководства по основам какао содержит пример переопределения isEqual:, скопированного следующим образом для класса с именем MyWidget: 

- (BOOL)isEqual:(id)other {
    if (other == self)
        return YES;
    if (!other || ![other isKindOfClass:[self class]])
        return NO;
    return [self isEqualToWidget:other];
}

- (BOOL)isEqualToWidget:(MyWidget *)aWidget {
    if (self == aWidget)
        return YES;
    if (![(id)[self name] isEqual:[aWidget name]])
        return NO;
    if (![[self data] isEqualToData:[aWidget data]])
        return NO;
    return YES;
}

Он проверяет равенство указателей, затем равенство классов и, наконец, сравнивает объекты, используя isEqualToWidget:, который проверяет только свойства name и data. Пример не показывает, как переопределить hash.

Предположим, есть другие свойства, которые не влияют на равенство, скажем, age. Не следует ли переопределить метод hash таким образом, чтобы только хэши влияли только на name и data? И если так, как бы вы это сделали? Просто добавьте хэши name и data? Например: 

- (NSUInteger)hash {
    NSUInteger hash = 0;
    hash += [[self name] hash];
    hash += [[self data] hash];
    return hash;
}

Этого достаточно? Есть ли лучшая техника? Что если у вас есть примитивы, такие как int? Преобразовать их в NSNumber, чтобы получить их хэш? Или структурирует как NSRect?

( Мозговое пердеть : Первоначально написал "побитовое ИЛИ" их вместе с |=. Значит добавить.)

Ответы [ 16 ]

110 голосов
/ 31 октября 2008

Начните с 

 NSUInteger prime = 31;
 NSUInteger result = 1;

Тогда для каждого примитива вы делаете 

 result = prime * result + var

Для 64-битных систем вам также может потребоваться сдвиг и xor. 

 result = prime * result + (int) (var ^ (var >>> 32));

Для объектов вы используете 0 для nil и в противном случае их хеш-код. 

 result = prime * result + [var hash];

Для логических значений вы используете два разных значения 

 result = prime * result + (var)?1231:1237;

Объяснение и атрибуция

Это не работа Цурдта, и в комментариях требовалось больше объяснений, поэтому я считаю, что редактирование для атрибуции справедливо.

Этот алгоритм был популяризирован в книге «Эффективная Java», и соответствующая глава в настоящее время может быть найдена здесь . Эта книга популяризировала алгоритм, который теперь используется по умолчанию во многих Java-приложениях (включая Eclipse). Однако он произошел от еще более старой реализации, которая по-разному приписывается Дэну Бернштейну или Крису Тореку. Этот старый алгоритм изначально использовался в Usenet, и определенная атрибуция затруднена. Например, в этом коде Apache есть интересный комментарий (поиск по их именам), который ссылается на первоисточник.

Суть в том, что это очень старый, простой алгоритм хеширования. Он не самый производительный, и математически даже не доказано, что он является «хорошим» алгоритмом. Но это просто, и многие люди использовали его в течение длительного времени с хорошими результатами, поэтому он имеет большую историческую поддержку.

81 голосов
/ 31 октября 2008

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

С другой стороны, если 2 экземпляра не равны, они могут иметь или не иметь один и тот же хэш - лучше, если они этого не делают. В этом разница между поиском O (1) в хеш-таблице и поиском O (N) - если все ваши хеш-коды сталкиваются, вы можете обнаружить, что поиск в вашей таблице не лучше, чем поиск в списке.

С точки зрения лучших практик ваш хеш должен возвращать случайное распределение значений для своего ввода. Это означает, что, например, если у вас есть double, но большинство ваших значений имеют тенденцию кластеризоваться между 0 и 100, вам необходимо убедиться, что хэши, возвращаемые этими значениями, равномерно распределены по всему диапазону возможных значений хеш-функции. , Это значительно улучшит вашу производительность.

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

31 голосов
/ 16 ноября 2013

Достаточно простого XOR над значениями хеша критических свойств 99% времени.

Например: 

- (NSUInteger)hash
{
    return [self.name hash] ^ [self.data hash];
}

Решение найдено в http://nshipster.com/equality/ Мэттом Томпсоном (который также упоминал этот вопрос в своем посте!)

27 голосов
/ 26 ноября 2010

Я нашел эту ветку чрезвычайно полезной, предоставляя все, что мне нужно для реализации моих isEqual: и hash методов, реализованных с помощью одной зацепки При тестировании переменных экземпляра объекта в isEqual: код примера использует: 

if (![(id)[self name] isEqual:[aWidget name]])
    return NO;

Это неоднократно не удавалось ( то есть , возвращалось NO ) без ошибок и ошибок, когда я знал объекты были идентичны в моем устройстве тестирование. Причина была в том, что одна из NSString переменных экземпляра была nil , поэтому вышеприведенное утверждение было: 

if (![nil isEqual: nil])
    return NO;

и поскольку ноль будет отвечать на любой метод, это совершенно законно, но 

[nil isEqual: nil]

возвращает nil , что составляет NO , поэтому, когда и объект, и объект, который тестируется, имеют nil объект, они будут считаться не равными ( т.е. , isEqual: вернет NO ).

Это простое исправление состояло в том, чтобы изменить оператор if на: 

if ([self name] != [aWidget name] && ![(id)[self name] isEqual:[aWidget name]])
    return NO;

Таким образом, если их адреса одинаковы, он пропускает вызов метода, независимо от того, оба они nil или оба указывают на один и тот же объект, но если один из них не nil или они указывают на разные объекты, тогда компаратор соответствующим образом называется.

Надеюсь, это сэкономит кому-то несколько минут от царапин на голове.

20 голосов
/ 09 декабря 2010

Хеш-функция должна создавать полууникальное значение, которое вряд ли столкнется или совпадет с хеш-значением другого объекта.

Вот полная хеш-функция, которую можно адаптировать к переменным экземпляра ваших классов. Он использует NSUInteger вместо int для совместимости с 64/32-битными приложениями.

Если результат станет 0 для разных объектов, вы рискуете столкнуться с хэшами. Столкновение хэшей может привести к неожиданному поведению программы при работе с некоторыми классами коллекций, которые зависят от хэш-функции. Обязательно проверьте свою хеш-функцию перед использованием. 

-(NSUInteger)hash {
    NSUInteger result = 1;
    NSUInteger prime = 31;
    NSUInteger yesPrime = 1231;
    NSUInteger noPrime = 1237;

    // Add any object that already has a hash function (NSString)
    result = prime * result + [self.myObject hash];

    // Add primitive variables (int)
    result = prime * result + self.primitiveVariable; 

    // Boolean values (BOOL)
    result = prime * result + self.isSelected?yesPrime:noPrime;

    return result;
}
13 голосов
/ 31 октября 2008

Простой, но неэффективный способ - вернуть одно и то же значение -hash для каждого экземпляра. В противном случае, да, вы должны реализовать хеш, основанный только на объектах, которые влияют на равенство. Это сложно, если вы используете слабые сравнения в -isEqual: (например, сравнение строк без учета регистра). Для целых обычно можно использовать сам int, если вы не будете сравнивать с NSNumbers.

Не используйте | =, однако, это насытит. Вместо этого используйте ^ =.

Случайный забавный факт: [[NSNumber numberWithInt:0] isEqual:[NSNumber numberWithBool:NO]], но [[NSNumber numberWithInt:0] hash] != [[NSNumber numberWithBool:NO] hash]. (рдар: // 4538282, открыт с 05 мая 2006 г.)

10 голосов
/ 24 сентября 2012

Помните, что вам нужно указывать хеш, равный только тогда, когда isEqual имеет значение true. Когда isEqual ложно, хеш не должен быть неравным, хотя, предположительно, это так. Следовательно:

Сохраняйте хэш простым. Выберите переменную члена (или нескольких членов), которая является наиболее отличительной.

Например, для CLPlacemark достаточно только имени. Да, есть 2 или 3 отличия CLPlacemark с одинаковыми именами, но они встречаются редко. Используйте этот хэш. 

@interface CLPlacemark (equal)
- (BOOL)isEqual:(CLPlacemark*)other;
@end

@implementation CLPlacemark (equal)

... 

-(NSUInteger) hash
{
    return self.name.hash;
}


@end

Обратите внимание: я не беспокоюсь об указании города, страны и т. Д. Название достаточно. Возможно имя и название.

Хеш должен быть равномерно распределен. Таким образом, вы можете объединить несколько переменных членов, используя символ ^ (знак xor)

Так что-то вроде 

hash = self.member1.hash ^ self.member2.hash ^ self.member3.hash

Таким образом, хэш будет равномерно распределен. 

Hash must be O(1), and not O(n)

Так что же делать в массиве?

Опять все просто. Вам не нужно хэшировать все элементы массива. Достаточно хешировать первый элемент, последний элемент, количество, может быть, некоторые средние элементы, и все.

7 голосов
/ 18 января 2012

Постойте, конечно, гораздо более простой способ сделать это - сначала переопределить - (NSString )description и предоставить строковое представление состояния вашего объекта (вы должны представить все состояние вашего объекта в этой строке).

Затем просто предоставьте следующую реализацию hash: 

- (NSUInteger)hash {
    return [[self description] hash];
}

Это основано на принципе, что «если два строковых объекта равны (как определено методом isEqualToString:), они должны иметь одинаковое значение хеш-функции».

Источник: Ссылка на класс NSString

5 голосов
/ 19 мая 2013

Равные и хеш-контракты хорошо определены и тщательно исследованы в мире Java (см. Ответ @ mipardi), но все те же соображения должны применяться к Objective-C.

Eclipse выполняет надежную работу по генерации этих методов в Java, поэтому вот пример Eclipse, перенесенный вручную в Objective-C: 

- (BOOL)isEqual:(id)object {
    if (self == object)
        return true;
    if ([self class] != [object class])
        return false;
    MyWidget *other = (MyWidget *)object;
    if (_name == nil) {
        if (other->_name != nil)
            return false;
    }
    else if (![_name isEqual:other->_name])
        return false;
    if (_data == nil) {
        if (other->_data != nil)
            return false;
    }
    else if (![_data isEqual:other->_data])
        return false;
    return true;
}

- (NSUInteger)hash {
    const NSUInteger prime = 31;
    NSUInteger result = 1;
    result = prime * result + [_name hash];
    result = prime * result + [_data hash];
    return result;
}

И для подкласса YourWidget, который добавляет свойство serialNo: 

- (BOOL)isEqual:(id)object {
    if (self == object)
        return true;
    if (![super isEqual:object])
        return false;
    if ([self class] != [object class])
        return false;
    YourWidget *other = (YourWidget *)object;
    if (_serialNo == nil) {
        if (other->_serialNo != nil)
            return false;
    }
    else if (![_serialNo isEqual:other->_serialNo])
        return false;
    return true;
}

- (NSUInteger)hash {
    const NSUInteger prime = 31;
    NSUInteger result = [super hash];
    result = prime * result + [_serialNo hash];
    return result;
}

В этой реализации исключены некоторые подводные камни в образце isEqual: от Apple:

  • Тест класса Apple other isKindOfClass:[self class] является асимметричным для двух разных подклассов MyWidget. Равенство должно быть симметричным: a = b тогда и только тогда, когда b = a. Это можно легко исправить, изменив тест на other isKindOfClass:[MyWidget class], тогда все подклассы MyWidget будут взаимно сопоставимы.
  • Использование теста подкласса isKindOfClass: предотвращает переопределение подклассами isEqual: с уточненным тестом на равенство. Это потому, что равенство должно быть транзитивным: если a = b и a = c, то b = c. Если экземпляр MyWidget сравнивается равным двум YourWidget экземплярам, ​​то эти YourWidget экземпляры должны сравниваться равными друг другу, даже если их serialNo отличается.

Вторую проблему можно устранить, считая объекты равными, только если они принадлежат к одному и тому же классу, следовательно, здесь тест [self class] != [object class]. Для типичных классов приложений этот подход кажется наилучшим.

Однако, безусловно, есть случаи, когда тест isKindOfClass: предпочтительнее. Это более типично для каркасных классов , чем для классов приложений. Например, любой NSString должен сравниваться равным с любым другим NSString с той же базовой последовательностью символов, независимо от различия NSString / NSMutableString, а также независимо от того, какие частные классы в кластере классов NSString участвуют.

В таких случаях isEqual: должно иметь четко определенное, хорошо документированное поведение, и должно быть ясно, что подклассы не могут переопределить это. В Java ограничение «без переопределения» можно применить, помечая методы equals и hashcode как final, но Objective-C не имеет эквивалента.

5 голосов
/ 31 октября 2008

Это напрямую не отвечает на ваш вопрос (вообще), но я использовал MurmurHash прежде, чтобы генерировать хэши: murmurhash

Думаю, я должен объяснить, почему: ропот быстро чертовски ...

Страница:
...