不知道大家有沒有思考過NSDictionary和NSArray內(nèi)部是怎么實(shí)現(xiàn)的旋炒，那么今天就深挖一下NSDictionary& NSArray的 內(nèi)部結(jié)構(gòu)尤泽。
首先咱們了解一下這幾個(gè)概念：哈希表歌逢、時(shí)間復(fù)雜度巾钉、鏈表
看了上面的文章，估計(jì)大家都懵逼了秘案。砰苍。潦匈。好吧，正文來了
NSDictionary
NSDictionary（字典）是使用 哈希表來實(shí)現(xiàn)key和value之間的映射和存儲的赚导， hash函數(shù)設(shè)計(jì)的好壞影響著數(shù)據(jù)的查找訪問效率茬缩。數(shù)據(jù)在hash表中分布的越均勻，其訪問效率越高吼旧。而在Objective-C中凰锡，通常都是利用NSString 來作為鍵值，其內(nèi)部使用的hash函數(shù)也是通過使用 NSString對象作為鍵值來保證數(shù)據(jù)的各個(gè)節(jié)點(diǎn)在hash表中均勻分布圈暗。
- (void)setObject:(id)anObject forKey:(id <NSCopying>)aKey;?
NSDictionary中的key是唯一的掂为，key可以是遵循NSCopying 協(xié)議和重載- (NSUInteger)hash;、- (BOOL)isEqual:(id)object;方法的任何對象员串。也就是說在NSDictionary內(nèi)部勇哗，會對 aKey 對象 copy 一份新的。而 anObject 對象在其內(nèi)部是作為強(qiáng)引用（retain或strong)昵济。
-
hash方法是用來計(jì)算該對象的 hash 值智绸，最終的 hash 值決定了該對象在 hash 表中存儲的位置。所以同樣访忿，如果想重寫該方法瞧栗，我們盡量設(shè)計(jì)一個(gè)能讓數(shù)據(jù)分布均勻的 hash 函數(shù)。 - ?
isEqual :方法是為了通過 hash 值來找到 對象 在hash ?表中的位置海铆。
在調(diào)用setObject: forKey: 后迹恐，內(nèi)部會去調(diào)用 ? key 對象的 hash 方法確定 object 在hash表內(nèi)的入口位置，然后會調(diào)用 isEqual : 來確定該值是否已經(jīng)存在于 NSDictionary中卧斟。
注：關(guān)于hash殴边，isEqual :可以看看這篇文章 iOS開發(fā) 之 不要告訴我你真的懂isEqual與hash!
其實(shí)，NSDictionary使用NSMapTable實(shí)現(xiàn)珍语。NSMapTable同樣是一個(gè)key－value的容器锤岸，下面是NSMapTable的部分代碼：
@interface NSMapTable : NSObject {
NSMapTableKeyCallBacks *keyCallBacks;
NSMapTableValueCallBacks *valueCallBacks;
NSUInteger count;
NSUInteger nBuckets;
struct _NSMapNode **buckets;
}
可以看出來NSMapTable是一個(gè)哈希＋鏈表的數(shù)據(jù)結(jié)構(gòu)，因此在NSMapTable中插入或者刪除一對對象時(shí)
尋找的時(shí)間是O（1）＋O（m）板乙，m最壞時(shí)可能為n是偷。
O（1）：為對key進(jìn)行hash得到bucket的位置
O（m）：遍歷該bucket后面沖突的value，通過鏈表連接起來募逞。
NSDictionary中的key Value遍歷時(shí)是無序的蛋铆，至如按照什么樣的順序，跟hash函數(shù)相關(guān)放接。NSMapTable使用NSObject的哈希函數(shù)刺啦。
-(NSUInteger)hash {
return (NSUInteger)self>>4;
}
上述是NSObject的哈希值的計(jì)算方式，簡單通過移位實(shí)現(xiàn)纠脾。右移4位玛瘸，左邊補(bǔ)0.
因?yàn)閷ο蟠蠖啻嬗诙阎型汕啵刂废嗖?位應(yīng)該很正常。
補(bǔ)充一個(gè)小知識：iOS setValue和setObject的區(qū)別：
- (void)setObject:(ObjectType)anObject forKey:(KeyType <NSCopying>)aKey;
- (void)setValue:(nullable ObjectType)value forKey:(NSString *)key;
首先：setObject: ForKey:是NSMutableDictionary特有的捧韵；setValue: ForKey:是KVC的主要方法市咆。
區(qū)別：
(1)
setValue: ForKey:的value是可以為nil的（但是當(dāng)value為nil的時(shí)候，會自動(dòng)調(diào)用removeObject：forKey方法）再来；
setObject: ForKey:的value則不可以為nil蒙兰。
(2)setValue: ForKey:的key必須是不為nil的字符串類型；
setObject: ForKey:的key可以是不為nil的所有繼承NSCopying的類型芒篷。
