原文鏈接: http://draveness.me/hashtable/

關(guān)注倉庫坟乾，及時獲得更新：iOS-Source-Code-Analyze
Follow: Draveness · Github

因?yàn)?ObjC 的 runtime 只能在 Mac OS 下才能編譯，所以文章中的代碼都是在 Mac OS，也就是 x86_64 架構(gòu)下運(yùn)行的，對于在 arm64 中運(yùn)行的代碼會特別說明。

寫在前面

文章會介紹上古時代 Objective-C 哈希表跷睦，也就是 NXHashTable ：

• NXHashTable 的實(shí)現(xiàn)
• NXHashTable 的性能分析
• NXHashTable 的作用

NXHashTable 的實(shí)現(xiàn)有著將近 30 年的歷史，不過仍然作為重要的底層數(shù)據(jù)結(jié)構(gòu)存儲整個應(yīng)用中的類肋演。

文中會涉及一些數(shù)據(jù)結(jié)構(gòu)方面的簡單知識抑诸，例如拉鏈法烂琴。

注意：文章中分析的不是 NSHashTable 而是 NXHashTable。

NXHashTable

NXHashTable 的實(shí)現(xiàn)位于 hashtable2.mm 文件蜕乡，我們先來看一下 NXHashTable 的結(jié)構(gòu)以及重要的接口：

typedef struct {
    const NXHashTablePrototype *prototype;
    unsigned count;
    unsigned nbBuckets;
    void *buckets;
    const void *info;
} NXHashTable;

對于結(jié)構(gòu)體中的 NXHashTablePrototype 屬性暫且不說奸绷，其中的 buckets 是真正用來存儲數(shù)據(jù)的數(shù)組。

NXHashTable *NXCreateHashTableFromZone (NXHashTablePrototype prototype, unsigned capacity, const void *info, void *z);
unsigned NXCountHashTable (NXHashTable *table);
int NXHashMember (NXHashTable *table, const void *data);
void *NXHashGet (NXHashTable *table, const void *data);
void *NXHashInsert (NXHashTable *table, const void *data);
void *NXHashRemove (NXHashTable *table, const void *data);

我們會以上面的這些方法作為切入點(diǎn)层玲，分析 NXHashTable 的實(shí)現(xiàn)号醉。

NXCreateHashTableFromZone

NXHashTable 使用 NXCreateHashTableFromZone 方法初始化：

NXHashTable *NXCreateHashTableFromZone (NXHashTablePrototype prototype, unsigned capacity, const void *info, void *z) {
    NXHashTable         *table;
    NXHashTablePrototype     *proto;

    table = ALLOCTABLE(z);
    if (! prototypes) bootstrap ();
    if (! prototype.hash) prototype.hash = NXPtrHash;
    if (! prototype.isEqual) prototype.isEqual = NXPtrIsEqual;
    if (! prototype.free) prototype.free = NXNoEffectFree;

    proto = (NXHashTablePrototype *)NXHashGet (prototypes, &prototype);
    if (! proto) {
        proto = (NXHashTablePrototype *) malloc(sizeof (NXHashTablePrototype));
        bcopy ((const char*)&prototype, (char*)proto, sizeof (NXHashTablePrototype));
        (void) NXHashInsert (prototypes, proto);
        proto = (NXHashTablePrototype *)NXHashGet (prototypes, &prototype);
    };
    table->prototype = proto;
    table->count = 0;
    table->info = info;
    table->nbBuckets = GOOD_CAPACITY(capacity);
    table->buckets = ALLOCBUCKETS(z, table->nbBuckets);
    return table;
}

在這個方法中，絕大多數(shù)代碼都是用來初始化 table->prototype 的辛块，我們先把這部分全部忽略畔派，分析一下簡略版本的實(shí)現(xiàn)。

NXHashTable *NXCreateHashTableFromZone (NXHashTablePrototype prototype, unsigned capacity, const void *info, void *z) {
    NXHashTable         *table;
    NXHashTablePrototype     *proto;

    table = ALLOCTABLE(z);
    
    ...

    table->count = 0;
    table->info = info;
    table->nbBuckets = GOOD_CAPACITY(capacity);
    table->buckets = ALLOCBUCKETS(z, table->nbBuckets);
    return table;
}

