1

NSObject Protocol Referenceには、「2 つのオブジェクトが等しい場合、それらは同じハッシュ値を持つ必要がある」と書かれています。

なぜしなければならないのですか？同じハッシュ値を持たない 2 つの等しいオブジェクトの問題は何でしょうか?

4

2 に答える 2

7

そうすると、基本的に、ハッシュ テーブルで等しい値を検索することができなくなります。ハッシュ コードは基本的に、ハッシュ テーブル (またはハッシュ セット) 内で一致する可能性のあるキーをすばやく見つける方法として使用されます。これは、「オブジェクトの等価性はハッシュの等価性を意味する」という契約に依存しています。

クイックルックアップのためにハッシュを使用するものでオブジェクトを使用する予定がない場合は、異なるハッシュコードを返す同等のオブジェクトを使用することでうまくいくかもしれませんが、できれば避けたいと思います。

于 2012-05-22T15:32:09.427 に答える
2

以下は、ハッシュ テーブルがどのように機能するかを簡単に説明したものです。NSSet はハッシュ テーブルです。

基本構造

N 個の NSMutableArray の NSArray を割り当てます。外側の配列を「テーブル」、内側の配列を「リスト」と呼びましょう。この構造がハッシュ テーブルです。

挿入の仕組み

オブジェクトを挿入するには、'hash' を呼び出します。これにより、数値が得られます。0 から (N - 1) の間になるように数値を切り捨てます。その結果をテーブルのインデックスとして扱います。そのスロット (リスト) の変更可能な配列に移動し、「オブジェクト」が既にリストにあるかどうかを確認し、そうでない場合は追加します。もしそうなら、何もすることはありません。

ルックアップの仕組み

値がハッシュ テーブルにあるかどうかを確認するには、その値に対して hash を呼び出します。これにより、数値が得られます。0 から (N - 1) の間になるように数値を切り捨てます。その結果をテーブルのインデックスとして扱います。そのスロット (リスト) の変更可能な配列に移動し、「オブジェクト」が既にリストにあるかどうかを確認します。そこにある場合、テーブルにはオブジェクトが含まれますが、そうでない場合は含まれません。

等しいオブジェクトが等しいハッシュ値を持つ必要があるのはなぜですか?

ハッシュ コードは、検索するリストを見つけるために使用されます。2 つのオブジェクトが概念的には等しいがハッシュ値が異なる場合、上記の外側のテーブルを検索すると、オブジェクトが 2 つの異なるリストに解決されるため、期待されるリストにオブジェクトが見つかりません。

于 2012-05-22T17:22:01.160 に答える