NSDictionary介紹
NSDictionary（字典）是使用 hash表來(lái)實(shí)現(xiàn)key和value之間的映射和存儲(chǔ)的挠羔， hash函數(shù)設(shè)計(jì)的好壞影響著數(shù)據(jù)的查找訪問(wèn)效率。數(shù)據(jù)在hash表中分布的越均勻案淋，其訪問(wèn)效率越高矢腻。而在Objective-C中煌张，通常都是利用NSString 來(lái)作為鍵值早歇，其內(nèi)部使用的hash函數(shù)也是通過(guò)使用 NSString對(duì)象作為鍵值來(lái)保證數(shù)據(jù)的各個(gè)節(jié)點(diǎn)在hash表中均勻分布。
NSDictionary內(nèi)部結(jié)構(gòu)
參考cocotron的源代碼憔涉，NSDictionary是使用NSMapTable來(lái)實(shí)現(xiàn)订框。
NSMapTable同樣是一個(gè)key－value的容器，下面是NSMapTable的部分代碼：
typedef struct {
NSMapTable *table;
NSInteger i;
struct _NSMapNode *j;
} NSMapEnumerator;
上述結(jié)構(gòu)體描述了遍歷一個(gè)NSMapTable時(shí)的一個(gè)指針對(duì)象兜叨，其中包含table對(duì)象自身的指針穿扳，計(jì)數(shù)值衩侥，和節(jié)點(diǎn)指針。
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;
上述結(jié)構(gòu)體中存放的是幾個(gè)函數(shù)指針矛物，用于計(jì)算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;
上述存放的三個(gè)函數(shù)指針，定義在對(duì)nsmaptable插入一對(duì)key－value時(shí)忆首，對(duì)value對(duì)象的操作骨杂。
struct NSMapTable {
NSMapTableKeyCallBacks *keyCallBacks;
NSMapTableValueCallBacks *valueCallBacks;
NSUInteger count;
NSUInteger nBuckets;
NSMapNode **buckets;
};
可以看出來(lái)NSMapTable是一個(gè)哈希＋鏈表的數(shù)據(jù)結(jié)構(gòu)，因此在NSMapTable中插入或者刪除一對(duì)對(duì)象時(shí)雄卷， 尋找的時(shí)間是O(1)＋O(m)，m最壞時(shí)可能為n蛤售。
- O(1)：為對(duì)key進(jìn)行hash得到bucket的位置
- O(m)：遍歷該bucket后面沖突的value丁鹉，通過(guò)鏈表連接起來(lái)。
因此NSDictionary中的Key-Value遍歷時(shí)是無(wú)序的悴能，至如按照什么樣的順序揣钦，跟hash函數(shù)相關(guān)。NSMapTable使用NSObject的哈希函數(shù)漠酿。
-(NSUInteger)hash {
return (NSUInteger)self>>4;
}
上述是NSObject的哈希值的計(jì)算方式冯凹，簡(jiǎn)單通過(guò)移位實(shí)現(xiàn)。右移4位炒嘲，左邊補(bǔ)0宇姚。因?yàn)閷?duì)象大多存于堆中，地址相差4位應(yīng)該很正常夫凸。
NSDictionary的KVC實(shí)現(xiàn)
@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:是NSMutableDictionary特有的浑劳；setValue: ForKey:是KVC的主要方法。
(1)
setValue: ForKey:的value是可以為nil的（但是當(dāng)value為nil的時(shí)候夭拌，會(huì)自動(dòng)調(diào)用removeObject：forKey方法）魔熏；setObject: ForKey:的value則不可以為nil。
(2)setValue: ForKey:的key必須是不為nil的字符串類(lèi)型鸽扁；
setObject: ForKey:的key可以是不為nil的所有繼承NSCopying的類(lèi)型蒜绽。
NSDictionary copy key對(duì)象
NSDictionary 提供了 key -> object 的映射。從本質(zhì)上講桶现，NSDictionary 中存儲(chǔ)的 object 位置是由 key 來(lái)索引的躲雅。
由于對(duì)象存儲(chǔ)在特定位置，NSDictionary 中要求 key 的值不能改變（否則 object 的位置會(huì)錯(cuò)誤）巩那。為了保證這一點(diǎn)吏夯，NSDictionary 會(huì)始終copy key 到自己私有空間此蜈。而且object對(duì)象在其內(nèi)部是作為強(qiáng)引用(retain或strong);
這個(gè) key 的copy行為也是 NSDictionary 如何工作的基礎(chǔ)，但這也有一個(gè)限制：你只能使用 OC 對(duì)象作為 NSDictionary 的 key噪生，并且必須支持 NSCopying 協(xié)議裆赵。此外，key 應(yīng)該是小且高效的跺嗽，以至于復(fù)制的時(shí)候不會(huì)對(duì) CPU 和內(nèi)存造成負(fù)擔(dān)战授。
這意味著，NSDictionary 中真的只適合將值類(lèi)型的對(duì)象作為 key（如簡(jiǎn)短字符串和數(shù)字）桨嫁。并不適合自己的模型類(lèi)來(lái)做對(duì)象到對(duì)象的映射植兰。
參考：
NSDictionary 的內(nèi)部實(shí)現(xiàn)
NSDictionary底層實(shí)現(xiàn)原理
