上古時代 Objective-C 中哈希表的實現

vbje3051 8年前發布 | 32K 次閱讀 Objective-C開發

因為 ObjC 的 runtime 只能在 Mac OS 下才能編譯，所以文章中的代碼都是在 Mac OS，也就是 x86_64 架構下運行的，對于在 arm64 中運行的代碼會特別說明。

寫在前面

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

NXHashTable 的實現
NXHashTable 的性能分析
NXHashTable 的作用

NXHashTable 的實現有著將近 30 年的歷史，不過仍然作為重要的底層數據結構存儲整個應用中的類。

文中會涉及一些數據結構方面的簡單知識，例如拉鏈法。

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

NXHashTable

NXHashTable 的實現位于 hashtable2.mm 文件，我們先來看一下 NXHashTable 的結構以及重要的接口：

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

對于結構體中的 NXHashTablePrototype 屬性暫且不說，其中的 buckets 是真正用來存儲數據的數組。

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);

我們會以上面的這些方法作為切入點，分析 NXHashTable 的實現。

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;

}
</code></pre> 
  
在這個方法中，絕大多數代碼都是用來初始化 table->prototype 的，我們先把這部分全部忽略，分析一下簡略版本的實現。 
  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;

}
</code></pre> 
  
其中 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)))
</code></pre> 
  
ALLOCTABLE 和 ALLOCBUCKETS 只是調用了 malloc_zone_calloc 來初始化相應的結構體，而 GOOD_CAPACITY 有一些特殊，我們來舉個例子說明： 
  c   binary  result  
1   1       1  
2   10      3(0b11)  
6   110     7(0b111)  
100 1100100 127(0b111 1111)  
 
  c 表示傳入參數，binary 表示二進制下的參數，而 result 就是 GOOD_CAPACITY 返回的結果。 
   
   每次返回當前位數下的二進制最大值。 
   
  獲得 table->nbBuckets 之后，再初始化 table->nbBuckets * sizeof (HashBucket)大小的內存空間。 
  NXHashTablePrototype 
  在繼續分析其它方法之前，我們需要先知道 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 的函數指針（用于獲取數據的哈希、判斷兩個數據是否相等以及釋放數據）。 
  在 hashtable2.mm 文件中有一個宏 ISEQUAL 就是用了 NXHashTablePrototype 中的 isEqual 來判斷兩個數據是否相等： 
  #define ISEQUAL(table, data1, data2) ((data1 == data2) || (*table->prototype->isEqual)(table->info, data1, data2))
 
  可以說，NXHashTablePrototype 中存儲了一些構建哈希表必要的函數指針。 
   
   因為 NXHashTable 使用拉鏈法來實現哈希表，在存入表前對數據執行 hash，然后找到對應的 buckets，如果與 buckets 中的數據相同（使用 isEqual 判斷），就替換原數據，否則將數據添加到鏈表中。 
   
  HashBucket 
  在這里另一個需要注意的數據結構就是 HashBucket： 
  typedef struct    {  
    unsigned count;
    oneOrMany elements;
} HashBucket;
 
  oneOrMany 是一個 union 結構體： 
  typedef union {  
    const void *one;
    const void **many;
} oneOrMany;
 
   
   這么設計的主要原因是提升性能。 
   
  如果 HashBucket 中只有一個元素，那么就直接訪問 one，否則訪問 many，遍歷這個 many 列表。 
  NXCountHashTable 
  NXCountHashTable 方法應該是我們要介紹的方法中的最簡單的一個，它會直接返回 NXHashTable 結構體中的 count。 
  unsigned NXCountHashTable (NXHashTable *table) {  
    return table->count;
}
 
  NXHashMember 
  NXHashMember 的函數簽名雖然會返回 int，其實它是一個布爾值，會判斷當前的 NXHashTable 中是否包含傳入的數據： 
  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;

}
</code></pre> 
  
