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

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

46 голосов
/ 11 июля 2009

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

Фон

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

Контекст

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

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

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

Проблемы

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

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

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

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

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

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

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

Вопросы

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

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

Ответы [ 3 ]

18 голосов
/ 11 июля 2009

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

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

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

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

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

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

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

4 голосов
/ 11 июля 2009

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

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

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

3 голосов
/ 10 июля 2012

Я провел некоторое исследование по умолчанию реализации хеша 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 - счетчик массива, и ему все равно, находится ли он внутри коллекции.

...