其中 ALLOCTABLE润绵、GOOD_CAPACITY 以及 ALLOCBUCKETS 都是用來輔助初始化的宏：

#define  ALLOCTABLE(z) ((NXHashTable *) malloc_zone_malloc ((malloc_zone_t *)z,sizeof (NXHashTable)))
#define GOOD_CAPACITY(c) (exp2m1u (log2u (c)+1))
#define ALLOCBUCKETS(z,nb) ((HashBucket *) malloc_zone_calloc ((malloc_zone_t *)z, nb, sizeof (HashBucket)))

ALLOCTABLE 和 ALLOCBUCKETS 只是調(diào)用了 malloc_zone_calloc 來初始化相應(yīng)的結(jié)構(gòu)體线椰，而 GOOD_CAPACITY 有一些特殊，我們來舉個例子說明：

c   binary  result
1   1       1 
2   10      3(0b11)
6   110     7(0b111)
100 1100100 127(0b111 1111)

c 表示傳入?yún)?shù)授药，binary 表示二進(jìn)制下的參數(shù)士嚎，而 result 就是 GOOD_CAPACITY 返回的結(jié)果。

每次返回當(dāng)前位數(shù)下的二進(jìn)制最大值悔叽。

獲得 table->nbBuckets 之后莱衩，再初始化 table->nbBuckets * sizeof (HashBucket) 大小的內(nèi)存空間。

NXHashTablePrototype

在繼續(xù)分析其它方法之前娇澎，我們需要先知道 NXHashTablePrototype 是什么：

typedef struct {
    uintptr_t (*hash)(const void *info, const void *data);
    int (*isEqual)(const void *info, const void *data1, const void *data2);
    void (*free)(const void *info, void *data);
    int style; /* reserved for future expansion; currently 0 */
} NXHashTablePrototype;

NXHashTablePrototype 中存儲了 hash笨蚁、isEqual 和 free 的函數(shù)指針（用于獲取數(shù)據(jù)的哈希、判斷兩個數(shù)據(jù)是否相等以及釋放數(shù)據(jù)）趟庄。

在 hashtable2.mm 文件中有一個宏 ISEQUAL 就是用了 NXHashTablePrototype 中的 isEqual 來判斷兩個數(shù)據(jù)是否相等：

#define ISEQUAL(table, data1, data2) ((data1 == data2) || (*table->prototype->isEqual)(table->info, data1, data2))

可以說括细，NXHashTablePrototype 中存儲了一些構(gòu)建哈希表必要的函數(shù)指針。

因?yàn)?NXHashTable 使用拉鏈法來實(shí)現(xiàn)哈希表戚啥，在存入表前對數(shù)據(jù)執(zhí)行 hash奋单，然后找到對應(yīng)的 buckets，如果與 buckets 中的數(shù)據(jù)相同（使用 isEqual 判斷）猫十，就替換原數(shù)據(jù)览濒，否則將數(shù)據(jù)添加到鏈表中。

HashBucket

在這里另一個需要注意的數(shù)據(jù)結(jié)構(gòu)就是 HashBucket：

typedef struct  {
    unsigned count;
    oneOrMany elements;
} HashBucket;

oneOrMany 是一個 union 結(jié)構(gòu)體：

typedef union {
    const void *one;
    const void **many;
} oneOrMany;

這么設(shè)計(jì)的主要原因是提升性能拖云。

如果 HashBucket 中只有一個元素贷笛，那么就直接訪問 one，否則訪問 many宙项，遍歷這個 many 列表乏苦。

NXCountHashTable

NXCountHashTable 方法應(yīng)該是我們要介紹的方法中的最簡單的一個，它會直接返回 NXHashTable 結(jié)構(gòu)體中的 count尤筐。

unsigned NXCountHashTable (NXHashTable *table) {
    return table->count;
}

NXHashMember

NXHashMember 的函數(shù)簽名雖然會返回 int汇荐，其實(shí)它是一個布爾值洞就，會判斷當(dāng)前的 NXHashTable 中是否包含傳入的數(shù)據(jù)：

