Реализация -hash / -isEqual: / -isEqualTo...: для коллекций Objective-C

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


Фон

NSObject предоставляет реализации по умолчанию -hash (который возвращает адрес экземпляра, например (NSUInteger)self) а также -isEqual: (который возвращает NO если адреса получателя и параметра не совпадают). Эти методы предназначены для переопределения по мере необходимости, но в документации ясно сказано, что вы должны предоставить оба или ни того, ни другого. Далее, если -isEqual: возвращается YES для двух объектов, то результат -hash для этих объектов должны быть одинаковыми. Если нет, могут возникнуть проблемы, когда объекты должны быть одинаковыми - например, два экземпляра строки, для которых -compare: возвращается NSOrderedSame - добавляются в коллекцию какао или сравниваются напрямую.

контекст

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

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

  • -[NSArray isEqualToArray:]
  • -[NSDate isEqualToDate:]
  • -[NSDictionary isEqualToDictionary:]
  • -[NSNumber isEqualToNumber:]
  • -[NSSet isEqualToSet:]
  • -[NSString isEqualToString:]
  • -[NSValue isEqualToValue:]

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

Проблемы

-isEqualTo...: Метод отлично работает сам по себе, но классы, которые определяют эти методы, обычно также переопределяют -isEqual: вызывать [self isEqualTo...:] если параметр имеет тот же класс (или, возможно, подкласс), что и получатель, или [super isEqual:] иначе. Это означает, что класс также должен определять -hash так что он будет возвращать одно и то же значение для разнородных экземпляров, имеющих одинаковое содержимое.

Кроме того, документация Apple для -hash оговаривается следующее: (выделено мое)

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

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

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

Это имеет смысл для меня, чтобы реализовать -isEqual: а также -hash, поскольку (например) косвенный пользователь одного из моих классов может не знать конкретного -isEqualTo...: вызываемый метод или даже забота о том, являются ли два объекта экземплярами одного и того же класса. Они должны быть в состоянии позвонить -isEqual: или же -hash на любую переменную типа id и получить ожидаемый результат.

В отличие от -isEqual: (который имеет доступ к двум сравниваемым экземплярам), -hash должен возвращать результат "вслепую", имея доступ только к данным в конкретном экземпляре. Поскольку он не может знать, для чего используется хеш, результат должен быть согласованным для всех возможных случаев, которые следует считать равными / идентичными, и всегда должен согласовываться с -isEqual:, (Редактировать: это было опровергнуто ответами ниже, и это, безусловно, облегчает жизнь.) Кроме того, написание хороших хеш-функций нетривиально - гарантией уникальности является проблема, особенно когда у вас есть только NSUInteger (32/64 бита) в котором представлять это.

Вопросы

  1. Существуют ли лучшие практики при проведении сравнений на равенство -hash для коллекций?
  2. Есть ли какие-то особенности для планирования в коллекциях Objective-C и Cocoa?
  3. Есть ли хорошие подходы для юнит-тестирования -hash с разумной степенью уверенности?
  4. Любые предложения по реализации -hash согласиться с -isEqual: для коллекций, содержащих элементы произвольных типов? О каких подводных камнях я должен знать? (Правка: не так проблематично, как я сначала подумал - как отмечает @kperryua, "равно -hash значения не подразумевают -isEqual: ".)

Изменить: я должен был уточнить, что я не смущен о том, как реализовать -isEqual: или -isEqualTo...: для коллекций, это просто. Я думаю, что моя путаница возникла главным образом из-за (ошибочного) мнения, что -hash ДОЛЖЕН вернуть другое значение, если -isEqual: возвращает NO. Сделав криптографию в прошлом, я подумал, что хэши для разных значений ДОЛЖНЫ быть разными. Тем не менее, ответы ниже заставили меня понять, что "хорошая" хеш-функция на самом деле сводит к минимуму столкновения сегментов и цепочки для коллекций, которые используют -hash , Хотя уникальные хеши предпочтительнее, они не являются строгим требованием.

3 ответа

Решение

Я думаю, что попытка придумать какую-нибудь полезную хеш-функцию, которая будет генерировать уникальные хеш-значения для коллекций, бесполезна. Предложение U62 объединить хэши всего содержимого не будет хорошо масштабироваться, так как делает хеш-функцию O(n). Хеш-функции должны действительно иметь значение O(1), чтобы обеспечить хорошую производительность, иначе цель хеширования будет проигнорирована. (Рассмотрим общую конструкцию списков Какао, которые являются словарями, содержащими массивы и другие словари, потенциально до тошноты. Попытка взять хэш словаря верхнего уровня большого списка будет мучительно медленной, если бы хэш-функциями коллекций были O (п).)

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

Если вы действительно беспокоитесь о столкновениях (и у вас есть доказательства в конкретных измерениях реальных ситуаций, которые подтверждают, что стоит о чем-то беспокоиться), вы все равно можете в некоторой степени последовать совету U62. Например, вы можете взять хэш, скажем, первого и / или последнего элемента в коллекции, и объединить его с, скажем, -count коллекции. Этого будет достаточно, чтобы обеспечить приличный хэш.

Я надеюсь, что ответит хотя бы на один из ваших вопросов.

Что касается № 1: Реализация -isEqual: довольно резок и сух. Вы перечисляете содержимое и проверяете isEqual: на каждом из элементов.

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

№ 2 немного расплывчато. Не уверен, что ты имеешь в виду там.

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

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

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

Я провел некоторое исследование по умолчанию реализации хеша NSArray и NSMutableArray и (если я что-то не так понял) кажется, что Apple не следует своим собственным правилам:

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

Вот мой тестовый код

NSMutableArray* myMutableArray = [NSMutableArray arrayWithObjects:@"a", @"b", @"c", nil];
NSMutableArray* containerForMutableArray = [NSMutableArray arrayWithObject:myMutableArray];

NSUInteger hashBeforeMutation = [[containerForMutableArray objectAtIndex:0] hash];
[[containerForMutableArray objectAtIndex:0] removeObjectAtIndex:1];
NSUInteger hashAfterMutation = [[containerForMutableArray objectAtIndex:0] hash];

NSLog(@"Hash Before: %d", hashBeforeMutation);
NSLog(@"Hash After : %d", hashAfterMutation);

Выход:

Hash Before: 3
Hash After : 2

Таким образом, он выглядит как реализация по умолчанию для метода Hash как в NSArray, так и в NSMutableArray - счетчик массива, и ему все равно, находится он внутри коллекции или нет.

Другие вопросы по тегам