objective-c - isEqual: および hash をオーバーライドするためのベストプラクティス

Question

isEqual:Objective-C で適切にオーバーライドするにはどうすればよいですか? 「キャッチ」は、2 つのオブジェクトが (メソッドによって決定されるように) 等しい場合isEqual:、それらは同じハッシュ値を持つ必要があるようです。

Cocoa Fundamentals GuideのIntrospectionセクションには、という名前のクラスについて、次のようにコピーされたをオーバーライドする方法の例があります。isEqual:MyWidget

- (BOOL)isEqual:(id)other {
    if (other == self)
        return YES;
    if (!other || ![other isKindOfClass:[self class]])
        return NO;
    return [self isEqualToWidget:other];
}

- (BOOL)isEqualToWidget:(MyWidget *)aWidget {
    if (self == aWidget)
        return YES;
    if (![(id)[self name] isEqual:[aWidget name]])
        return NO;
    if (![[self data] isEqualToData:[aWidget data]])
        return NO;
    return YES;
}

ポインターの等価性、次にクラスの等価性をチェックし、最後にとプロパティisEqualToWidget:のみをチェックするを使用してオブジェクトを比較します。例が示していないのは、オーバーライドする方法です。namedatahash

等式に影響しない他のプロパティがあると仮定しましょうage。ハッシュのみに影響を与えるhashようにメソッドをオーバーライドするべきではありませんか? もしそうなら、どうやってそれをしますか？とのハッシュを追加するだけですか？例えば：namedatanamedata

- (NSUInteger)hash {
    NSUInteger hash = 0;
    hash += [[self name] hash];
    hash += [[self data] hash];
    return hash;
}

それで十分ですか？より良いテクニックはありますか？のようなプリミティブがある場合はどうなりますintか? それらを変換しNSNumberてハッシュを取得しますか? またはのような構造体NSRect？

( Brain fart : 元々は「bitwise OR」をと一緒に書きました|=。加算を意味します。)

score 114 · Accepted Answer

皮切りに

 NSUInteger prime = 31;
 NSUInteger result = 1;

次に、すべてのプリミティブに対して

 result = prime * result + var

オブジェクトの場合、nilには0を使用し、それ以外の場合はハッシュコードを使用します。

 result = prime * result + [var hash];

ブール値の場合、2つの異なる値を使用します

 result = prime * result + ((var)?1231:1237);

説明と帰属

これはtcurdtの仕事ではなく、コメントはより多くの説明を求めていたので、帰属の編集は公正であると私は信じています。

このアルゴリズムは「EffectiveJava」という本で普及しており、関連する章は現在オンラインでここにあります。その本はアルゴリズムを普及させました。そして、それは現在多くのJavaアプリケーション（Eclipseを含む）のデフォルトです。ただし、これは、DanBernsteinまたはChrisTorekにさまざまに起因するさらに古い実装から派生したものです。その古いアルゴリズムは元々Usenetに浮かんでおり、特定の帰属は困難です。たとえば、このApacheコード（名前を検索）には、元のソースを参照する興味深い解説がいくつかあります。

結論として、これは非常に古くて単純なハッシュアルゴリズムです。これは最もパフォーマンスが高いわけではなく、数学的に「優れた」アルゴリズムであることが証明されていません。でもシンプルで、長い間使っていて良い結果が出ているので、歴史的にも多くの支持を得ています。

score 81 · Accepted Answer

私は自分で Objective-C を手に入れたばかりなので、その言語について具体的に話すことはできませんが、私が使用する他の言語では、2 つのインスタンスが「等しい」場合、同じハッシュを返す必要があります。それらをハッシュテーブル（または任意の辞書タイプのコレクション）のキーとして使用しようとすると、さまざまな問題が発生します。

一方、2 つのインスタンスが等しくない場合、同じハッシュを持つ場合と持たない場合があります。同じでない場合が最善です。これは、ハッシュテーブルでの O(1) 検索と O(N) 検索の違いです。すべてのハッシュが衝突した場合、テーブルを検索してもリストを検索するよりも優れているとは限りません。

