Методы реализации -hash на изменяемых объектах Какао

Question

В документации для -hash говорится, что она не должна изменяться, пока изменяемый объект хранится в коллекции, и аналогично в документации для -isEqual: говорится, что значение -hash должно быть одинаковым для равных объектов.

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

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

РЕДАКТИРОВАТЬ: Мне интересно, возможно ли сохранить 2 контракта (где равные объекты имеют одинаковые хеши, и хеши не меняются, пока объект находится в коллекции), когда я мутирует внутреннее состояние объекта. Я склонен сказать «нет», если только я не сделаю что-то глупое, например, всегда возвращаю 0 для хэша, но именно поэтому я задаю этот вопрос.

Answer 1

Интересный вопрос, но я думаю, что вы хотите, логически невозможно. Допустим, вы начинаете с 2 объектов, A и B. Они оба разные, и они начинаются с разных хеш-кодов. Вы добавляете оба к некоторой хэш-таблице. Теперь вы хотите изменить A, но вы не можете изменить хеш-код, потому что он уже находится в таблице. Тем не менее, можно изменить A таким образом, чтобы он .equals () B.

В этом случае у вас есть 2 варианта, ни один из которых не работает:

1. Измените хеш-код A на равный B.hashcode, что нарушает ограничение не изменять хеш-коды в хэш-таблице.
2. Не изменяйте хеш-код, в этом случае A.equals (B), но они не имеют одинаковые хеш-коды.

Мне кажется, что невозможно сделать это без использования константы в качестве хеш-кода.

Answer 2

Мое чтение документации заключается в том, что значение изменяемого объекта для hash может (и, вероятно, должно) изменяться при его мутировании, но не должно изменяться , когда объект не мутировал. Поэтому в части документации, на которую следует ссылаться, говорится: «Не изменяйте объекты, хранящиеся в коллекции, потому что это приведет к изменению их значения hash».

Цитировать напрямую из документации NSObject для hash:

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

(Акцент мой.)

Answer 3

Вопрос здесь не в том, как удовлетворить оба эти требования, а в том, какое из них должно удовлетворить. В документации Apple четко указано, что:

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

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

Просто чтобы закончить свой ответ, я приведу пример хорошей реализации хэша. Допустим, вы пишете реализацию -hash для созданной вами коллекции. Эта коллекция хранит массив NSObjects как указатели. Поскольку все NSObject реализуют хеш-функцию, вы можете использовать их хеш при вычислении хеша коллекции:

- (NSUInteger)hash {
    NSUInteger theHash = 0;
    for (NSObject * aPtr in self) { // fast enumeration
        theHash ^= [aPtr hash];
    }
    return theHash;
}

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

Answer 4

Ответ на этот вопрос и ключ к предотвращению многих ошибок какао:

Внимательно прочитайте документацию. Поместите каждое слово и пунктуацию в золотую шкалу и взвесьте, как это было последнее зерно пшеницы в мире.

Давайте снова прочитаем документацию:

Если изменяемый объект добавлен в коллекцию, которая использует хеш-значения для определения позиции объекта в коллекции, [...]

(выделено мое).

Что автор документации, в своей вечной мудрости, подразумевает под этим то, что когда вы реализуете коллекцию, например словарь, вы не должны использовать хеш для позиционирования, поскольку это может измениться. Другими словами, это не имеет ничего общего с реализацией -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, в противном случае).

Answer 5

Поскольку вы уже переопределяете -isEqual: для сравнения на основе значений вы уверены, что вам действительно нужно беспокоиться о -hash?

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

Answer 6

В Java большинство изменяемых классов просто не переопределяют Object.hashCode () , поэтому реализация по умолчанию возвращает значение, основанное на адресе объекта и не изменяющееся. Это может быть то же самое с Objective C.