使用 BUCKETOF 對 data 進行 hash，將結果與哈希表的 buckets 數取模，返回 buckets 數組中對應的 NXHashBucket。 
  #define BUCKETOF(table, data) (((HashBucket *)table->buckets)+((*table->prototype->hash)(table->info, data) % table->nbBuckets))
 
  在獲取了 bucket 之后，根據其中元素個數的不同，選擇不同的分支： 
  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 比較查找的數據與 bucket->elements.one 
    count > 1，依次與 bucket->elements.many 中的值進行比較 
     
     你可能覺得到這里的時間復雜度比較糟糕，然而這個列表并不會很長，具體會在NXHashInsert 中解釋。 
    
  
   
  NXHashGet 
   
   其實我一直覺得這個方法可能用處不是很大，尤其是在使用默認的 NXHashTablePrototype 時，因為默認的 NXHashTablePrototype 中的 isEqual 函數指針只是比較兩個數據的指針是否相同。 
   其最大作用就是查看當前 data 是不是在表中。 
   如果當前數據在表中，那么這個方法只會返回一個相同的指針，沒有太多的意義。 
   
  它的實現跟上面的 NXHashMember 區別并不大，這里就不過多介紹了： 
  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;

}
</code></pre> 
  
NXHashInsert 
  NXHashInsert 是 NXHashTable 中比較重要的方法，其作用就是向表中插入數據： 
  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;

}
</code></pre> 
  
雖然這里的實現比上面的兩個方法復雜得多，但是脈絡仍然很清晰，我們將插入的過程分為三種情況： 
   
   bucket->count == 0 
   bucket->count == 1 
   bucket->count > 1 
   
  如果對應的 bucket 為空： 
  if (! j) {  
    bucket->count++; 
    bucket->elements.one = data;
    table->count++;
    return NULL;
};
 
  將數據直接填入 bucket，增加 bucket 中元素的數目，以及 table 中存儲的元素的數目： 
   
  如果原來的 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;

};
</code></pre> 
  
當前數據 data 如果與 bucket 中存儲的數據相同，就會更新這個數據，否則就會使用 ALLOCPAIRS 初始化一個新的數組，然后將 data 和原來的數據傳入。 
   
  但是如果原來的 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 將原鏈表中元素拷貝到新的數組 newt 中。 
   
  在每次添加完一個元素之后，都會進行下面的判斷： 
  if (table->count > table->nbBuckets) _NXHashRehash (table);  
 
   
   上面的這行代碼會保證哈希表中的元素數據小于等于表中的 bucket 數量。 
   
  這就是 buckets 后面的列表非常短的原因，在理想情況下，每一個 buckets 中都只存儲一個或零個元素。 
  _NXHashRehash 
  如果哈希表在添加元素后，其中的數據多于 buckets 數量，就會對 NXHashTable 進行 _NXHashRehash 操作。 
  static void _NXHashRehash (NXHashTable *table) {  
    _NXHashRehashToCapacity (table, MORE_CAPACITY(table->nbBuckets));
}
 
  它調用 _NXHashRehashToCapacity 方法來擴大 NXHashTable 的容量（HashBucket 的個數）。 
  #define MORE_CAPACITY(b) (b*2+1)
 
  而 MORE_CAPACITY 會將當前哈希表的容量翻倍，并將新的容量傳入 _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);

}
</code></pre> 
  
 
   創建一個 NXHashTable 的指針指向原哈希表 
   改變哈希表的 nbBuckets，并重新初始化哈希表的 buckets 數組 
   重新將元素插入到哈希表中 
   釋放原哈希表 old 以及 buckets 
   
  NXHashState 
  在將元素重新插入到哈希表中涉及了一個非常奇怪的結構體 NXHashState，這個結構體主要作用是遍歷 NXHashTable 中的元素。 
  typedef struct {  
    int i;
    int j;
} NXHashState;
 
  我們可以使用如下的代碼對哈希表中的元素進行遍歷： 
   unsigned count = 0;
 MyData     *data;
 NXHashState state = NXInitHashState(table);
 while (NXNextHashState(table, &state, &data)) {
    count++;
 }
 
  代碼片段中調用了兩個方法，分別是 NXInitHashState 以及 NXNextHashState： 
  NXHashState NXInitHashState (NXHashTable *table) {

    NXHashState    state;

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

};
</code></pre> 
  
