Методы реализации -hash на изменяемых объектах Какао
Документация для -hash говорит, что он не должен изменяться, пока изменяемый объект хранится в коллекции, а также документация для -isEqual: говорит -hash значение должно быть одинаковым для равных объектов.
Учитывая это, кто-нибудь есть какие-либо предложения для лучшего способа реализации -hash таким образом, что он удовлетворяет обоим этим условиям и все же фактически вычисляется разумно (то есть не просто возвращает 0)? Кто-нибудь знает, как изменяемые версии классов, предоставляемых фреймворком, делают это?
Самое простое, что можно сделать, это, конечно, просто забыть первое условие (чтобы оно не менялось) и просто убедиться, что я никогда не изменю объект случайно, пока он находится в коллекции, но мне интересно, есть ли какое-нибудь решение, более гибкое.
РЕДАКТИРОВАТЬ: мне интересно здесь, возможно ли сохранить 2 контракта (где равные объекты имеют одинаковые хэши, и хэши не меняются, пока объект находится в коллекции), когда я изменяю внутреннее состояние объекта. Я склонен сказать "нет", если только я не сделаю что-нибудь глупое, например, всегда возвращаю 0 для хэша, но именно поэтому я задаю этот вопрос.
6 ответов
Интересный вопрос, но я думаю, что вы хотите, логически невозможно. Допустим, вы начинаете с двух объектов, A и B. Они оба разные, и они начинаются с разных хэш-кодов. Вы добавляете оба к некоторой хэш-таблице. Теперь вы хотите изменить A, но вы не можете изменить хеш-код, потому что он уже находится в таблице. Тем не менее, можно изменить A таким образом, чтобы он.equals() B.
В этом случае у вас есть 2 варианта, ни один из которых не работает:
- Измените хеш-код A на равный B.hashcode, что нарушает ограничение не изменять хеш-коды в хеш-таблице.
- Не меняйте хеш-код, в этом случае A.equals(B), но они не имеют одинаковые хеш-коды.
Мне кажется, что невозможно сделать это без использования константы в качестве хеш-кода.
Мое чтение документации заключается в том, что значение изменяемого объекта для hash может (и, вероятно, должен) измениться, когда он мутировал, но не должен измениться, когда объект не был мутирован. Поэтому часть документации, на которую следует ссылаться, гласит: "Не изменяйте объекты, которые хранятся в коллекции, потому что это приведет к их hash значение для изменения."
Цитировать непосредственно из документации NSObject дляhash:
Если изменяемый объект добавляется в коллекцию, которая использует хеш-значения для определения позиции объекта в коллекции, значение, возвращаемое методом хеш-функции объекта, не должно изменяться, пока объект находится в коллекции. Следовательно, либо метод хеширования не должен полагаться на какую-либо информацию о внутреннем состоянии объекта, либо вы должны убедиться, что информация о внутреннем состоянии объекта не изменяется, пока объект находится в коллекции.
(Акцент мой.)
Вопрос здесь не в том, как удовлетворить оба эти требования, а в том, какое из них вы должны выполнить. В документации Apple четко указано, что:
изменяемый словарь может быть помещен в хеш-таблицу, но вы не должны изменять его, пока он там находится.
При этом, кажется, более важно, чтобы вы соответствовали требованию равенства хэшей. Хеш объекта всегда должен быть способом проверить, равен ли объект другому. Если это не так, это не настоящая хеш-функция.
Просто чтобы закончить свой ответ, я приведу пример хорошей реализации хеша. Допустим, вы пишете реализацию -hash на коллекции, которую вы создали. Эта коллекция хранит массив NSObjects как указатели. Поскольку все NSObject реализуют хеш-функцию, вы можете использовать их хеш-значения для вычисления хеша коллекции:
- (NSUInteger)hash {
NSUInteger theHash = 0;
for (NSObject * aPtr in self) { // fast enumeration
theHash ^= [aPtr hash];
}
return theHash;
}
Таким образом, два объекта коллекции, содержащие одинаковые указатели (в одном и том же порядке), будут иметь одинаковый хэш.
Поскольку вы уже переопределяете -isEqual: чтобы провести сравнение на основе значений, вы уверены, что вам действительно нужно беспокоиться о -hash?
Конечно, я не могу догадаться, для чего именно это вам нужно, но если вы хотите проводить сравнение на основе значений, не отклоняясь от ожидаемой реализации -isEqual: возвращать YES только тогда, когда хэши идентичны, лучшим подходом может быть подражание -IsEqualToString: NSString, поэтому для создания собственного -isEqualToFoo: метода вместо использования или переопределения -isEqual:.
Ответ на этот вопрос и ключ к предотвращению многих ошибок какао:
Внимательно прочитайте документацию. Поместите каждое слово и пунктуацию в золотую шкалу и взвесьте, как это было последнее зерно пшеницы в мире.
Давайте снова прочитаем документацию:
Если изменяемый объект добавлен в коллекцию, которая использует хэш-значения для определения позиции объекта в коллекции, [...]
(акцент мой).
Автор этой документации в своей вечной мудрости подразумевает под этим то, что когда вы реализуете коллекцию, например, словарь, вы не должны использовать хеш для позиционирования, поскольку это может измениться. Другими словами, это не имеет ничего общего с реализацией -hash на изменчивых объектах Какао (что все мы думали, что это имело место, предполагая, что документация не изменилась за последние ~10 лет после того, как вопрос был задан).
Вот почему словари всегда копируют свои ключи - так что они могут гарантировать, что значение хеша не изменится.
Затем вы зададите вопрос: Но, сэр, как NSMapTable и подобные ему справляются с этим?
Ответ на это согласно документации:
"Его ключи или значения могут быть скопированы на входе или могут использовать идентичность указателя для равенства и хеширования".
(снова акцент мой).
Поскольку в прошлый раз нас так легко одурачила документация, давайте проведем небольшой эксперимент, чтобы убедиться, как все работает на самом деле:
NSMutableString *string = [NSMutableString stringWithString:@"so lets mutate this"];
NSString *originalString = string.copy;
NSMapTable *mutableStrings = [NSMapTable strongToStrongObjectsMapTable];
[mutableStrings setObject:originalString forKey:string];
[string appendString:@" into a larger string"];
if ([mutableStrings objectForKey:string] == nil)
NSLog(@"not found!");
if ([mutableStrings objectForKey:originalString] == nil)
NSLog(@"Not even the original string is found?");
for (NSString *inCollection in mutableStrings)
{
NSLog(@"key '%@' : is '%@' (null)", inCollection, [mutableStrings objectForKey:inCollection]);
}
for (NSString *value in NSAllMapTableValues(mutableStrings))
{
NSLog(@"value exists: %@", value);
}
Сюрприз!
Таким образом, вместо использования указателя равенства они сосредотачиваются здесь на словах "может", которые в данном случае означают "не может", и просто копируют значение хеша при добавлении материала в коллекцию.
(Все это на самом деле хорошо, так как было бы довольно сложно реализовать NSHashMap или -hash, в противном случае).
В Java большинство изменяемых классов просто не переопределяют Object.hashCode(), поэтому реализация по умолчанию возвращает значение, основанное на адресе объекта и не изменяющееся. Это может быть то же самое с целью С.