1

このコードをデバッガーで実行し、後で停止します (私は Xcode 5.0.1 の iOS 7 シミュレーターを使用しています)。

NSString *nsStr = @"/Users/123456789012/Library/Application Support/iPhone Simulator/7.0/Applications/94F31827-6DAD-4BD5-AC91-B215176265E1/Documents/libraries/shared/17517_abPub/OEBPS/indexes/Index.sqlite";
NSString *nsStr2 = @"/Users/123456789012/Library/Application Support/iPhone Simulator/7.0/Applications/94F31827-6DAD-4BD5-AC91-B215176265E1/Documents/libraries/shared/16583_abPub/OEBPS/indexes/Index.sqlite";
NSUInteger form1 = [nsStr hash];
NSUInteger form2 = [nsStr2 hash];

NSMutableDictionary *dict = [[[NSMutableDictionary alloc]init]autorelease];
[dict setObject:@"foo" forKey:nsStr];

id foobar = [dict objectForKey:nsStr2];

form1とform2は同じであることに注意してください。ハッシュ衝突があります。であることにも注意してfoobarくださいnil。ハッシュの衝突は発生しませんNSDictionary。どうしてこれなの？Appleが辞書でハッシュ衝突を乗り切るために何をしているのか、またはこれに対するいくつかの良い戦略は何かを知っている人はいますか?

編集: 参考までに、NSString ハッシュの詳細を次に示します。どうやら、このメソッドは最初、中間、および最後の 32 文字しか見ていないようです。文字列内の他のものは問題ではありません。

4

1 に答える 1

7

hash値は一意ではありません。多くの異なる値が同じハッシュ値を持つことができます。ディクショナリの実装はこれを認識しています。ハッシュの使用は、単にルックアップを最適化する方法です。しかし、重要なのはハッシュ値ではなく、実際のキー値です。

YESに戻る2 つのオブジェクトisEqual:も同じである限り、hash問題はありません。

辞書は一連のバケットと考えてください。ハッシュは、値が入っているバケットを決定します。バケットがわかった後も、正確なキーを探す必要があります。

于 2013-10-09T20:16:55.230 に答える