int NXHashMember (NXHashTable *table, const void *data) {
    HashBucket  *bucket = BUCKETOF(table, data);
    unsigned    j = bucket->count;
    const void  **pairs;

    if (! j) return 0;
    if (j == 1) {
        return ISEQUAL(table, data, bucket->elements.one);
    };
    pairs = bucket->elements.many;
    while (j--) {
        if (ISEQUAL(table, data, *pairs)) return 1;
        pairs ++;
    };
    return 0;
}

使用 BUCKETOF 對 data 進(jìn)行 hash，將結(jié)果與哈希表的 buckets 數(shù)取模拢驾，返回 buckets 數(shù)組中對應(yīng)的 NXHashBucket奖磁。

#define BUCKETOF(table, data) (((HashBucket *)table->buckets)+((*table->prototype->hash)(table->info, data) % table->nbBuckets))

在獲取了 bucket 之后，根據(jù)其中元素個數(shù)的不同繁疤，選擇不同的分支：

if (! j) return 0;
if (j == 1) {
    return ISEQUAL(table, data, bucket->elements.one);
};
pairs = bucket->elements.many;
while (j--) {
    if (ISEQUAL(table, data, *pairs)) return 1;
    pairs ++;
};

• count == 0咖为，直接返回

• count == 1，使用 ISEQUAL 比較查找的數(shù)據(jù)與 bucket->elements.one

• count > 1稠腊，依次與 bucket->elements.many 中的值進(jìn)行比較

  你可能覺得到這里的時間復(fù)雜度比較糟糕躁染，然而這個列表并不會很長，具體會在 NXHashInsert 中解釋架忌。

NXHashGet

其實(shí)我一直覺得這個方法可能用處不是很大吞彤，尤其是在使用默認(rèn)的 NXHashTablePrototype 時，因?yàn)槟J(rèn)的 NXHashTablePrototype 中的 isEqual 函數(shù)指針只是比較兩個數(shù)據(jù)的指針是否相同叹放。

其最大作用就是查看當(dāng)前 data 是不是在表中饰恕。

如果當(dāng)前數(shù)據(jù)在表中，那么這個方法只會返回一個相同的指針井仰，沒有太多的意義埋嵌。

它的實(shí)現(xiàn)跟上面的 NXHashMember 區(qū)別并不大，這里就不過多介紹了：

void *NXHashGet (NXHashTable *table, const void *data) {
    HashBucket  *bucket = BUCKETOF(table, data);
    unsigned    j = bucket->count;
    const void  **pairs;

    if (! j) return NULL;
    if (j == 1) {
        return ISEQUAL(table, data, bucket->elements.one)
        ? (void *) bucket->elements.one : NULL;
    };
    pairs = bucket->elements.many;
    while (j--) {
        if (ISEQUAL(table, data, *pairs)) return (void *) *pairs;
        pairs ++;
    };
    return NULL;
}

NXHashInsert

NXHashInsert 是 NXHashTable 中比較重要的方法俱恶，其作用就是向表中插入數(shù)據(jù)：

void *NXHashInsert (NXHashTable *table, const void *data) {
    HashBucket *bucket = BUCKETOF(table, data);
    unsigned j = bucket->count;
    const void **pairs;
    const void **newt;

    if (! j) {
        bucket->count++;
        bucket->elements.one = data;
        table->count++;
        return NULL;
    };
    if (j == 1) {
        if (ISEQUAL(table, data, bucket->elements.one)) {
            const void *old = bucket->elements.one;
            bucket->elements.one = data;
            return (void *) old;
        };
        newt = ALLOCPAIRS(z, 2);
        newt[1] = bucket->elements.one;
        *newt = data;
        bucket->count++;
        bucket->elements.many = newt;
        table->count++;
        if (table->count > table->nbBuckets) _NXHashRehash (table);
        return NULL;
    };
    pairs = bucket->elements.many;
    while (j--) {
        if (ISEQUAL(table, data, *pairs)) {
            const void  *old = *pairs;
            *pairs = data;
            return (void *) old;
        };
        pairs ++;
    };
    newt = ALLOCPAIRS(z, bucket->count+1);
    if (bucket->count) bcopy ((const char*)bucket->elements.many, (char*)(newt+1), bucket->count * PTRSIZE);
    *newt = data;
    FREEPAIRS (bucket->elements.many);
    bucket->count++; 
    bucket->elements.many = newt;
    table->count++;
    if (table->count > table->nbBuckets) _NXHashRehash (table);
    return NULL;
}

