-hash / -isEqual の実装:/ -isEqualTo…:Objective-C コレクションの場合

https://stackoverflow.com/questions/1112373

12-09-2019
|

質問

注記： 次の SO の質問は関連していますが、特に等価性テストの実装に関連して、それらもリンクされたリソースも私の質問に完全には答えていないようです。 オブジェクトのコレクション.

背景

NSObjectが提供するのは デフォルト の実装 -hash (これはインスタンスのアドレスを返します。 (NSUInteger)self）そして -isEqual: (返されるのは NO ただし、受信側とパラメータのアドレスが同一である場合は除きます。これらのメソッドは必要に応じてオーバーライドされるように設計されていますが、ドキュメントでは両方を提供するか、どちらも提供しないことが明確に示されています。さらに、 -isEqual: 戻り値 YES 2 つのオブジェクトの場合、次の結果 -hash それらのオブジェクトに対して しなければならない 同じであること。そうでない場合、同じであるべきオブジェクトが同じである場合、たとえば 2 つの文字列インスタンスが同じである場合に問題が発生する可能性があります。 -compare: 戻り値 NSOrderedSame — Cocoa コレクションに追加されるか、直接比較されます。

コンテクスト

私は開発します CHDataStructures.framework, 、Objective-C データ構造のオープンソースライブラリ。私は数多くのコレクションを実装しており、現在それらの機能を改良および強化しています。私が追加したい機能の 1 つは、コレクションが等しいかどうかを別のコレクションと比較する機能です。

これらの比較では、メモリアドレスのみを比較するのではなく、2 つのコレクションに存在するオブジェクト (該当する場合は順序付けも含む) を考慮する必要があります。このアプローチは Cocoa でかなり前例があり、通常は次のような別のメソッドを使用します。

カスタムコレクションを等価性のテストに対して堅牢なものにしたいと考えています。そうすれば、カスタムコレクションを他のコレクションに安全に (そして予想どおりに) 追加でき、他のコレクション (NSSet など) が 2 つのコレクションが等しい/同等/重複であるかどうかを判断できるようになります。

問題点

アン -isEqualTo...: メソッドはそれ自体でうまく機能しますが、通常、これらのメソッドを定義するクラスもオーバーライドします。 -isEqual: 呼び出す [self isEqualTo...:] パラメータが受信側と同じクラス (またはサブクラス) である場合、または [super isEqual:] さもないと。これは、クラスでも定義する必要があることを意味します -hash これにより、同じ内容を持つ異なるインスタンスに対して同じ値が返されます。

さらに、Apple のドキュメントでは、 -hash では次のように規定されています。(私のことを強調)

「コレクション内でのオブジェクトの位置を決定するためにハッシュ値を使用するコレクションに変更可能なオブジェクトが追加された場合、オブジェクトがコレクション内にある間、オブジェクトのハッシュメソッドによって返される値は変更されてはなりません。したがって、 どちらか ハッシュメソッドはオブジェクトの内部状態情報に依存してはなりません または オブジェクトがコレクション内にある間、オブジェクトの内部状態情報が変更されないことを確認する必要があります。したがって、たとえば、変更可能な辞書をハッシュテーブルに入れることはできますが、そこにある間は変更してはなりません。(特定のオブジェクトがコレクション内にあるかどうかを知るのは難しい場合があることに注意してください。)

編集： 私はなぜこれが必要なのかを明確に理解しており、その推論に完全に同意します。ここで言及したのは追加の文脈を提供するためであり、簡潔にするためになぜそうなるのかという話題は避けました。

私のコレクションはすべて変更可能であり、ハッシュは少なくとも考慮する必要があります いくつかの したがって、ここでの唯一の選択肢は、別のコレクションに格納されているコレクションを変更することはプログラミングエラーであると考えることです。(私のコレクションはすべて採用しています NSコピー, したがって、NSDictionary のようなコレクションは、キーとして使用するコピーを正常に作成できます。)

私にとって実装するのは理にかなっています -isEqual: そして -hash, 、（たとえば）私のクラスの 1 つの間接的なユーザーは、特定のクラスを知らない可能性があるためです。 -isEqualTo...: 呼び出すメソッドを指定したり、2 つのオブジェクトが同じクラスのインスタンスであるかどうかさえ考慮したりできます。彼らは電話できるはずです -isEqual: または -hash 任意の型の変数に対して id そして期待通りの結果が得られます。

とは異なり -isEqual: (比較される 2 つのインスタンスにアクセスできます)、 -hash 特定のインスタンス内のデータのみにアクセスして、結果を「盲目的に」返す必要があります。ハッシュが何に使用されているかを知ることができないため、結果は一貫している必要があります。全て等しい/同一とみなされ、常に一致する必要があるインスタンスの可能性 -isEqual:. （編集：これは以下の回答によって誤りであることが証明されており、確かに生活が楽になります。) さらに、適切なハッシュ関数を作成することは簡単ではありません。一意性を保証することは、特にそれを表す NSUInteger (32/64 ビット) しかない場合には困難です。

質問

導入時のベストプラクティスはありますか ~~等価比較~~ -hash コレクション用？
Objective-C および Cocoa 風のコレクションで計画すべき特徴はありますか?
単体テストに適したアプローチはありますか -hash ある程度の自信を持って？
実装に関する提案があれば -hash 同意する -isEqual: 任意の型の要素を含むコレクションの場合?どのような落とし穴について知っておくべきですか?(編集： 私が最初に考えていたほど問題はありませんでした— @kperrua 指摘するのは「等しい -hash 価値観はそうするない暗示する -isEqual:".)

編集： -isEqual の実装方法について混乱していないことを明確にする必要がありました。または -isEqualTo...:コレクションの場合は簡単です。私の混乱は主に、-isEqual の場合、-hash は別の値を返さなければならないと (誤って) 考えたことから生じたと思います。NOを返します。以前に暗号化を行ったことがあり、異なる値のハッシュは異なるはずだと考えていました。しかし、以下の回答を見て、「良い」ハッシュ関数とは実際には次のようなものであることに気づきました。 最小化する バケットの衝突と、使用するコレクションのチェーン -hash. 。一意のハッシュが望ましいですが、厳密な要件ではありません。

解決

私は、コレクションのためのユニークなハッシュ値を生成しますいくつかの一般的に有用なハッシュ関数を思い付くしようと考えて無益の練習です。それはハッシュ関数O（n）を作るように、すべてのコンテンツのハッシュを組み合わせるU62の提案は、うまくスケールしません。ハッシュ関数は、本当にO（1）良好なパフォーマンスを確保するために、それ以外の場合は、ハッシュの目的は敗北されるべきです。（コレクションハッシュ関数がOであれば、大きなプロパティリストの最上位の辞書のハッシュを取るしようとする（耐え難いほど遅いであろう。広告nauseum潜在的に、アレイおよび他の辞書を含む辞書であるプレースメントリストの共通ココア構築を検討N））

私の提案は、コレクションのハッシュについて多くのことを心配する必要はないだろう。あなたが述べたように、-isEqual:は等しい-hash値を意味します。一方、同じ-hash値は、にない-isEqual:を意味するものではありません。この事実は、単純なハッシュを作成するためにあなたに余裕の多くを提供します。

あなたがが衝突については本当に心配している（そして、あなたは気になる何かであることを確認し、の具体的な測定の実世界の状況の中に証拠を持っている）場合は、

は、あなたはまだへのU62のアドバイスに従うことができある程度。たとえば、コレクション内の最初および/または最後の要素、たとえば、のハッシュを取ることができる、とコレクションの-count、たとえば、とのことを兼ね備えています。それがまともなハッシュを提供するのに十分でます。

私はあなたの質問の答えは、少なくとも1つの希望ます。

1号について：-isEqual:はかなりカットし、乾燥さ実装します。あなたは、内容を列挙し、メソッドとisEqualをチェックしてください。各要素に

一つのことは、あなたのコレクション-hash機能のために行うことを決定どのような影響を与えるかもしれないのに注意するがあります。あなたのコレクションのクライアントも-isEqual:と-hashを管理する規則を理解しなければなりません。あなたがコンテンツを使用する場合-hashと-hash同意しないあなたのコレクションのisEqual:で-hashを内容ならば、あなたのコレクションが解除されますを。もちろん、クライアントのせいだが、それは、コレクションの内容を離れてあなたの-hashを基づかに対する別の引数です。

はありません。図2は、一種のあいまいです。わからない何が念頭に置いています。

他のヒント

コレクションが順序付けられている場合は、

2つのコレクションは、要素が同じ順序であることを、彼らは同じ要素が含まれている場合に等しいと考えられ、さらにする必要があります。

コレクションのためのハッシュの対象で、いくつかの方法（それらをXORまたはそれらを追加モジュロ）内の要素のハッシュを組み合わせるために十分でなければなりません。ルールはISEQUALに従って等しい2つのオブジェクトが同一のハッシュを返す必要があると述べているが、反対が成立しないことに注意：ハッシュの一意性が望ましいが、それは溶液の正確さのために必要ではありません。このように注文したコレクションは、要素の順序を考慮する必要はありません。

アップルのドキュメントからの抜粋は道によって必要な制限があります。また、同じ値を持つオブジェクトが同じハッシュを持っていることを確保しながら、オブジェクトは、突然変異の下で同じハッシュ値を維持することができませんでした。これは、オブジェクトだけでなく、コレクションの最も簡単に適用されます。もちろん、それだけで通常はそれが要素だ整理するためにハッシュを使用した容器内にあるとき、オブジェクトのハッシュが変化すること重要。このすべての結論は、別の容器の内部に置かれたときに変更可能なコレクションが変異するべきではありませんが、その後真のハッシュ関数を持つ任意のオブジェクトがすべきでもないということです。

私はNSArrayのとNSMutableArrayのデフォルトのハッシュの実装にいくつかの調査を行っていると（私は何かを誤解していない限り）それはthier独自のルールに従わないアップルのような縫い目ます：

可変オブジェクトはハッシュ値を使用してコレクションに追加された場合コレクション内のオブジェクトの位置を決定し、値が返されますオブジェクトがある一方で、オブジェクトのハッシュ法で変更しないでくださいコレクションインチそのため、どちらかのハッシュ法は、頼りにしてはなりませんオブジェクトの内部状態情報のいずれか、またはあなたは確認する必要があります一方で、オブジェクトの内部状態情報は変更されません。オブジェクトがコレクションです。したがって、例えば、可変辞書ハッシュテーブルに入れることができるが、それはしている間、あなたはそれを変更してはなりませんそこ。（与えられたかどうかを知ることは難しいことができることに注意してくださいオブジェクトがコレクションである。）

ここに私のテストコードがある

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

にNSArrayとNSMutableArrayの両方のハッシュメソッドのデフォルト実装は、配列の数であり、そのコレクション内のかどうかは気をdosn'tように、それは縫い目のでます。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow