iOS 字典的實(shí)現(xiàn)原理

一、NSDictionary使用原理

1.NSDictionary（字典）是使用hash表來(lái)實(shí)現(xiàn)key和value之間的映射和存儲(chǔ)的，hash函數(shù)設(shè)計(jì)的好壞影響著數(shù)據(jù)的查找訪問(wèn)效率。
-(void)setObject:(id)anObject forKey:(id)aKey;

2.Objective-C中的字典N(xiāo)SDictionary底層其實(shí)是一個(gè)哈希表，實(shí)際上絕大多數(shù)語(yǔ)言中字典都通過(guò)哈希表實(shí)現(xiàn).

二、哈希的原理

1.根據(jù)key計(jì)算出它的哈希值h。

2.假設(shè)箱子的個(gè)數(shù)為n，那么這個(gè)鍵值對(duì)應(yīng)該放在第(h % n)個(gè)箱子中。

3.如果該箱子中已經(jīng)有了鍵值對(duì)，就使用開(kāi)放尋址法或者拉鏈法解決沖突。
在使用拉鏈法解決哈希沖突時(shí)，每個(gè)箱子其實(shí)是一個(gè)鏈表，屬于同一個(gè)箱子的所有鍵值對(duì)都會(huì)排列在鏈表中。

哈希表還有一個(gè)重要的屬性:負(fù)載因子(load factor)，它用來(lái)衡量哈希表的空/滿(mǎn)程度，一定程度上也可以體現(xiàn)查詢(xún)的效率，計(jì)算公式為:
負(fù)載因子=總鍵值對(duì)數(shù)/箱子個(gè)數(shù)
負(fù)載因子越大，意味著哈希表越滿(mǎn)，越容易導(dǎo)致沖突，性能也就越低。因此，一般來(lái)說(shuō)，當(dāng)負(fù)載因子大于某個(gè)常數(shù)(可能是1，或者0.75等)時(shí)，哈希表將自動(dòng)擴(kuò)容。

重哈希概念:

哈希表在自動(dòng)擴(kuò)容時(shí)，一般會(huì)創(chuàng)建兩倍于原來(lái)個(gè)數(shù)的箱子，因此即使key的哈希值不變，對(duì)箱子個(gè)數(shù)取余的結(jié)果也會(huì)發(fā)生改變，因此所有鍵值對(duì)的存放位置都有可能發(fā)生改變，這個(gè)過(guò)程也稱(chēng)為重哈希(rehash)。

哈希表的擴(kuò)容并不總是能夠有效解決負(fù)載因子過(guò)大的問(wèn)題。假設(shè)所有key的哈希值都一樣，那么即使擴(kuò)容以后他們的位置也不會(huì)變化。雖然負(fù)載因子會(huì)降低，但實(shí)際存儲(chǔ)在每個(gè)箱子中的鏈表長(zhǎng)度并不發(fā)生改變，因此也就不能提高哈希表的查詢(xún)性能。

四、總結(jié)，細(xì)心的讀者可能會(huì)發(fā)現(xiàn)哈希表的兩個(gè)問(wèn)題:

1.如果哈希表中本來(lái)箱子就比較多，擴(kuò)容時(shí)需要重新哈希并移動(dòng)數(shù)據(jù)，性能影響較大。

2.如果哈希函數(shù)設(shè)計(jì)不合理，哈希表在極端情況下會(huì)變成線性表，性能極低。

關(guān)于hash表

想想一下，我們有一個(gè)數(shù)組，數(shù)組長(zhǎng)度是100個(gè)，現(xiàn)在的需求是：給出這個(gè)數(shù)組是否包含一個(gè)對(duì)象obj？

如果這是個(gè)無(wú)序的數(shù)組，那么我們只能用遍歷的方法來(lái)查找是否包含這個(gè)對(duì)象obj了。這是我們的時(shí)間復(fù)雜度就是O(n)。

這種查找效率是很低的，所以hash表應(yīng)運(yùn)而生。

hash表其實(shí)也是一個(gè)數(shù)組，區(qū)別數(shù)組的地方是它會(huì)建立 存儲(chǔ)的值 到 存儲(chǔ)的下標(biāo) 索引的一個(gè)映射，也就是散列函數(shù)。

我們來(lái)舉一個(gè)通俗易懂的例子：

現(xiàn)在我們有個(gè)hash表，表長(zhǎng)度count = 16，現(xiàn)在我們依次把3，12，24，30依次存入hash表中。