ベストプラクティスに関しては、ハッシュはその入力に対してランダムな分布の値を返す必要があります。これは、たとえば、double があるが、値の大部分が 0 から 100 の間でクラスター化する傾向がある場合、それらの値によって返されるハッシュが可能なハッシュ値の範囲全体に均等に分散されていることを確認する必要があることを意味します。 . これにより、パフォーマンスが大幅に向上します。

ここにリストされているいくつかを含め、そこには多数のハッシュアルゴリズムがあります。パフォーマンスに大きな影響を与える可能性があるため、新しいハッシュアルゴリズムを作成しないようにしています。そのため、既存のハッシュメソッドを使用し、例で行っているようにビット単位の組み合わせを行うことは、それを回避する良い方法です。

score 27 · Accepted Answer

このスレッドは、自分isEqual:とhashメソッドを1つのキャッチで実装するために必要なすべてのものを提供するのに非常に役立ちました。isEqual:サンプルコードでオブジェクトインスタンス変数をテストする場合、以下を使用します。

if (![(id)[self name] isEqual:[aWidget name]])
    return NO;

単体テストでオブジェクトが同一であることがわかった場合、これはエラーなしで繰り返し失敗しました（つまり、 NOが返されました）。その理由は、インスタンス変数の1つがnilであったため、上記のステートメントは次のとおりでした。NSString

if (![nil isEqual: nil])
    return NO;

nilはどのメソッドにも応答するため、これは完全に合法ですが

[nil isEqual: nil]

nilを返します。これはNOであるため、オブジェクトとテスト対象のオブジェクトの両方にnilオブジェクトがある場合、それらは等しくないと見なされます（つまり、NOisEqual:を返します）。

この簡単な修正は、ifステートメントを次のように変更することでした。

if ([self name] != [aWidget name] && ![(id)[self name] isEqual:[aWidget name]])
    return NO;

このように、アドレスが同じである場合、両方がnilであるか、両方が同じオブジェクトを指しているかに関係なく、メソッド呼び出しをスキップしますが、どちらかがnilでないか、異なるオブジェクトを指している場合、コンパレータは適切に呼び出されます。

これにより、誰かが頭をかいて数分節約できることを願っています。

score 22 · Accepted Answer

ハッシュ関数は、別のオブジェクトのハッシュ値と衝突または一致する可能性が低い、ある程度一意の値を作成する必要があります。

クラスのインスタンス変数に適用できる完全なハッシュ関数を次に示します。64/32 ビットアプリケーションでの互換性のために、int ではなく NSUInteger を使用します。

異なるオブジェクトの結果が 0 になると、ハッシュが衝突する危険性があります。ハッシュが衝突すると、ハッシュ関数に依存するコレクションクラスの一部を操作するときに、予期しないプログラムの動作が発生する可能性があります。ハッシュ関数を使用する前に必ずテストしてください。

-(NSUInteger)hash {
    NSUInteger result = 1;
    NSUInteger prime = 31;
    NSUInteger yesPrime = 1231;
    NSUInteger noPrime = 1237;
    
    // Add any object that already has a hash function (NSString)
    result = prime * result + [self.myObject hash];
    
    // Add primitive variables (int)
    result = prime * result + self.primitiveVariable; 

    // Boolean values (BOOL)
    result = prime * result + (self.isSelected ? yesPrime : noPrime);
    
    return result;
}

score 12 · Accepted Answer

-hash簡単ですが非効率的な方法は、すべてのインスタンスに対して同じ値を返すことです。それ以外の場合は、同等に影響するオブジェクトのみに基づいてハッシュを実装する必要があります。これは、緩い比較-isEqual:(大文字と小文字を区別しない文字列比較など) を使用する場合には注意が必要です。int の場合、NSNumbers と比較する場合を除き、通常は int 自体を使用できます。

ただし、|= は使用しないでください。飽和します。代わりに ^= を使用してください。

