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

Начать с

 NSUInteger prime = 31;
 NSUInteger result = 1;

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

 result = prime * result + var

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

 result = prime * result + [var hash];

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

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

Объяснение и авторство

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

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

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

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

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

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

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

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

Например:

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

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

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

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

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

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

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

[nil isEqual: nil]

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

Это простое исправление заключалось в изменении оператора if на:

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

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

Надеюсь, это избавит кого-то от нескольких минут почесывания головы.

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

Вот полная хеш-функция, которую можно адаптировать к переменным экземпляра ваших классов. Он использует 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;
}

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

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

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

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

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

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

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

@implementation CLPlacemark (equal)

...

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


@end

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

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

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

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

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

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

Итак, что делать в массиве?

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

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

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

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

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

Источник: Справочник по классу NSString

Контракты равенства и хеширования хорошо определены и тщательно исследованы в мире 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 с той же базовой последовательностью символов, независимо от различия _20 _ / _ 21_, а также независимо от того, какие частные классы в кластере классов NSString задействованы.

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

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

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

Я нашел эта страница, чтобы быть полезным руководством по переопределению методов равного и хеш-типа. В нем есть неплохой алгоритм вычисления хэш-кодов. Страница ориентирована на Java, но ее довольно легко адаптировать к Objective-C / Cocoa.

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

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

Некоторые из ключевых моментов здесь:

Пример функции из tcurdt предполагает, что «31» - хороший множитель, потому что он простой. Нужно показать, что простота - необходимое и достаточное условие. На самом деле 31 (и 7), вероятно, не очень хорошие простые числа, потому что 31 == -1% 32. Нечетный умножитель с примерно половиной установленных битов и половиной битов очищенными, вероятно, будет лучше. (Этим свойством обладает константа умножения хэша murmur.)

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

Установка начального результата на значение, при котором примерно половина битов равна нулю, а примерно половина битов равна единице, также может быть полезной.

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

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

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

Комбинируя ответ @ tcurdt с ответом @ oscar-gomez для получения имен свойств, мы можем создать простое решение для обоих isEqual и хэш:

NSArray *PropertyNamesFromObject(id object)
{
    unsigned int propertyCount = 0;
    objc_property_t * properties = class_copyPropertyList([object class], &propertyCount);
    NSMutableArray *propertyNames = [NSMutableArray arrayWithCapacity:propertyCount];

    for (unsigned int i = 0; i < propertyCount; ++i) {
        objc_property_t property = properties[i];
        const char * name = property_getName(property);
        NSString *propertyName = [NSString stringWithUTF8String:name];
        [propertyNames addObject:propertyName];
    }
    free(properties);
    return propertyNames;
}

BOOL IsEqualObjects(id object1, id object2)
{
    if (object1 == object2)
        return YES;
    if (!object1 || ![object2 isKindOfClass:[object1 class]])
        return NO;

    NSArray *propertyNames = PropertyNamesFromObject(object1);
    for (NSString *propertyName in propertyNames) {
        if (([object1 valueForKey:propertyName] != [object2 valueForKey:propertyName])
            && (![[object1 valueForKey:propertyName] isEqual:[object2 valueForKey:propertyName]])) return NO;
    }

    return YES;
}

NSUInteger MagicHash(id object)
{
    NSUInteger prime = 31;
    NSUInteger result = 1;

    NSArray *propertyNames = PropertyNamesFromObject(object);

    for (NSString *propertyName in propertyNames) {
        id value = [object valueForKey:propertyName];
        result = prime * result + [value hash];
    }

    return result;
}

Теперь в вашем пользовательском классе вы можете легко реализовать isEqual: и hash:

- (NSUInteger)hash
{
    return MagicHash(self);
}

- (BOOL)isEqual:(id)other
{
    return IsEqualObjects(self, other);
}

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

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

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

Извините, если я рискну показаться здесь полным болваном, но ... ... никто не позаботился упомянуть, что для следования `` лучшим практикам '' вам определенно не следует указывать метод equals, который НЕ будет учитывать все данные, принадлежащие вашему целевому объекту, например, что угодно данные агрегированы для вашего объекта, а не ассоциированного с ним, следует учитывать при реализации equals. Если вы не хотите принимать во внимание, скажем, «возраст» при сравнении, тогда вам следует написать компаратор и использовать его для сравнения вместо isEqual :.

Если вы определяете метод isEqual:, который произвольно выполняет сравнение на равенство, вы подвергаетесь риску того, что этот метод будет неправильно использован другим разработчиком или даже вами, если вы забудете «поворот» в своей интерпретации равенства.

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