雖然這里的實(shí)現(xiàn)比上面的兩個方法復(fù)雜得多雹嗦，但是脈絡(luò)仍然很清晰，我們將插入的過程分為三種情況：

• bucket->count == 0
• bucket->count == 1
• bucket->count > 1

如果對應(yīng)的 bucket 為空：

if (! j) {
    bucket->count++; 
    bucket->elements.one = data;
    table->count++;
    return NULL;
};

將數(shù)據(jù)直接填入 bucket合是，增加 bucket 中元素的數(shù)目了罪，以及 table 中存儲的元素的數(shù)目：

objc-hashtable-insert-empty

如果原來的 buckets 中有一個元素，它會替換或者使用 many 替換原來的 one：

if (j == 1) {
    if (ISEQUAL(table, data, bucket->elements.one)) {
        const void  *old = bucket->elements.one;
        bucket->elements.one = data;
        return (void *) old;
    };
    newt = ALLOCPAIRS(z, 2);
    newt[1] = bucket->elements.one;
    *newt = data;
    bucket->count++;
    bucket->elements.many = newt;
    table->count++;
    
    ...

    return NULL;
};

當(dāng)前數(shù)據(jù) data 如果與 bucket 中存儲的數(shù)據(jù)相同聪全，就會更新這個數(shù)據(jù)泊藕，否則就會使用 ALLOCPAIRS 初始化一個新的數(shù)組，然后將 data 和原來的數(shù)據(jù)傳入难礼。

objc-hashtable-insert-one.gif

但是如果原來的 bucket 中存儲的元素大于 1吱七，那么會在鏈表的頭部追加一個新的元素：

while (j--) {
    if (ISEQUAL(table, data, *pairs)) {
        const void  *old = *pairs;
        *pairs = data;
        return (void *) old;
    };
    pairs ++;
};
newt = ALLOCPAIRS(z, bucket->count+1);
if (bucket->count) bcopy ((const char*)bucket->elements.many, (char*)(newt+1), bucket->count * PTRSIZE);
*newt = data;
FREEPAIRS (bucket->elements.many);
bucket->count++;
bucket->elements.many = newt;
table->count++;

上面的代碼使用 bcopy 將原鏈表中元素拷貝到新的數(shù)組 newt 中。

objc-hashtable-insert-many.gif

在每次添加完一個元素之后鹤竭，都會進(jìn)行下面的判斷：

if (table->count > table->nbBuckets) _NXHashRehash (table);

上面的這行代碼會保證哈希表中的元素?cái)?shù)據(jù)小于等于表中的 bucket 數(shù)量。

這就是 buckets 后面的列表非常短的原因景醇，在理想情況下臀稚，每一個 buckets 中都只存儲一個或零個元素。

_NXHashRehash

如果哈希表在添加元素后三痰，其中的數(shù)據(jù)多于 buckets 數(shù)量吧寺，就會對 NXHashTable 進(jìn)行 _NXHashRehash 操作窜管。

static void _NXHashRehash (NXHashTable *table) {
    _NXHashRehashToCapacity (table, MORE_CAPACITY(table->nbBuckets));
}

它調(diào)用 _NXHashRehashToCapacity 方法來擴(kuò)大 NXHashTable 的容量（HashBucket 的個數(shù)）。

#define MORE_CAPACITY(b) (b*2+1)

而 MORE_CAPACITY 會將當(dāng)前哈希表的容量翻倍稚机，并將新的容量傳入 _NXHashRehashToCapacity 中：