首先我們來(lái)約定一個(gè)簡(jiǎn)單的映射關(guān)系：存儲(chǔ)的索引下表(index) = 存儲(chǔ)值(value) % hash表長(zhǎng)度(count)；

[注：實(shí)際的映射并不是簡(jiǎn)單的存儲(chǔ)值，而是經(jīng)過(guò)計(jì)算得到的hash值]

算下來(lái)hash表的存儲(chǔ)分布是這樣的：hash[3] = 3、hash[12] = 12、hash[8] = 24、hash[14] = 30

還是一樣的需求，當(dāng)我們給出24的時(shí)候，求出hash表中是否存有24？

此時(shí)，按照原先約定的映射關(guān)系：index = 24 % 16 = 8，然后我們?cè)趆ash[8]查詢(xún)等于24。這樣，通過(guò)數(shù)組需要O(n)的時(shí)間復(fù)雜度，通過(guò)hash表只需要O(1)；

散列碰撞

上面提到的hash表在存入3，12，24，30后，如果要面臨存入19呢？

此時(shí)index = 19 % 16 = 3，而之前hash[3] 已經(jīng)存入了3這個(gè)值了！這種情況就是發(fā)送了散列碰撞。

此時(shí)，我們可以改進(jìn)一下我們的hash表，讓它存儲(chǔ)的是一個(gè)鏈表。這樣發(fā)送散列碰撞的元素就可以以鏈表的形式共處在hash表的某一個(gè)下標(biāo)位置了。

hash存儲(chǔ)

所以，只要發(fā)生了散列碰撞，我們查找的時(shí)間復(fù)雜度就不能像O(1)這么小了，因?yàn)檫€要考慮鏈表的查找時(shí)間復(fù)雜度O(n)。

負(fù)載因子、自動(dòng)擴(kuò)容

哈希表還有一個(gè)重要的屬性: 負(fù)載因子(load factor)，它用來(lái)衡量哈希表的 空/滿(mǎn) 程度

負(fù)載因子 = 總鍵值對(duì)數(shù) / 箱子個(gè)數(shù)

當(dāng)存儲(chǔ)的元素個(gè)數(shù)越來(lái)越多，在hash表長(zhǎng)度不變的前提下，發(fā)生散列碰撞的概率就會(huì)變大，查找性能就變低了。所以當(dāng)負(fù)載因子達(dá)到一定的值，hash表會(huì)進(jìn)行自動(dòng)擴(kuò)容。

哈希表在自動(dòng)擴(kuò)容時(shí)，一般會(huì)擴(kuò)容出一倍的長(zhǎng)度。元素的hash值不變，對(duì)哈希表長(zhǎng)度取模的值也會(huì)改變，所以元素的存儲(chǔ)位置也要相對(duì)應(yīng)重新計(jì)算，這個(gè)過(guò)程也稱(chēng)為重哈希(rehash)。

哈希表的擴(kuò)容并不總是能夠有效解決負(fù)載因子過(guò)大而引起的查詢(xún)性能變低的問(wèn)題。假設(shè)所有 key 的哈希值都一樣，那么即使擴(kuò)容以后他們的位置也不會(huì)變化。雖然負(fù)載因子會(huì)降低，但實(shí)際存儲(chǔ)在每個(gè)箱子中的鏈表長(zhǎng)度并不發(fā)生改變，因此也就不能提高哈希表的查詢(xún)性能。所以，設(shè)計(jì)一個(gè)合理有效的散列函數(shù)顯得相當(dāng)?shù)挠斜匾?，這個(gè)合理有效應(yīng)該體現(xiàn)在映射之后各元素均勻的分布在hash表當(dāng)中。

說(shuō)回NSDictionary

字典是開(kāi)發(fā)中最常見(jiàn)的集合了。當(dāng)我們調(diào)用

- (void)setObject:(ObjectType)anObject forKey:(KeyType <NSCopying>)aKey;

我們來(lái)探究下字典存儲(chǔ)鍵值對(duì)的過(guò)程，有兩個(gè)方法對(duì)hash存儲(chǔ)起著關(guān)鍵的影響：

- (NSUInteger)hash;
- (BOOL)isEqual:(id)object;

demo1

@interface KeyType : NSObject<NSCopying>

@property (nonatomic, copy) NSString *keyName;

- (instancetype)initWithKeyName:(NSString *)keyName;

@end

@implementation KeyType

- (instancetype)initWithKeyName:(NSString *)keyName {
    if (self = [super init]) {
       _keyName  = keyName;
    }
    return self;
}