NXInitHashState 會將 NXHashState 指向哈希表的最末端： 
   
   
   這個位置其實并不屬于 NXHashTable，它一定會為空。 
   
  而每次調用 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;

};
</code></pre> 
  
下面的 gif 為我么么展示了每一次調用 NXNextHashState 方法之后當前的 NXHashState： 
   
  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;

}
</code></pre> 
  
它的實現也分為三種情況，不過在這里就不多說了。 
  NXHashTable 的性能 
  在已經熟悉了 NXHashTable 的具體實現之后，我們要分析插入不同數據量級的情況下，所需要的時間，這里是主程序的代碼，分別測試了在 
  100, 1000, 10000, 100000, 1000000, 2000000, 3000000, 5000000, 10000000 數據下 NXHashTable 的性能表現： 
    
  #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;

}
</code></pre> 
  
代碼中初始化了一個 capacities 存儲需要測量的數據量級，然后調用 NXHashInsert方法將相當數量級的數據添加到哈希表中： 
  |Capacities|Execution Time| Mean Time| |-------:|---------:|-------------:| | 100| 0.000334| 0.0000033402 | | 1000| 0.001962| 0.0000019619 | | 10000| 0.022001| 0.0000022001 | | 100000| 0.349998| 0.0000035000 | | 1000000| 2.622551| 0.0000026226 | | 2000000| 4.165023| 0.0000020825 | | 3000000| 6.973098| 0.0000023244 | | 5000000| 13.179743| 0.0000026359 | |10000000| 53.387356| 0.0000053387 | 
  在對 NXHashTable 的性能測試中，當數據量小于 5000000 時，執行時間的增長還是線性的，平均時間也基本穩定，但是一旦數據量達到了千萬級，執行時間就會出現顯著的增長。 
  如果僅僅在哈希表中插入數據，相信其時間增長應該都是線性的，這里出現問題的原因推測是在對哈希表進行 Rehash 的時候，遷移原數據至新的數組所造成的。 
  如何避免哈希表的 Rehash 呢，重新回顧一下創建哈希表的函數： 
  NXHashTable *NXCreateHashTable (NXHashTablePrototype prototype, unsigned capacity, const void *info);  
 
  這個函數的簽名中包含一個 capacity 的參數，我們在上面的代碼中傳入了 0，也就是最開始的 buckets 數為 0，但是它的數目并不是固定的，它會隨著哈希表中數據的增多，逐漸變大。 
   
   capacity 只是一個提示，幫助 NXHashTable 了解其中會存儲多少數據。 
   
  如果在創建 NXHashTable 時傳入 capacity.integerValue： 
    NXHashTable *hashTable = NXCreateHashTable(NXPtrPrototype, capacity.integerValue, NULL);
 
  重新運行代碼，測量性能： 
  |Capacities|Execution Time| Mean Time| |-------:|---------:|-------------:| | 100| 0.000740| 0.0000073999 | | 1000| 0.003442| 0.0000034420 | | 10000| 0.023341| 0.0000023341 | | 100000| 0.215209| 0.0000021521 | | 1000000| 1.836802| 0.0000018368 | | 2000000| 3.683246| 0.0000018416 | | 3000000| 5.474610| 0.0000018249 | | 5000000| 10.576254| 0.0000021153 | |10000000| 46.725459| 0.0000046725 | 
  雖然在測試 10,000,000 數據時其平均時間依然是 5,000,000 時的二倍，不過整體的性能都有所提升，然而這部分性能的損耗暫時還不是很清楚原因。 
  如果我們使用 Instrument 對有無 capacity 的情況進行比較（這是在使用 2,000,000 數據時進行的測試）： 
   
  沒有傳入 capacity 的哈希表會在多次插入之后出現一個峰值（由于 Rehash 引起的，其寬度就是 Rehash 使用的時間），而傳入 capacity 的哈希表會在代碼剛運行時就初始化足夠大的數組。 
  NSMutableArray 性能 
   
   這部分只算是一個小插曲，你可以選擇跳過這一小節的內容。 
   
  NSMutableArray 的構造器 
  - (instancetype)initWithCapacity:(NSUInteger)numItems 也有一個參數 capacity，雖然數組和哈希表是兩種數據結構。 
    
   
   不過我們這里主要研究的是：傳入 capacity 是否會對性能造成影響。 
   
  首先是使用 init 創建的 NSMutableArray 數組，也就是沒有傳入 capacity： 
  |Capacities|Execution Time| Mean Time| |--------:|---------:|-------------:| | 100| 0.000539| 0.0000053900| | 1000| 0.003185| 0.0000031850| | 10000| 0.074033| 0.0000074033| | 100000| 0.370899| 0.0000037090| | 1000000| 1.504855| 0.0000015049| | 2000000| 2.852519| 0.0000014263| | 3000000| 3.995536| 0.0000013318| | 5000000| 6.833879| 0.0000013668| | 10000000| 14.444605| 0.0000014445| 
  下面是使用 initWithCapacity: 創建的數組： 
  |Capacities|Execution Time| Mean Time| |--------:|---------:|-------------:| | 100| 0.000256| 0.0000025600| | 1000| 0.001775| 0.0000017750| | 10000| 0.015906| 0.0000015906| | 100000| 0.174376| 0.0000017438| | 1000000| 1.650481| 0.0000016505| | 2000000| 2.802310| 0.0000014012| | 3000000| 4.451261| 0.0000014838| | 5000000| 7.093753| 0.0000014188| | 10000000| 14.598415| 0.0000014598| 
  你可以在表格中看到，兩者在執行效率上并沒有顯著的差異或者區別。 
  但是如果使用 instrument 來查看兩者的內存分配，可以很明顯的看到，沒有傳入 capacity 的 NSMutableArray 會在可變數組內存占用增加前出現一個短暫的內存分配峰值。 
   
  導致這一現象的原始可能是：在將原數組中的內容移入新數組時，臨時變量申請了大量的內存控件。 
   
   在之后關于 CoreFoundation 源代碼分析的文中會介紹它們是怎么實現的。 
   
  NXHashTable 的應用 
  在整個 objc/runtime 中，作為私有的數據結構 NXHashTable，直接使用了它的就是存儲所有類或者元類的哈希表（在這里會忽略對元類的存儲，因為實現幾乎完全相同）： 
  static NXHashTable *realized_class_hash = nil;  
 
  我么可以使用 objc_copyClassList 獲取類的數組： 
  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;

}
</code></pre> 
  
 
   調用 realizedClasses 返回 realized_class_hash 哈希表 
   使用 NSHashState 遍歷 realized_class_hash 中的類，并將所有的類存入 result 
   
  接下來使用上面的方法，打印出 realized_class_hash 中存儲的所有類： 
   
  小結 
   
   NXHashTable 在 OS X 10.1 中就已經標記為棄用了，但是依舊支持著 runtime 底層的工作。 
   
  NXHashTable 可以說有著非常非常久遠的歷史了，最早可以追溯到將近 30 多年前 NeXT 時代： 
  // hashtable2.mm 文件中
hashtable2.m

Copyright 1989-1996 NeXT Software, Inc.

Created by Bertrand Serlet, Feb 89

</code></pre> 
  
NSHashTable 對哈希表的實現還是非常優雅的，可以說非常標準的使用了拉鏈法實現哈希表。 
  不過現在，我們會使用 NSHashTable 來取代這個上古時代的產物。 
  來自：http://draveness.me/hashtable/


                    
                         本文由用戶 vbje3051 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
                         轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
                         本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！
                         本文地址：http://www.baiduhome.net/lib/view/open1462847338718.html
                         Objective-C開發

上古時代 Objective-C 中哈希表的實現

寫在前面

NXHashTable

NXCreateHashTableFromZone

define GOOD_CAPACITY(c) (exp2m1u (log2u (c)+1))

define ALLOCBUCKETS(z,nb) ((HashBucket ) malloc_zone_calloc ((malloc_zone_t )z, nb, sizeof (HashBucket)))

NXCountHashTable

NXHashMember

NXHashGet

NXHashInsert

NXHashRemove

NXHashTable 的性能

import "hashtable2.h"

NSMutableArray 性能

NXHashTable 的應用

小結

相關經驗

相關資訊

相關文檔

目錄