自定义对象作为NSDictionary key的一些问题

hikui posted @ 2012年10月11日 16:49 in 未分类 , 10493 阅读

在Java中把一个自定义的类生成的对象作为HashTable的key是天生可行的,但是在Objective C中,NSDictionary的key使用的是copy方法,所以自定义的类必须要实现copyWithZone才可以。

假设现在有一个CustomClass:

@interface CustomClass : NSObject <NSCopying>

@property (strong) NSString *name;

@end

这个时候,如果不写copyWithZone,那么把它当作NSDictionary key时,就会报错。于是,需要实现copyWithZone方法:

- (id)copyWithZone:(NSZone *)zone
{
    id aCopy = [[[self class] alloc]init];
    if (aCopy) {
        [aCopy setName:[self.name copyWithZone:zone]];
    }
    return aCopy;
}

这样做之后,就可以当作key传到NSDictionary中去了。

但是这还没完,只实现了copyWithZone,只能保证放的进去,却没办法取出来。需要在CustomClass里面另外实现isEqual方法和hash方法才能保证取出来。

比如说我这里定义如果两个obj的name一样就算equal了:

//这是一个错误的设计
- (BOOL)isEqual:(id)object
{
    if ([object isKindOfClass:self.class] && [((CustomClass *)object).name isEqualToString:self.name]) {
        return YES;
    }
    return NO;
}

如果这个时候我不重写hash方法,那么用这样的Class生成的object作为key的时候就会出逻辑上的问题:

 

        CustomClass *a = [[CustomClass alloc]init];

        CustomClass *b = [[CustomClass alloc]init];

        a.name = @"a";

        b.name = @"a";

        NSMutableDictionary *dict = [[NSMutableDictionary alloc]init];

        [dict setObject:@"aaa" forKey:a];

        [dict setObject:@"bbb" forKey:b];

        NSLog(@"%@",[dict objectForKey:b]);

        NSLog(@"dict count: %ld",dict.count);

当两个对象的name是一样时,这个打印出来会是aaa,而且count是1。这是因为NSDictionary在找value的时候,是通过hash值和isEqual共同计算出来的。默认的hash算法会使得a和b返回的hash是一样,而isEqual又是一样的,那么a和b实际上就是相同的key了。

虽然不知道apple的NSDictionary具体是怎么工作的,但是通过GNUStep的源码可以知道,它的内部工作原理。它使用了如下的数据结构作为Map

 /*   This is the map                C - array of the buckets
 *   +---------------+             +---------------+
 *   | _GSIMapTable  |      /----->| nodeCount     |  
 *   |---------------|     /       | firstNode ----+--\  
 *   | buckets    ---+----/        | ..........    |  |
 *   | bucketCount  =| size of --> | nodeCount     |  |
 *   | nodeChunks ---+--\          | firstNode     |  |
 *   | chunkCount  =-+\ |          |     .         |  | 
 *   |   ....        || |          |     .         |  |
 *   +---------------+| |          | nodeCount     |  |
 *                    | |          | fistNode      |  | 
 *                    / |          +---------------+  | 
 *         ----------   v                             v
 *       /       +----------+      +---------------------------+ 
 *       |       |  * ------+----->| Node1 | Node2 | Node3 ... | a chunk
 *   chunkCount  |  * ------+--\   +---------------------------+
 *  is size of = |  .       |   \  +-------------------------------+
 *               |  .       |    ->| Node n | Node n + 1 | ...     | another
 *               +----------+      +-------------------------------+
 *               array pointing
 *               to the chunks
 */

key的hash方法返回的值被用来计算bucket所在的位置(通过mod计算),计算出bucket之后,就从node1开始遍历,直到[nodeX->key isEqual: key]为止,再取出nodeX->value。

  • 所以在重写isEqual和hash的时候,如果设计不当,会出现各种问题:
  • 首先按照苹果的文档,要保证两个obj如果isEqual为YES,那么两个obj的hash值必须一样。
  • 并且,因为NSDictionary会copy,所以要保证obj1 copy出来的obj2的hash和obj1必须一样,并且obj1 isEqual:obj2要为YES,否则能放不能取。
  • 并且,hash的算法最好不要依赖于object的内部变量,除非你能保证这个内部变量不变。

基于上述要求,我想到一个比较山寨的解决办法:

加入一个私有的@property (unsafe_unretained) NSUInteger myHash;

当init时,将myHash的值改为(NSUInteger)self;

在copyWithZone时,将拷贝出来的对象的myHash改成原先的myHash。

代码:

 

@interface CustomClass()

@property (unsafe_unretained) NSUInteger myHash;

@end

@implementation CustomClass

- (id)copyWithZone:(NSZone *)zone
{
    id aCopy = [[[self class] alloc]init];
    if (aCopy) {
        [aCopy setName:[self.name copyWithZone:zone]];
        [aCopy setMyHash:self.myHash];
    }
    return aCopy;
}
- (id)init
{
    if (self = [super init]) {
        _myHash = (NSUInteger)self;
    }
    return self;
}
- (NSUInteger)hash
{
    return _myHash;
}
- (BOOL)isEqual:(id)object
{
    return self.myHash == ((CustomClass *)object).myHash;
}
@end

 

 

創用 CC 授權條款
本著作係採用創用 CC 姓名標示 2.0 通用版 授權條款授權.

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter