-isEqualTo …: для коллекций Objective-C

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

Рекомендации по переопределению -isEqual: and -hash
Методы для реализации -hash на изменяемых объектах cocoa

Задний план

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

контекст

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

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

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

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

Проблемы

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

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

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

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

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

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

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

Вопросов

Существуют ли лучшие практики при реализации ~~сравнений сравнений~~ -hash для коллекций?
Существуют ли какие-либо особенности для планирования в коллекциях Objective-C и Cocoa-esque?
Существуют ли какие-либо хорошие подходы для модульного тестирования -hash с достаточной степенью уверенности?
Любые предложения по реализации -hash для согласования с -isEqual: для коллекций, содержащих элементы произвольных типов? О каких ошибках я должен знать? ( Edit: Не так проблематично, как я думал сначала, как указывает @kperryua , «равные -hash значения не подразумевают -isEqual: ».)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 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 – это подсчет массива, и он не заботится о том, является ли его внутри коллекции или нет.

Как проверить, являются ли два выражения <Func > одинаковыми

LINQ Выберите «Определить» с анонимными типами

Как игнорировать маркер порядка байтов UTF-8 в сравнении строк?

Как вы сравниваете структуры для равенства в C?

Равномерность объекта jQuery

equals vs Arrays.equals в Java

Что случилось с использованием == для сравнения float в Java?