转载

上古时代 Objective-C 中哈希表的实现

关注仓库，及时获得更新： iOS-Source-Code-Analyze

因为 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; }

在这个方法中，绝大多数代码都是用来初始化 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; }

其中 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 只是调用了 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; }

使用 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 中的值进行比较

    你可能觉得到这里的时间复杂度比较糟糕，然而这个列表并不会很长，具体会在中解释。

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

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

虽然这里的实现比上面的两个方法复杂得多，但是脉络仍然很清晰，我们将插入的过程分为三种情况：

  • 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 中存储的元素的数目：

上古时代 Objective-C 中哈希表的实现

如果原来的 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; };

当前数据 data 如果与 bucket 中存储的数据相同，就会更新这个数据，否则就会使用 ALLOCPAIRS 初始化一个新的数组，然后将 data 和原来的数据传入。

上古时代 Objective-C 中哈希表的实现

但是如果原来的 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 中。

上古时代 Objective-C 中哈希表的实现

在每次添加完一个元素之后，都会进行下面的判断：

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); }
  1. 创建一个 NXHashTable 的指针指向原哈希表
  2. 改变哈希表的 nbBuckets ，并重新初始化哈希表的 buckets 数组
  3. 重新将元素插入到哈希表中
  4. 释放原哈希表 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; };

NXInitHashState 会将 NXHashState 指向哈希表的最末端：

上古时代 Objective-C 中哈希表的实现

这个位置其实并不属于 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; };

下面的 gif 为我么么展示了每一次调用 NXNextHashState 方法之后当前的 NXHashState ：

上古时代 Objective-C 中哈希表的实现

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

它的实现也分为三种情况，不过在这里就不多说了。

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

代码中初始化了一个 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 数据时进行的测试）：

上古时代 Objective-C 中哈希表的实现

没有传入 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 会在可变数组内存占用增加前出现一个 短暂的内存分配峰值 。

上古时代 Objective-C 中哈希表的实现

导致这一现象的原始可能是：在将原数组中的内容移入新数组时， 临时变量申请了大量的内存控件 。

在之后关于 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; }
  1. 调用 realizedClasses 返回 realized_class_hash 哈希表
  2. 使用 NSHashState 遍历 realized_class_hash 中的类，并将所有的类存入 result

接下来使用上面的方法，打印出 realized_class_hash 中存储的所有类：

上古时代 Objective-C 中哈希表的实现

小结

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

NSHashTable 对哈希表的实现还是非常优雅的，可以说非常标准的使用了 拉链法 实现哈希表。

不过现在，我们会使用 NSHashTable 来取代这个上古时代的产物。

原文  http://draveness.me/hashtable/
正文到此结束
所属分类： 编程技术

热门推荐

相关文章

阿里云首购8折
说给你听

本文目录
随机标签
书籍教程
springboot-demo Java入门教程 bootstrap3 CSS Apache基础教程 php ionic 教程 Python mysql教程 eclipse Ubuntu VPS系统配置 AngularJS 教程 MongoDB教程 Struts2教程 Redis教程 Spring教程 Git教程 Jenkins进阶系列 openfire参考指南 Java设计模式 HBase教程 Maven教程 hibernate教程 Docker 教程 memcached教程 Quartz指南 springcloud-demo Hive教程 Ant教程 ANTLR教程 SpringCloud java实例教程 XStream教程 Hazelcast教程 Elastic-Job-Lite 深入浅出MyBatis SVN教程 ibaties教程 rabittmq教程 solr教程 Hadoop教程 WebService CXF学习 JPA教程 ActiveMQ中文指南 java-demo Java内存模型 dubbo教程 python3-demo Linux入门视频教程
近期评论
  1. 1 如何将Spring Cloud Task发布Data Flow上执行？
  2. 2 Spring Cloud Data Flow快速入门Demo
  3. 3 Spring Cloud Consul实现选举机制
  4. 4 Spring Boot集成ShedLock实现分布式定时任务
  5. 5 利用oss进行数据库和网站图片备份
  6. 6 Spring Cloud Stream实现数据流处理
  7. 7 Python3访问MySQL数据库快速入门Demo
  8. 8 Github开源项目作者可以免费申请 JetBrains 全家桶
  9. 9 Spring Cloud Vault快速入门Demo
  10. 10 Spring Cloud Gateway快速入门Demo
网站信息
  • 文章总数：82,716 篇
  • 文件总数：284,297 个
  • 标签总数：2,396 个
  • 分类总数：85 个
  • 留言数量：2,560 条
  • 在线人数：604 人
  • 运行天数：4,411天
  • 最后更新：2024年11月24日07点
Loading...

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

[HBLOG]公众号 HBLOG HBLOG