13

異なる辞書に対して同じハッシュ値を取得するという問題に遭遇しました。明らかに間違ったことをしているのかもしれませんが、コンテンツが異なるオブジェクト (別名、等しくないオブジェクト) は異なるハッシュ値を持つべきだと思いました。

NSDictionary *dictA = @{ @"foo" : @YES };
NSDictionary *dictB = @{ @"foo" : @NO };

BOOL equal = [dictA hash] == [dictB hash];

NSAssert(!equal, @"Assuming, that different dictionaries have different hash values.");

何かご意見は？

4

5 に答える 5

25

2 つの異なるオブジェクトが異なるハッシュ値を持つという保証はありません。

CoreFoundationの最新のオープンソース バージョンでは、CFDictionary (NSDictionary と同等) のハッシュは次のように定義されます。

static CFHashCode __CFDictionaryHash(CFTypeRef cf) {
    return __CFBasicHashHash((CFBasicHashRef)cf);
}

であり、__CFBasicHashHash次のように定義されます。

__private_extern__ CFHashCode __CFBasicHashHash(CFTypeRef cf) {
    CFBasicHashRef ht = (CFBasicHashRef)cf;
    return CFBasicHashGetCount(ht);
}

これは単にコレクションに格納されているエントリの数です。つまり、[dictA hash]との両方[dictB hash]のハッシュ値は、辞書のエントリ数である1です。

これは非常に悪いハッシュ アルゴリズムですが、CF はここで何も悪いことをしていません。より正確なハッシュ値が必要な場合は、Obj-C カテゴリで自分で提供できます。

于 2012-08-16T09:49:42.657 に答える
1

順序に依存しないigor-kulaginの回答に基づくソリューション:

@implementation NSDictionary (Extensions)

- (NSUInteger) hash
{
    NSUInteger prime = 31;
    NSUInteger result = 1;
    for (NSObject *key in [[self allKeys] sortedArrayUsingSelector:@selector(compare:)]) {
        result = prime * result + [key hash];
        result = prime * result + [self[key] hash];
    }
    return result;
}
@end

ただし、ディクショナリに他のディクショナリが値として含まれている場合は、衝突が発生する可能性があります。

于 2014-05-20T13:35:45.913 に答える
1

関数「ハッシュ」は実際のハッシュ関数ではありません。文字列（すべて予測可能）には異なる値を与えますが、コレクション（配列と辞書）の場合はカウントを返すだけです。一意のハッシュが必要な場合は、素数、関数 srandom() および random() を使用して自分で計算するか、CommonCrypto/CommonDigest.h で利用可能な SHA1 のような実際のハッシュ関数を調べることができます。

于 2014-09-08T21:08:33.043 に答える
-2

この回答に基づいて、NSDictionaryカテゴリとオーバーライドされたハッシュメソッドを作成しました: isEqual: とハッシュをオーバーライドするためのベスト プラクティス

@implementation NSDictionary (Extensions)

- (NSUInteger) hash {
    NSUInteger prime = 31;
    NSUInteger result = 1;

    NSArray *sortedKeys = [self.allKeys sortedArrayUsingSelector: @selector(compare:)];
    for (NSObject *key in sortedKeys) {
        result = prime * result + key.hash;
        id value = self[key];
        if ([value conformsToProtocol: @protocol(NSObject)] == YES) {
            result = prime * result + [value hash];
        }
    }

    return result;
}

@end

そしてSwift実装。

extension Dictionary where Key: Comparable, Value: Hashable {
    public var hashValue: Int {
        let prime = 31
        var result = 1

        let sortedKeys = self.keys.sorted()
        for (key) in sortedKeys {
            let value = self[key]!
            result = Int.addWithOverflow(Int.multiplyWithOverflow(prime, result).0, key.hashValue).0
            result = Int.addWithOverflow(Int.multiplyWithOverflow(prime, result).0, value.hashValue).0
        }

        return result
    }
}

完全にこれにはEquatableプロトコルの実装も必要なので、プロトコルの適合Dictionary性を追加することもできます。Hashable

于 2013-09-19T17:24:15.460 に答える