ランダムな楽しい事実: [[NSNumber numberWithInt:0] isEqual:[NSNumber numberWithBool:NO]]、しかし[[NSNumber numberWithInt:0] hash] != [[NSNumber numberWithBool:NO] hash]. (rdar://4538282、2006 年 5 月 5 日からオープン)

score 9 · Accepted Answer

isEqualが trueの場合に等しいハッシュを提供するだけでよいことに注意してください。が false の場合isEqual、ハッシュが不等である必要はありませんが、おそらく不等です。したがって：

ハッシュをシンプルに保ちます。最も特徴的なメンバー (またはいくつかのメンバー) 変数を選択します。

たとえば、CLPlacemark の場合、名前だけで十分です。はい、まったく同じ名前の 2 つまたは 3 つの異なる CLPlacemark がありますが、それらはまれです。そのハッシュを使用します。

@interface CLPlacemark (equal)
- (BOOL)isEqual:(CLPlacemark*)other;
@end

@implementation CLPlacemark (equal)

...

-(NSUInteger) hash
{
    return self.name.hash;
}


@end

都市、国などをわざわざ指定しないことに注意してください。名前で十分です。おそらく名前とCLLocation。

ハッシュは均等に分散する必要があります。したがって、キャレット ^ (xor 記号) を使用して複数のメンバー変数を組み合わせることができます。

だから、それは次のようなものです

hash = self.member1.hash ^ self.member2.hash ^ self.member3.hash

そうすれば、ハッシュは均等に分散されます。

Hash must be O(1), and not O(n)

では、配列で何をすべきか?

繰り返しますが、単純です。配列のすべてのメンバーをハッシュする必要はありません。最初の要素、最後の要素、カウント、おそらくいくつかの中間要素をハッシュするのに十分です。それだけです。

score 7 · Accepted Answer

ちょっと待ってください。これを行うためのはるかに簡単な方法は、最初にオーバーライド- (NSString )descriptionして、オブジェクトの状態の文字列表現を提供することです (この文字列でオブジェクトの状態全体を表す必要があります)。

次に、次のの実装を提供するだけですhash。

- (NSUInteger)hash {
    return [[self description] hash];
}

これは、「(isEqualToString: メソッドによって決定されるように) 2 つの文字列オブジェクトが等しい場合、それらは同じハッシュ値を持つ必要がある」という原則に基づいています。

ソース: NSString クラスリファレンス

score 5 · Accepted Answer

このページは、equals 型および hash 型のメソッドをオーバーライドする際に役立つガイドであることがわかりました。ハッシュコードを計算するための適切なアルゴリズムが含まれています。このページは Java を対象としていますが、Objective-C/Cocoa に適応させるのは非常に簡単です。

score 5 · Accepted Answer

これはあなたの質問に直接答えるものではありませんが（まったく）、以前にMurmurHashを使用してハッシュを生成しました：murmurhash

理由を説明する必要があると思います：マーマーハッシュはめちゃくちゃ速いです...

score 4 · Accepted Answer

私も Objective C の初心者ですが、Objective C の同一性と等価性に関する優れた記事を見つけました。私の読書によると、デフォルトのハッシュ関数 (一意の ID を提供する必要があります) を保持し、データ値を比較するように isEqual メソッドを実装できるように見えます。

score 3 · Accepted Answer

クインは、ここでつぶやきハッシュへの参照が役に立たないというのは間違っています。クインは、ハッシュの背後にある理論を理解したいというのは正しいことです。雑音は、その理論の多くを実装に抽出します。その実装をこの特定のアプリケーションに適用する方法を理解することは、調査する価値があります。

ここでの重要なポイントのいくつか：

tcurdtの関数の例は、「31」が素数であるため、適切な乗数であることを示しています。素数であることは必要十分条件であることを示す必要があります。実際、31（および7）は、31 == -1％32であるため、おそらく特に良い素数ではありません。ビットが約半分に設定され、ビットが半分クリアされた奇数の乗数の方が優れている可能性があります。（つぶやきハッシュ乗算定数にはその特性があります。）

このタイプのハッシュ関数は、乗算後に結果値がshiftとxorを介して調整された場合に、より強力になる可能性があります。乗算は、レジスタの上限で多くのビット相互作用の結果を生成し、レジスタの下端で低相互作用の結果を生成する傾向があります。シフトとxorは、レジスタの下端での相互作用を増加させます。

初期結果をビットの約半分がゼロでビットの約半分が1の値に設定することも役立つ傾向があります。

要素が結合される順序に注意することが役立つ場合があります。おそらく最初に、値が強く分布していないブール値やその他の要素を処理する必要があります。

計算の最後に、ビットスクランブリングステージをいくつか追加すると便利な場合があります。

このアプリケーションでつぶやきハッシュが実際に高速であるかどうかは、未解決の問題です。murmurハッシュは、各入力ワードのビットをプレミックスします。複数の入力ワードを並行して処理できるため、複数の問題がパイプライン化されたCPUに役立ちます。

score 3 · Accepted Answer

プロパティ名を取得するための @tcurdt の回答と @oscar-gomez の回答を組み合わせて、isEqual とハッシュの両方の簡単なドロップインソリューションを作成できます。

NSArray *PropertyNamesFromObject(id object)
{
    unsigned int propertyCount = 0;
    objc_property_t * properties = class_copyPropertyList([object class], &propertyCount);
    NSMutableArray *propertyNames = [NSMutableArray arrayWithCapacity:propertyCount];

    for (unsigned int i = 0; i < propertyCount; ++i) {
        objc_property_t property = properties[i];
        const char * name = property_getName(property);
        NSString *propertyName = [NSString stringWithUTF8String:name];
        [propertyNames addObject:propertyName];
    }
    free(properties);
    return propertyNames;
}

BOOL IsEqualObjects(id object1, id object2)
{
    if (object1 == object2)
        return YES;
    if (!object1 || ![object2 isKindOfClass:[object1 class]])
        return NO;

    NSArray *propertyNames = PropertyNamesFromObject(object1);
    for (NSString *propertyName in propertyNames) {
        if (([object1 valueForKey:propertyName] != [object2 valueForKey:propertyName])
            && (![[object1 valueForKey:propertyName] isEqual:[object2 valueForKey:propertyName]])) return NO;
    }

    return YES;
}

NSUInteger MagicHash(id object)
{
    NSUInteger prime = 31;
    NSUInteger result = 1;

    NSArray *propertyNames = PropertyNamesFromObject(object);

    for (NSString *propertyName in propertyNames) {
        id value = [object valueForKey:propertyName];
        result = prime * result + [value hash];
    }

    return result;
}

これで、カスタムクラスで次のことを簡単に実装できisEqual:ますhash。

- (NSUInteger)hash
{
    return MagicHash(self);
}

- (BOOL)isEqual:(id)other
{
    return IsEqualObjects(self, other);
}

score 2 · Accepted Answer

作成後に変更できるオブジェクトを作成している場合、オブジェクトがコレクションに挿入されている場合は、ハッシュ値を変更してはならないことに注意してください。実際には、これは、最初のオブジェクト作成の時点からハッシュ値を固定する必要があることを意味します。詳細については、NSObjectプロトコルの-hashメソッドに関するAppleのドキュメントを参照してください。

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

これは、ハッシュルックアップの効率を大幅に低下させる可能性があるため、私には完全な奇抜なように聞こえますが、注意を怠ってドキュメントの内容に従う方がよいと思います。

score 1 · Accepted Answer

ここで完全なボフィンを鳴らす危険がある場合は申し訳ありませんが... ...「ベストプラクティス」に従うために、ターゲットオブジェクトが所有するすべてのデータを考慮しないequalsメソッドを絶対に指定しないでください。 equals を実装するときは、データがオブジェクトに集約されるのに対して、その関連付けを考慮する必要があります。比較で「年齢」などを考慮したくない場合は、コンパレータを作成し、isEqual: の代わりにそれを使用して比較を実行する必要があります。

等値比較を任意に実行する isEqual: メソッドを定義すると、等値解釈の「ひねり」を忘れてしまうと、このメソッドが別の開発者や自分自身によって悪用されるリスクが生じます。

エルゴ、これはハッシュに関するすばらしい質問ですが、通常はハッシュ方法を再定義する必要はありません。代わりにアドホックコンパレータを定義する必要があります。

objective-c - isEqual: および hash をオーバーライドするためのベスト プラクティス

16 に答える 16

説明と帰属

Related

Reference

objective-c - isEqual: および hash をオーバーライドするためのベストプラクティス