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

Question

Как правильно переопределить 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?

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

Answer 1

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

Answer 2

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

Answer 3

Сочетая ответ @ 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);
}

Answer 4

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

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

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

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

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

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

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

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

Answer 5

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

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

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

Answer 6

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

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

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