void _NXHashRehashToCapacity (NXHashTable *table, unsigned newCapacity) {
    NXHashTable *old;
    NXHashState state;
    void    *aux;
    __unused void *z = ZONE_FROM_PTR(table);

    old = ALLOCTABLE(z);
    old->prototype = table->prototype; old->count = table->count;
    old->nbBuckets = table->nbBuckets; old->buckets = table->buckets;
    table->nbBuckets = newCapacity;
    table->count = 0; table->buckets = ALLOCBUCKETS(z, table->nbBuckets);
    state = NXInitHashState (old);
    while (NXNextHashState (old, &state, &aux))
        (void) NXHashInsert (table, aux);
    freeBuckets (old, NO);
    
    free (old->buckets);
    free (old);
}

1. 創(chuàng)建一個 NXHashTable 的指針指向原哈希表
2. 改變哈希表的 nbBuckets幕帆，并重新初始化哈希表的 buckets 數(shù)組
3. 重新將元素插入到哈希表中
4. 釋放原哈希表 old 以及 buckets

NXHashState

在將元素重新插入到哈希表中涉及了一個非常奇怪的結(jié)構(gòu)體 NXHashState，這個結(jié)構(gòu)體主要作用是遍歷 NXHashTable 中的元素赖条。

typedef struct {
    int i;
    int j;
} NXHashState;

我們可以使用如下的代碼對哈希表中的元素進(jìn)行遍歷：

 unsigned count = 0;
 MyData  *data;
 NXHashState state = NXInitHashState(table);
 while (NXNextHashState(table, &state, &data)) {
    count++;
 }

代碼片段中調(diào)用了兩個方法失乾，分別是 NXInitHashState 以及 NXNextHashState：

NXHashState NXInitHashState (NXHashTable *table) {
    NXHashState state;

    state.i = table->nbBuckets;
    state.j = 0;
    return state;
};

NXInitHashState 會將 NXHashState 指向哈希表的最末端：

objc-hashtable-hash-state-init

這個位置其實(shí)并不屬于 NXHashTable，它一定會為空纬乍。

而每次調(diào)用 NXNextHashState 都會向『前』移動一次：

int NXNextHashState (NXHashTable *table, NXHashState *state, void **data) {
    HashBucket      *buckets = (HashBucket *) table->buckets;

    while (state->j == 0) {
        if (state->i == 0) return NO;
        state->i--; state->j = buckets[state->i].count;
    }
    state->j--;
    buckets += state->i;
    *data = (void *) ((buckets->count == 1)
                      ? buckets->elements.one : buckets->elements.many[state->j]);
    return YES;
};

下面的 gif 為我么么展示了每一次調(diào)用 NXNextHashState 方法之后當(dāng)前的 NXHashState：

objc-hashtable-hashstate-next

NXHashRemove

這里的 NXHashRemove在某種意義上是 NXHashInsert 的逆操作：

void *NXHashRemove (NXHashTable *table, const void *data) {
    HashBucket  *bucket = BUCKETOF(table, data);
    unsigned    j = bucket->count;
    const void  **pairs;
    const void  **newt;
    __unused void *z = ZONE_FROM_PTR(table);

    if (! j) return NULL;
    if (j == 1) {
        if (! ISEQUAL(table, data, bucket->elements.one)) return NULL;
        data = bucket->elements.one;
        table->count--; bucket->count--; bucket->elements.one = NULL;
        return (void *) data;
    };
    pairs = bucket->elements.many;
    if (j == 2) {
        if (ISEQUAL(table, data, pairs[0])) {
            bucket->elements.one = pairs[1]; data = pairs[0];
        }
        else if (ISEQUAL(table, data, pairs[1])) {
            bucket->elements.one = pairs[0]; data = pairs[1];
        }
        else return NULL;
        FREEPAIRS (pairs);
        table->count--; bucket->count--;
        return (void *) data;
    };
    while (j--) {
        if (ISEQUAL(table, data, *pairs)) {
            data = *pairs;
            /* we shrink this bucket */
            newt = (bucket->count-1)
            ? ALLOCPAIRS(z, bucket->count-1) : NULL;
            if (bucket->count-1 != j)
                bcopy ((const char*)bucket->elements.many, (char*)newt, PTRSIZE*(bucket->count-j-1));
            if (j)
                bcopy ((const char*)(bucket->elements.many + bucket->count-j), (char*)(newt+bucket->count-j-1), PTRSIZE*j);
            FREEPAIRS (bucket->elements.many);
            table->count--; bucket->count--; bucket->elements.many = newt;
            return (void *) data;
        };
        pairs ++;
    };
    return NULL;
}

