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

不能保证两个不同的对象会有不同的哈希值。

在最新的 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 回答
4

使用只有整数、字符串等的字典。我将dict.description.hash用作快速代码。

于 2015-05-07T05:35:09.643 回答
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 回答