NSDictionary是IOS中使用的一种key－value容器，参考cocotron的源代码，NSDictionary使用NSMapTable实现。
NSMapTable同样是一个key－value的容器，下面是NSMapTable的部分代码：
typedef struct {
NSMapTable *table;
NSInteger i;
struct _NSMapNode *j;
} NSMapEnumerator;
上述结构体描述了遍历一个NSMapTable时的一个指针对象，其中包含table对象自身的指针，计数值，和节点指针。
typedef struct {
NSUInteger (*hash)(NSMapTable *table,const void *);
BOOL (*isEqual)(NSMapTable *table,const void *,const void *);
void (*retain)(NSMapTable *table,const void *);
void (*release)(NSMapTable *table,void *);
NSString *(*describe)(NSMapTable *table,const void *);
const void *notAKeyMarker;
} NSMapTableKeyCallBacks;
上述结构体中存放的是几个函数指针，用于计算key的hash值，判断key是否相等，retain，release操作。
typedef struct {
void (*retain)(NSMapTable *table,const void *);
void (*release)(NSMapTable *table,void *);
NSString *(*describe)(NSMapTable *table, const void *);
} NSMapTableValueCallBacks;
上述存放的三个函数指针，定义在对nsmaptable插入一对key－value时，对value对象的操作。
@interface NSMapTable : NSObject {
NSMapTableKeyCallBacks *keyCallBacks;
NSMapTableValueCallBacks *valueCallBacks;
NSUInteger count;
NSUInteger nBuckets;
struct _NSMapNode **buckets;
}
上面是NSMtabtable真正的描述，可以看出来NSMapTable是一个哈希＋链表的数据结构，因此在NSMapTable中插入或者删除一对对象时
寻找的时间是O（1）＋O（m），m最坏时可能为n。
O（1）：为对key进行hash得到bucket的位置
O（m）：遍历该bucket后面冲突的value，通过链表连接起来。
因此：NSDictionary中的key Value遍历时是无序的，至如按照什么样的顺序，跟hash函数相关。NSMapTable使用NSObject的哈希函数。
-(NSUInteger)hash {
return (NSUInteger)self>>4;
}
上述是NSObject的哈希值的计算方式，简单通过移位实现。右移4位，左边补0.
因为对象大多存于堆中，地址相差4位应该很正常。
@implementation NSDictionary (NSKeyValueCoding)
-(id)valueForKey:(NSString*)key;
{
if([key hasPrefix:@"@"])
return [super valueForKey:[key substringFromIndex:1]];
return [self objectForKey:key];
}
-(void)setValue:(id)value forKey:(NSString*)key
{
[NSException raise:NSInvalidArgumentException format:@"%@ called on immutable dictionary %@", NSStringFromSelector(_cmd), self];
}
@end
@implementation NSMutableDictionary (NSKeyValueCoding)
-(void)setValue:(id)value forKey:(NSString*)key
{
if(value)
[self setObject:value forKey:key];
else
[self removeObjectForKey:key];
}
@end
使用setObject：ForKey时很可能因为value或者key为空导致crash，使用setValue：Forkey就不会。
网友评论