它的實(shí)現(xiàn)也分為三種情況碱茁，不過在這里就不多說了。

NXHashTable 的性能

在已經(jīng)熟悉了 NXHashTable 的具體實(shí)現(xiàn)之后仿贬，我們要分析插入不同數(shù)據(jù)量級的情況下纽竣，所需要的時間，這里是主程序的代碼茧泪，分別測試了在 100, 1000, 10000, 100000, 1000000, 2000000, 3000000, 5000000, 10000000 數(shù)據(jù)下 NXHashTable 的性能表現(xiàn)：

#import <Foundation/Foundation.h>
#import "hashtable2.h"

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        NSArray<NSNumber *> *capacities = @[
            @100,
            @1000,
            @10000,
            @100000,
            @1000000,
            @2000000,
            @3000000,
            @5000000,
            @10000000
        ];

        for (NSNumber *capacity in capacities) {
            NXHashTable *hashTable = NXCreateHashTable(NXPtrPrototype, 0, NULL);
            NSDate *methodStart = [NSDate date];
            for (NSInteger i = 0; i < capacity.integerValue; i++) {
                NSString *value = [NSString stringWithFormat:@"%ld", (long)i];
                NXHashInsert(hashTable, (__bridge void *)value);
            }
            NSDate *methodFinish = [NSDate date];
            NSTimeInterval executionTime = [methodFinish timeIntervalSinceDate:methodStart];
            NSLog(@"Capacities: %@, executionTime = %f, meanTime = %.10f", capacity, executionTime, executionTime / capacity.integerValue);

            free(hashTable);
        }

    }
    return 0;
}

代碼中初始化了一個 capacities 存儲需要測量的數(shù)據(jù)量級蜓氨，然后調(diào)用 NXHashInsert 方法將相當(dāng)數(shù)量級的數(shù)據(jù)添加到哈希表中：

在對 NXHashTable 的性能測試中，當(dāng)數(shù)據(jù)量小于 5000000 時队伟，執(zhí)行時間的增長還是線性的穴吹，平均時間也基本穩(wěn)定，但是一旦數(shù)據(jù)量達(dá)到了千萬級缰泡，執(zhí)行時間就會出現(xiàn)顯著的增長刀荒。

如果僅僅在哈希表中插入數(shù)據(jù)，相信其時間增長應(yīng)該都是線性的棘钞，這里出現(xiàn)問題的原因推測是在對哈希表進(jìn)行 Rehash 的時候缠借，遷移原數(shù)據(jù)至新的數(shù)組所造成的。

如何避免哈希表的 Rehash 呢宜猜，重新回顧一下創(chuàng)建哈希表的函數(shù)：

NXHashTable *NXCreateHashTable (NXHashTablePrototype prototype, unsigned capacity, const void *info);

這個函數(shù)的簽名中包含一個 capacity 的參數(shù)泼返，我們在上面的代碼中傳入了 0，也就是最開始的 buckets 數(shù)為 0姨拥，但是它的數(shù)目并不是固定的绅喉，它會隨著哈希表中數(shù)據(jù)的增多，逐漸變大叫乌。

capacity 只是一個提示柴罐，幫助 NXHashTable 了解其中會存儲多少數(shù)據(jù)。

如果在創(chuàng)建 NXHashTable 時傳入 capacity.integerValue：

  NXHashTable *hashTable = NXCreateHashTable(NXPtrPrototype, capacity.integerValue, NULL);

重新運(yùn)行代碼憨奸，測量性能：

雖然在測試 10,000,000 數(shù)據(jù)時其平均時間依然是 5,000,000 時的二倍革屠，不過整體的性能都有所提升，然而這部分性能的損耗暫時還不是很清楚原因。

如果我們使用 Instrument 對有無 capacity 的情況進(jìn)行比較（這是在使用 2,000,000 數(shù)據(jù)時進(jìn)行的測試）：

objc-hashtable-instrument

