Примечание. Следующие вопросы SO связаны друг с другом, но ни они, ни связанные ресурсы, похоже, не полностью отвечают на мои вопросы, особенно в отношении выполнения тестов равенства для коллекций объектов.
- Рекомендации по переопределению -isEqual: и -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...:
отлично работает сам по себе, но классы, которые определяют эти методы, обычно также переопределяют -isEqual:
для вызова [self isEqualTo...:]
, если параметр имеет тот же класс (или, возможно, подкласс) в качестве получателя, или [super isEqual:]
в противном случае. Это означает, что класс должен также определить -hash
, чтобы он возвращал одно и то же значение для разрозненных экземпляров, имеющих одинаковое содержимое.
Кроме того, документация Apple для -hash
предусматривает следующее: (акцент мой)
"Если измененный объект добавляется в коллекцию, которая использует хэш-значения для определения позиции объекта в коллекции, значение, возвращаемое хэш-методом объекта, не должно меняться, пока объект находится в коллекции. Следовательно, или хэш-метод не должен полагаться на какую-либо информацию внутреннего состояния объекта или, вы должны убедиться, что информация о внутреннем состоянии объекта не изменяется, пока объект находится в коллекции. например, изменяемый словарь может быть помещен в хеш-таблицу, но вы не должны изменять его, пока он там. (Обратите внимание, что может быть трудно узнать, находится ли данный объект в коллекции.)"
Изменить: Я определенно понимаю, почему это необходимо и полностью согласуется с рассуждениями. Я упомянул об этом здесь, чтобы предоставить дополнительный контекст, и обошел тему о том, почему это происходит ради краткости.
Все мои коллекции изменяемы, и хэш должен будет рассмотреть хотя бы некоторое содержимое, поэтому единственным вариантом здесь является рассмотрение ошибки программирования для мутирования коллекции, хранящейся в другой коллекции. (Мои коллекции все принимают NSCopying, поэтому коллекции, такие как NSDictionary, могут успешно сделать копию для использования в качестве ключа и т.д.)
Для меня имеет смысл реализовать -isEqual:
и -hash
, поскольку (например) косвенный пользователь одного из моих классов может не знать конкретного метода -isEqualTo...:
для вызова или даже заботиться о том, являются ли два объекта экземпляры того же класса. Они должны иметь возможность вызывать -isEqual:
или -hash
для любой переменной типа id
и получать ожидаемый результат.
В отличие от -isEqual:
(который имеет доступ к двум экземплярам, которые сравниваются), -hash
должен возвращать результат "вслепую", имея доступ только к данным в конкретном экземпляре. Поскольку он не может знать, для чего используется хеш, результат должен быть последовательным для всех возможных экземпляров, которые должны считаться равными/идентичными и всегда должны совпадать с -isEqual:
удаp > . (Edit: Это было развенчано ответами ниже, и это, безусловно, облегчает жизнь.) Кроме того, писать хорошие хэш-функции нетривиально - гарантировать уникальность является проблемой, особенно когда у вас есть только NSUInteger (32/64 бит) в котором его представлять.
Вопросы
- Существуют ли лучшие практики при реализации сравнений равенства
-hash
для коллекций? - Есть ли какие-либо особенности для планирования в Objective-C и Cocoa -сеских коллекциях?
- Есть ли хорошие подходы к модульному тестированию
-hash
с разумной степенью уверенности? - Любые предложения по реализации
-hash
для согласования с-isEqual:
для коллекций, содержащих элементы произвольных типов? О каких ошибках я должен знать? ( Изменить: Не так проблематично, как я думал сначала, - указывает @kperryua, - значения-hash
не подразумевают-isEqual:
".)
Изменить: Я должен был уточнить, что я не смущен тем, как реализовать -isEqual: или -isEqualTo...: для коллекций, это просто. Я думаю, что моя путаница возникла главным образом из (ошибочно) мысли, что -hash ДОЛЖЕН вернуть другое значение, если -isEqual: возвращает NO. Сделав криптографию в прошлом, я думал, что хеши для разных значений ДОЛЖНЫ быть разными. Однако приведенные ниже ответы помогли мне понять, что "хорошая" хеш-функция действительно о минимизации коллизий и цепочки цепочек для коллекций, которые используют -hash
. Хотя уникальные хеши предпочтительнее, они не являются строгим требованием.