//直接電影父類(lèi)hash方法
- (NSUInteger)hash {
    NSLog(@"hash func");
    return [super hash];
}

//直接調(diào)用父類(lèi)isEqual方法
- (BOOL)isEqual:(id)object {
    NSLog(@"isEqual func");
    return [super isEqual:object];
}

- (nonnull id)copyWithZone:(nullable NSZone *)zone {
    NSLog(@"copy funcr");
    KeyType *key = [[KeyType alloc] initWithKeyName:self.keyName];
    return key;
}

@end

@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];
    
    NSMutableDictionary *dic = [NSMutableDictionary new];
    KeyType *key1 = [[KeyType alloc] initWithKeyName:@"key1"];
    
    NSLog(@"for value");
    NSLog(@"%@",[key1 valueForKey:@"retainCount"]);
    [dic setObject:key1 forKey:@"valueKey"];
    NSLog(@"%@",[key1 valueForKey:@"retainCount"]);
    
    NSLog(@"for key");
    [dic setObject:@"object1" forKey:key1];
    NSLog(@"%@",[key1 valueForKey:@"retainCount"]);
}

@end

控制臺(tái)打?。?for value
1
2
for key
hash func
copy func
2

分析：

  • key1作為鍵值對(duì)的value時(shí)，不會(huì)去計(jì)算hash值，dictionary會(huì)對(duì)key1進(jìn)行一次強(qiáng)引用。
  • key1作為鍵值對(duì)的key時(shí)，會(huì)先去計(jì)算hash值，然后[key1 copy]拷貝一份key1和value存儲(chǔ)在字典中
    下面來(lái)看第二個(gè)測(cè)試用例：Demo2
- (void)viewDidLoad {
    [super viewDidLoad];
    
    NSMutableDictionary *dic = [NSMutableDictionary new];
    KeyType *key1 = [[KeyType alloc] initWithKeyName:@"key1"];
    [dic setObject:@"object1" forKey:key1];
    NSLog(@"%ld",dic.count);
    NSLog(@"%@",dic[key1]);
}
控制臺(tái)打?。?hash func
copy func
1
hash func
isEqual func
(null)

dic.count = 1，說(shuō)明{key1 : @"object1"}已經(jīng)存儲(chǔ)進(jìn)去了。然而通過(guò)這個(gè)key去獲取竟然返回null？

從打印也可以看出來(lái)，現(xiàn)在isEqual函數(shù)開(kāi)始被調(diào)用了。

分析：

  • dic[key1]作為key去字典中查詢(xún)value時(shí)，也會(huì)先計(jì)算hash值，來(lái)確定在hash表中的存儲(chǔ)下標(biāo)位置

  • 因?yàn)榇鎯?chǔ)散列碰撞的可能，所以找到下標(biāo)后，會(huì)調(diào)用isEqual方法來(lái)匹配鏈表上面的各個(gè)元素之間的key值。當(dāng)isEqual:返回YES時(shí)，會(huì)把對(duì)應(yīng)的value返回。

  • 調(diào)用父類(lèi)的isEqual，NSObject的- (BOOL)isEqual:(id)object比較的是內(nèi)存地址

- (BOOL)isEqual:(id)object {
    return self == object;
}
  • 根據(jù)demo1的分析，key1作為鍵值對(duì)的key時(shí)，會(huì)拷貝一份存儲(chǔ)到字典中。既然是拷貝，那當(dāng)然和原始對(duì)象不是同一個(gè)對(duì)象，所以- (BOOL)isEqual:(id)object返回NO。所以我們?cè)阪湵淼牟樵?xún)中找不到對(duì)應(yīng)的key，最終返回null
//我們可以強(qiáng)制重寫(xiě)KeyType的isEqual:返回YES，demo2的返回值就不是null了
- (BOOL)isEqual:(id)object {
    return YES;
}

由此可見(jiàn)，當(dāng)一個(gè)類(lèi)需要作為字典的key，重寫(xiě)hash和isEqual:方法顯得很有必要。

重寫(xiě)hash方法

為什么要重寫(xiě)hash方法？

我們先來(lái)看看NSObject的hash方法返回什么：

KeyType *key1 = [[KeyType alloc] initWithKeyName:@"key1"];
NSLog(@"%p",key1);
NSLog(@"%lx",[key1 hash]);
控制臺(tái)打?。?0x600000640610
600000640610

由此可見(jiàn)，NSObject是把對(duì)象的內(nèi)存地址作為hash值返回。

