Лучшие практики для переопределения isEqual: и hash
Как правильно переопределить isEqual: в Objective-C? "Подвох", кажется, заключается в том, что если два объекта равны (как определено isEqual: метод), они должны иметь одинаковое хеш-значение.
В разделе " Самоанализ " Руководства по основам какао приведен пример переопределения 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?
(Мозг пердеть: Первоначально написал "побитовое ИЛИ" их вместе с |=, Значит добавить.)
17 ответов
Начать с
NSUInteger prime = 31;
NSUInteger result = 1;
Тогда для каждого примитива вы делаете
result = prime * result + var
Для 64-битной системы вы также можете использовать Shift и Xor.
result = prime * result + (int) (var ^ (var >>> 32));
Для объектов вы используете 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, вам необходимо убедиться, что хэши, возвращаемые этими значениями, равномерно распределены по всему диапазону возможных значений хеш-функции., Это значительно улучшит вашу производительность.
Существует множество алгоритмов хэширования, в том числе несколько перечисленных здесь. Я стараюсь избегать создания новых алгоритмов хеширования, поскольку это может иметь большое влияние на производительность, поэтому использование существующих методов хеширования и выполнение побитовой комбинации некоторого рода, как вы делаете в своем примере, является хорошим способом избежать этого.
Простое XOR над значениями хеша критических свойств достаточно в 99% случаев.
Например:
- (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;
Это неоднократно заканчивалось неудачей (то есть возвращалось НЕТ) без ошибок, когда я знал, что объекты были идентичны в моем модульном тестировании. Причина была в том, что один из NSString переменные экземпляра были равны нулю, поэтому приведенное выше утверждение было:
if (![nil isEqual: nil])
return NO;
и так как ноль будет отвечать на любой метод, это совершенно законно, но
[nil isEqual: nil]
возвращает ноль, то есть НЕТ, поэтому, когда и у объекта, и у тестируемого был нулевой объект, они считались бы не равными (т.е.isEqual: вернул бы НЕТ).
Это простое исправление состояло в том, чтобы изменить оператор 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: (например, сравнение строк без учета регистра). Для целых можно вообще использовать сам int, если вы не будете сравнивать с NSNumbers.
Не используйте |=, хотя, это насытит. Вместо этого используйте ^=.
Случайный забавный факт: [[NSNumber numberWithInt:0] isEqual:[NSNumber numberWithBool:NO]], но [[NSNumber numberWithInt:0] hash] != [[NSNumber numberWithBool:NO] hash], (rdar://4538282, открыт с 05 мая 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
Заметьте, я не затрудняюсь указывать город, страну и т. Д. Название достаточно. Возможно название и название.
Хеш должен быть равномерно распределен. Таким образом, вы можете объединить несколько переменных членов с помощью символа ^ (знак xor)
Так что это что-то вроде
hash = self.member1.hash ^ self.member2.hash ^ self.member3.hash
Таким образом, хэш будет равномерно распределен.
Hash must be O(1), and not O(n)
Так что же делать в массиве?
Опять все просто. Вам не нужно хэшировать все элементы массива. Достаточно хешировать первый элемент, последний элемент, количество, может быть, некоторые средние элементы, и все.
Контракты equals и hash хорошо определены и тщательно исследованы в мире 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 не имеет эквивалента.
Держись, конечно, гораздо более простой способ сделать это - сначала переопределить - (NSString )description и предоставьте строковое представление состояния вашего объекта (вы должны представить все состояние вашего объекта в этой строке).
Затем просто предоставьте следующую реализацию hash:
- (NSUInteger)hash {
return [[self description] hash];
}
Это основано на принципе, что "если два строковых объекта равны (как определено isEqualToString: метод), они должны иметь одинаковое значение хеш-функции".
Источник: Ссылка класса NSString
Я обнаружил, что эта страница является полезным руководством по переопределению методов типа equals и hash. Он включает в себя достойный алгоритм для вычисления хэш-кодов. Страница ориентирована на Java, но ее довольно легко адаптировать к Objective-C/Cocoa.
Это не дает прямого ответа на ваш вопрос (вообще), но я использовал MurmurHash прежде, чтобы генерировать хэши: murmurhash
Думаю, я должен объяснить, почему: ропот быстро
Я тоже новичок в Objective C, но я нашел отличную статью об идентичности и равенстве в Objective C здесь. Из моего прочтения видно, что вы можете сохранить хеш-функцию по умолчанию (которая должна обеспечивать уникальную идентичность) и реализовать метод isEqual, чтобы он сравнивал значения данных.
Комбинируя ответ @tcurdt с ответом @oscar-gomez для получения имен свойств, мы можем создать простое решение для вставки для isEqual и hash:
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);
}
Квинн просто ошибается, что ссылка на хэш ропота здесь бесполезна. Куинн прав, что вы хотите понять теорию хеширования. Ропот превращает большую часть этой теории в реализацию. Выяснение того, как применить эту реализацию к этому конкретному приложению, заслуживает изучения.
Некоторые из ключевых моментов здесь:
Пример функции из tcurdt предполагает, что "31" является хорошим множителем, потому что он является простым. Нужно показать, что простота является необходимым и достаточным условием. На самом деле 31 (и 7), вероятно, не особенно хорошие простые числа, потому что 31 == -1 % 32. Нечетный множитель с примерно половиной установленных битов и половиной очищенных битов, вероятно, будет лучше. (Константа умножения хэша рота имеет это свойство.)
Этот тип хеш-функции, вероятно, был бы сильнее, если бы после умножения значение результата было скорректировано с помощью сдвига и xor. Умножение имеет тенденцию давать результаты большого количества битовых взаимодействий в верхнем конце регистра и низкие результаты взаимодействия в нижнем конце регистра. Shift и xor увеличивают взаимодействия в нижнем конце регистра.
Установка начального результата в значение, при котором около половины битов равны нулю, а около половины битов равны единице, также может оказаться полезным.
Может быть полезно быть осторожным относительно порядка, в котором элементы комбинируются. Вероятно, следует сначала обработать логические значения и другие элементы, где значения не сильно распределены.
Может быть полезно добавить пару дополнительных этапов скремблирования битов в конце вычисления.
Является ли хамор на самом деле быстрым для этого приложения - вопрос открытый. Хэш бормотания предварительно смешивает биты каждого входного слова. Несколько входных слов могут обрабатываться параллельно, что помогает многопоточному конвейерному процессору.
Обратите внимание, что если вы создаете объект, который может быть изменен после создания, значение хеш-функции не должно изменяться, если объект вставлен в коллекцию. На практике это означает, что значение хеш-функции должно быть зафиксировано с момента создания исходного объекта. См . Документацию Apple по методу -hash протокола NSObject для получения дополнительной информации:
Если изменяемый объект добавляется в коллекцию, которая использует хеш-значения для определения позиции объекта в коллекции, значение, возвращаемое методом хеш-функции объекта, не должно изменяться, пока объект находится в коллекции. Следовательно, либо метод хеширования не должен полагаться на какую-либо информацию о внутреннем состоянии объекта, либо вы должны убедиться, что информация о внутреннем состоянии объекта не изменяется, пока объект находится в коллекции. Таким образом, например, изменяемый словарь может быть помещен в хеш-таблицу, но вы не должны изменять его, пока он там. (Обратите внимание, что может быть трудно узнать, находится ли данный объект в коллекции.)
Для меня это звучит как полный удар, так как он потенциально делает рендеринг хеша гораздо менее эффективным, но я полагаю, что лучше ошибиться с осторожностью и следовать указаниям документации.
Извините, если я рискну озвучить полный гроб здесь, но...... никто не потрудился упомянуть, что для того, чтобы следовать "наилучшим методам", вам определенно не следует указывать метод equals, который НЕ учитывал бы все данные, принадлежащие вашему целевому объекту, например любые данные агрегируются в ваш объект, и его сопоставление следует учитывать при реализации equals. Если вы не хотите принимать во внимание, скажем, "возраст", то вы должны написать компаратор и использовать его для сравнения, а не isEqual:.
Если вы определяете isEqual: метод, который произвольно выполняет сравнение на равенство, вы рискуете использовать этот метод другим разработчиком или даже самим собой, когда вы забыли "поворот" в своей интерпретации равенства.
Таким образом, хотя это замечательные вопросы о хешировании, обычно вам не нужно переопределять метод хеширования, вам, вероятно, следует вместо этого определить специальный компаратор.