NSDictionary是基于key - value 方式林说，把key映射到一個(gè)hash表中實(shí)現(xiàn)的
key
需要支持NSCopying協(xié)議禀崖，實(shí)際上不支持也可以作為key鞋吉，但在swift中就必須要支持捷兰，支持NSCopying的原因在于农渊，NSDicitionary是NSCopying的泻红，在copy一個(gè)dictionary的時(shí)候需要key是NSCopying的（不信你用一個(gè)UIImage做key也是可以正常運(yùn)行的夭禽，只要不copy）
添加key-value的時(shí)候不會(huì)對(duì)key做深復(fù)制，以下代碼打印的內(nèi)容是一樣的
NSString *key = @"key";
NSLog(@"%p",key);
NSDictionary *dic = @{key:@(1)};
NSLog(@"%p",dic.allKeys.firstObject);
所以添加非NSCopying的對(duì)象也是可以的谊路，因?yàn)閷?duì)象作為key的必要條件是對(duì)象實(shí)現(xiàn)了：
- (NSUInteger)hash;
2018.8.3更新
上面這個(gè)說(shuō)法僅限于創(chuàng)建NSDictionary的時(shí)候,如果是在NSMutableDictionary調(diào)用setObject方法,系統(tǒng)會(huì)強(qiáng)制復(fù)制一份,也就是會(huì)調(diào)用key的copyWithZone方法創(chuàng)建一個(gè)新的對(duì)象,setObject的key沒支持NSCopying的話就會(huì)崩,同理setValue的key也需要支持NSCopying
方法讹躯，而NSObject本身就已經(jīng)實(shí)現(xiàn)了這個(gè)方法，返回的是它本身的地址
如果你這樣打印：
NSObject *obj = NSObject.new;
NSLog(@"%@",obj.hash);
你會(huì)發(fā)現(xiàn)打印出來(lái)的內(nèi)容跟
NSLog(@"%@",obj);
是一樣的蜀撑，就側(cè)面證明了NSObject的默認(rèn)-hash打印的就是它本身的地址
而如果這樣打印一個(gè)NSString的話會(huì)直接崩掉挤巡。。酷麦。說(shuō)明NSString改寫了hash方法返回了基于string計(jì)算的hash矿卑，所以只要你傳入了內(nèi)容一樣的字符串都能拿到相應(yīng)的value
并且NSString是經(jīng)過特別優(yōu)化的，會(huì)經(jīng)可能的均勻hash的平均長(zhǎng)度沃饶，使hash表盡可能的小
如果你要通過key查找value母廷，需要key實(shí)現(xiàn)了：
- (BOOL)isEqual:(id)object;
同樣NSObject也實(shí)現(xiàn)了，默認(rèn)是通過對(duì)比自己的地址
value沒什么好講的糊肤，只要是個(gè)NSObject子類都行
hash表的實(shí)現(xiàn)
NSDictionary生成hash表使用的是拉鏈法琴昆，可以理解為“鏈表的數(shù)組”即：
根結(jié)構(gòu)為數(shù)組，每個(gè)元素為鏈表
添加key的時(shí)候馆揉，會(huì)把key的hash對(duì)根結(jié)構(gòu)的長(zhǎng)度取余业舍，結(jié)果作為根結(jié)構(gòu)的下標(biāo)，再把key插入到下標(biāo)對(duì)應(yīng)的鏈表元素中
一般不會(huì)在這個(gè)時(shí)候排序插入升酣，而是直接插在鏈表頭部以提高性能舷暮，當(dāng)鏈表元素過多時(shí)才排序轉(zhuǎn)換成平衡二叉樹（該處理來(lái)自http://ios.jobbole.com/87716/，里面提到NSDictionary和java的HashMap實(shí)現(xiàn)類似噩茄，而HashMap是轉(zhuǎn)換成紅黑樹）
解決hash沖突
hash沖突即存在多個(gè)hash一樣的key
一般來(lái)說(shuō)拉鏈法需要涉及到解決hash沖突下面，但巧就巧在，ObjC中一般對(duì)象的hash就是它本身的地址绩聘，所以幾乎是不可能沖突的沥割，對(duì)于NSString這類重寫了hash方法的，會(huì)同時(shí)要求重寫isEqual方法凿菩。當(dāng)真的遇到hash沖突的話机杜，NSDictionary插入時(shí)會(huì)無(wú)視沖突，而在取數(shù)據(jù)時(shí)衅谷，在找到hash后會(huì)多一步通過isEqual對(duì)比是不是需要的key叉庐，如果不是就繼續(xù)往下找，一般來(lái)說(shuō)出現(xiàn)hash沖突的key都會(huì)在同一個(gè)鏈表的相鄰位置会喝，所以查找的消耗會(huì)非常的低
同時(shí)NSHashTable陡叠，NSSet，NSMapTable的實(shí)現(xiàn)都是基于拉鏈法生成的hash表