以?xún)?nèi)存地址作為hash可以保證唯一性，但是這樣好不好？

這樣不好！

來(lái)看下這個(gè)場(chǎng)景：

@interface KeyType : NSObject<NSCopying>

@property (nonatomic, copy) NSString *keyName;

- (instancetype)initWithKeyName:(NSString *)keyName;

@end

@implementation KeyType

- (instancetype)initWithKeyName:(NSString *)keyName {
    if (self = [super init]) {
       _keyName  = keyName;
    }
    return self;
}

- (NSUInteger)hash {
    return [super hash];
}

//強(qiáng)制返回YES
- (BOOL)isEqual:(id)object {
    return YES;
}

- (nonnull id)copyWithZone:(nullable NSZone *)zone {
    KeyType *key = [[KeyType alloc] initWithKeyName:self.keyName];
    return key;
}

@end

@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];
    
    NSMutableDictionary *dic = [NSMutableDictionary new];
    KeyType *key1 = [[KeyType alloc] initWithKeyName:@"key1"];
    KeyType *key2 = [[KeyType alloc] initWithKeyName:@"key1"];
    [dic setObject:@"object1" forKey:key1];
    NSLog(@"%@",dic[key2]);
}

很明顯，最后打印是null。

但是在一般的業(yè)務(wù)場(chǎng)景，因?yàn)閗ey1和key2的keyName屬性都一樣，所以應(yīng)該被看為同一個(gè)key。

所以我們要重新hash方法。

如何重寫(xiě)hash方法

一個(gè)合理的hash方法要盡量讓hash表中的元素均勻分布，來(lái)保證較高的查詢(xún)性能。

如果兩個(gè)對(duì)象可以被視為同一個(gè)對(duì)象，那么他們的hash值要一樣。

mattt在文章Equality 中給出了一個(gè)普遍的算法:

- (NSUInteger)hash {
    return [self.property1 hash] ^ [self.property2 hash] ^ [self.property3 hash];
}
//假設(shè)對(duì)象有三個(gè)屬性，那么對(duì)這三個(gè)屬性分別算出hash值，然后進(jìn)行異或運(yùn)算

Instagram在開(kāi)源IGListKit的同時(shí)，鼓勵(lì)這么寫(xiě)hash方法：

- (NSUInteger)hash
{
  NSUInteger subhashes[] = {[self.property1 hash], [self.property2 hash], [self.property3 hash]};
  NSUInteger result = subhashes[0];
  for (int ii = 1; ii < 3; ++ii) {
    unsigned long long base = (((unsigned long long)result) << 32 | subhashes[ii]);
    base = (~base) + (base << 18);
    base ^= (base >> 31);
    base *=  21;
    base ^= (base >> 11);
    base += (base << 6);
    base ^= (base >> 22);
    result = base;
  }
  return result;
}

重寫(xiě)isEqual:

如何寫(xiě)一個(gè)合理高效的判等方法？

首先對(duì)內(nèi)存地址進(jìn)行判斷，地址相等return YES;
進(jìn)行判空處理，self == nil || object == nil ，return NO;
類(lèi)型判斷，![object isKindOfClass:[self class]] , return NO;
對(duì)對(duì)象的其他屬性進(jìn)行判斷
根據(jù)這四個(gè)步驟，我們可以發(fā)現(xiàn)，我們都是先判斷時(shí)間開(kāi)銷(xiāo)最少的屬性。所以對(duì)于第4個(gè)步驟，如果對(duì)象有很多屬性，我們也要依照這個(gè)原則來(lái)！比如[self.array isEqual:other.array] && self.intVal == other.intVal這種寫(xiě)法是不合理的，因?yàn)閍rray的判等會(huì)去遍歷元素，時(shí)間開(kāi)銷(xiāo)大。如果intVal不相等的話就可以直接return NO了，沒(méi)必要進(jìn)行數(shù)組的判等。應(yīng)該這么寫(xiě)： self.intVal == other.intVal && [self.array isEqual:other.array]

示例如下：

- (BOOL)isEqual:(PersonModel *)object
{
  if (self == object) {
    return YES;
  } else if (self == nil || object == nil || ![object isKindOfClass:[self class]]) {
    return NO;
  }
  return
    (_property1 == object->_property1 ? YES : [_property1 isEqual:object->_property1]) &&
    (_property2 == object->_property2 ? YES : [_property2 isEqual:object->_property2]) &&
    (_property3 == object->_property3 ? YES : [_property3 isEqual:object->_property3]);
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容