沒有傳入 capacity 的哈希表會在多次插入之后出現(xiàn)一個峰值（由于 Rehash 引起的似芝，其寬度就是 Rehash 使用的時間）那婉，而傳入 capacity 的哈希表會在代碼剛運(yùn)行時就初始化足夠大的數(shù)組。

NSMutableArray 性能

這部分只算是一個小插曲党瓮，你可以選擇跳過這一小節(jié)的內(nèi)容详炬。

NSMutableArray 的構(gòu)造器 - (instancetype)initWithCapacity:(NSUInteger)numItems 也有一個參數(shù) capacity，雖然數(shù)組和哈希表是兩種數(shù)據(jù)結(jié)構(gòu)寞奸。

不過我們這里主要研究的是：傳入 capacity 是否會對性能造成影響呛谜。

首先是使用 init 創(chuàng)建的 NSMutableArray 數(shù)組，也就是沒有傳入 capacity：

下面是使用 initWithCapacity: 創(chuàng)建的數(shù)組：

你可以在表格中看到蝇闭，兩者在執(zhí)行效率上并沒有顯著的差異或者區(qū)別呻率。

但是如果使用 instrument 來查看兩者的內(nèi)存分配，可以很明顯的看到呻引，沒有傳入 capacity 的 NSMutableArray 會在可變數(shù)組內(nèi)存占用增加前出現(xiàn)一個短暫的內(nèi)存分配峰值礼仗。

objc-hashtable-nsarray-instrument

導(dǎo)致這一現(xiàn)象的原始可能是：在將原數(shù)組中的內(nèi)容移入新數(shù)組時，臨時變量申請了大量的內(nèi)存控件逻悠。

在之后關(guān)于 CoreFoundation 源代碼分析的文中會介紹它們是怎么實(shí)現(xiàn)的元践。

NXHashTable 的應(yīng)用

在整個 objc/runtime 中，作為私有的數(shù)據(jù)結(jié)構(gòu) NXHashTable童谒，直接使用了它的就是存儲所有類或者元類的哈希表（在這里會忽略對元類的存儲单旁，因?yàn)閷?shí)現(xiàn)幾乎完全相同）：

static NXHashTable *realized_class_hash = nil;

我么可以使用 objc_copyClassList 獲取類的數(shù)組：

Class *
objc_copyClassList(unsigned int *outCount)
{
    rwlock_writer_t lock(runtimeLock);

    realizeAllClasses();

    Class *result = nil;
    NXHashTable *classes = realizedClasses();
    unsigned int count = NXCountHashTable(classes);

    if (count > 0) {
        Class cls;
        NXHashState state = NXInitHashState(classes);
        result = (Class *)malloc((1+count) * sizeof(Class));
        count = 0;
        while (NXNextHashState(classes, &state, (void **)&cls)) {
            result[count++] = cls;
        }
        result[count] = nil;
    }
        
    if (outCount) *outCount = count;
    return result;
}

1. 調(diào)用 realizedClasses 返回 realized_class_hash 哈希表
2. 使用 NSHashState 遍歷 realized_class_hash 中的類，并將所有的類存入 result

接下來使用上面的方法饥伊，打印出 realized_class_hash 中存儲的所有類：

objc-hashtable-copy-class-list

小結(jié)

NXHashTable 在 OS X 10.1 中就已經(jīng)標(biāo)記為棄用了象浑，但是依舊支持著 runtime 底層的工作。

NXHashTable 可以說有著非常非常久遠(yuǎn)的歷史了琅豆，最早可以追溯到將近 30 多年前 NeXT 時代：

// hashtable2.mm 文件中

hashtable2.m
Copyright 1989-1996 NeXT Software, Inc.
Created by Bertrand Serlet, Feb 89

NSHashTable 對哈希表的實(shí)現(xiàn)還是非常優(yōu)雅的愉豺，可以說非常標(biāo)準(zhǔn)的使用了拉鏈法實(shí)現(xiàn)哈希表。

不過現(xiàn)在茫因，我們會使用 NSHashTable 來取代這個上古時代的產(chǎn)物蚪拦。

關(guān)注倉庫，及時獲得更新：iOS-Source-Code-Analyze
Follow: Draveness · Github