2009-01-14 58 views
10

-hash的文檔說明,當可變對象存儲在集合中時,它不能更改,並且類似地-isEqual:的文檔說明-hash值必須與相同對象的值相同。用於在可變可可對象上實現-hash的技巧

鑑於此,是否有人對實施-hash的最佳方式有任何建議,以使其符合這兩個條件,但是實際上是智能計算的(即不僅僅返回0)?有誰知道框架提供的類的可變版本是如何做到的?

最簡單的事情當然就是忘記第一個條件(關於它不會改變),並且確保我在事件集合中不會意外地改變對象,但是我想知道是否有任何解決方案更多靈活。

編輯:我不知道這裏是否有可能維持2個合同(其中相等的對象具有相同的哈希值,並且當對象是一個集合的哈希值不改變)當我變異內部對象的狀態。我的意思是說「不」,除非我做了一些愚蠢的事情,比如總是爲散列返回0,但這就是爲什麼我要問這個問題。

+0

猜測這是一個老問題,剛剛發現它......但不是可變對象用作通常複製的集合中的鍵嗎?這不就是爲了避開這個問題嗎? – nielsbot 2012-03-16 03:24:09

+0

@nielsbot:只複製NSDictionaries的密鑰。 NSSet不復制它的對象,`CFDictionarySetValue()`API也不復制它的鍵。 – 2012-03-16 04:29:28

+0

`CFDictionarySetValue`確實會將`kCFTypeDictionaryKeyCallbacks`傳遞給`CFDictionaryCreate`,否?文檔幾乎是非感性的......我想一個可變集合obj可以,呃,緩存散列值,這與假設一個集合中的可變obj不會改變它的散列相同,對吧? – nielsbot 2012-03-16 08:36:46

回答

2

有趣的問題,但我想你想要的是邏輯上是不可能。假設你從2個對象A和B開始。它們都不同,它們以不同的哈希碼開始。你將兩個都添加到一個哈希表。現在,你想改變A,但你不能改變哈希碼,因爲它已經在表中了。但是,可以用這樣的方式來改變A,即.equals()B.

在這種情況下,你有兩個選擇,而且作品:

  1. 變遷的哈希碼等於B.hashcode,違反不改變的哈希碼,而在哈希表的約束。
  2. 不要更改散列碼,在這種情況下,A.equals(B)但它們不具有相同的散列碼。

在我看來,沒有可能的方式做到這一點,而不使用常量作爲散列碼。

-2

在Java中,大多數可變類完全不會覆蓋Object.hashCode(),因此默認實現將返回基於對象地址且不會更改的值。它可能只是同與目標C.

2

我的文檔閱讀是一個可變對象爲hash可以(也許應該)變化值,當它發生突變,但不應該變化,當對象沒有發生變異。因此,要引用的文檔部分是這樣說的:「不要改變存儲在集合中的對象,因爲這會導致其值更改。」

要直接從NSObject documentation for hash引證:

如果可變對象被添加到使用散列值來 確定對象的所述 集合中的位置,由 散列方法返回的值的 集合的對象不能在 集合中更改,而對象位於 集合中。 因此,無論是散 方法不能依賴於任何的 對象的內部狀態信息或 您必須確保對象的 內部狀態信息不 變化,而對象是 集合英寸

(重點煤礦。)

0

既然你已經重寫-isEqual:做一個基於價值的比較,你確定你真的需要打擾-hash嗎?

我無法猜到你當然需要什麼,但是如果你想在不偏離預期的-isEqual實現的情況下進行基於價值的比較:只有當哈希值相同時才返回YES,更好的方法可能是模仿NSString的-isEqualToString :,所以要創建你自己的-isEqualToFoo:方法,而不是使用或覆蓋-isEqual :.

1

這裏的問題並不是如何滿足這兩個要求,而是你應該在哪一個見面。在Apple的文檔中,明確指出:

可變字典可以放在哈希表中,但不能在哈希表中進行更改。

這就是說,看起來更重要的是你滿足哈希的平等要求。對象的散列應始終是檢查對象是否與另一個對象相同的一種方法。如果情況並非如此,那麼它不是一個真正的散列函數。

爲了完成我的回答,我將舉一個好的散列實現的例子。假設您正在爲您創建的集合編寫-hash的實現。該集合將一組NSObject作爲指針存儲。由於所有NSObjects實現哈希函數,你可以用自己的哈希值計算集合的哈希值:

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

這樣,含有相同的指針(以相同的順序)兩個收集對象將具有相同的哈希值。