<blockquote>     <p>因为 ObjC 的 runtime 只能在 Mac OS 下才能编译，所以文章中的代码都是在 Mac OS，也就是 <code>x86_64</code> 架构下运行的，对于在 arm64 中运行的代码会特别说明。</p>    </blockquote>    <h2>写在前面</h2>    <p>文章会介绍上古时代 Objective-C 哈希表，也就是 <code>NXHashTable</code> ：</p>    <ul>     <li><code>NXHashTable</code> 的实现</li>     <li><code>NXHashTable</code> 的性能分析</li>     <li><code>NXHashTable</code> 的作用</li>    </ul>    <p><code>NXHashTable</code> 的实现有着将近 30 年的历史，不过仍然作为重要的底层数据结构存储整个应用中的类。</p>    <blockquote>     <p>文中会涉及一些数据结构方面的简单知识，例如<a href="/misc/goto?guid=4959672782601271013">拉链法</a>。</p>     <p>注意：文章中分析的不是 <code>NSHashTable</code> 而是 <code>NXHashTable</code>。</p>    </blockquote>    <h2>NXHashTable</h2>    <p><code>NXHashTable</code> 的实现位于 <code>hashtable2.mm</code> 文件，我们先来看一下 <code>NXHashTable</code> 的结构以及重要的接口：</p>    <pre>  <code class="language-objectivec">typedef struct {        const NXHashTablePrototype *prototype;      unsigned count;      unsigned nbBuckets;      void *buckets;      const void *info;  } NXHashTable;  </code></pre>    <p>对于结构体中的 <code>NXHashTablePrototype</code> 属性暂且不说，其中的 <code>buckets</code> 是真正用来存储数据的数组。</p>    <pre>  <code class="language-objectivec">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);    </code></pre>    <p>我们会以上面的这些方法作为切入点，分析 <code>NXHashTable</code> 的实现。</p>    <h3>NXCreateHashTableFromZone</h3>    <p><code>NXHashTable</code> 使用 <code>NXCreateHashTableFromZone</code> 方法初始化：</p>    <pre>  <code class="language-objectivec">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>    <p>在这个方法中，绝大多数代码都是用来初始化 <code>table->prototype</code> 的，我们先把这部分全部忽略，分析一下简略版本的实现。</p>    <pre>  <code class="language-objectivec">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>    <p>其中 <code>ALLOCTABLE</code>、<code>GOOD_CAPACITY</code> 以及 <code>ALLOCBUCKETS</code> 都是用来辅助初始化的宏：</p>    <pre>  <code class="language-objectivec">#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>    <p><code>ALLOCTABLE</code> 和 <code>ALLOCBUCKETS</code> 只是调用了 <code>malloc_zone_calloc</code> 来初始化相应的结构体，而 <code>GOOD_CAPACITY</code> 有一些特殊，我们来举个例子说明：</p>    <pre>  <code class="language-objectivec">c   binary  result    1   1       1    2   10      3(0b11)    6   110     7(0b111)    100 1100100 127(0b111 1111)    </code></pre>    <p><code>c</code> 表示传入参数，<code>binary</code> 表示二进制下的参数，而 <code>result</code> 就是 <code>GOOD_CAPACITY</code> 返回的结果。</p>    <blockquote>     <p>每次返回当前位数下的二进制最大值。</p>    </blockquote>    <p>获得 <code>table->nbBuckets</code> 之后，再初始化 <code>table->nbBuckets * sizeof (HashBucket)</code>大小的内存空间。</p>    <p>NXHashTablePrototype</p>    <p>在继续分析其它方法之前，我们需要先知道 <code>NXHashTablePrototype</code> 是什么：</p>    <pre>  <code class="language-objectivec">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;  </code></pre>    <p><code>NXHashTablePrototype</code> 中存储了 <code>hash</code>、<code>isEqual</code> 和 <code>free</code> 的函数指针（用于获取数据的哈希、判断两个数据是否相等以及释放数据）。</p>    <p>在 <code>hashtable2.mm</code> 文件中有一个宏 <code>ISEQUAL</code> 就是用了 <code>NXHashTablePrototype</code> 中的 <code>isEqual</code> 来判断两个数据是否相等：</p>    <pre>  <code class="language-objectivec">#define ISEQUAL(table, data1, data2) ((data1 == data2) || (*table->prototype->isEqual)(table->info, data1, data2))  </code></pre>    <p>可以说，<code>NXHashTablePrototype</code> 中存储了一些构建哈希表必要的函数指针。</p>    <blockquote>     <p>因为 <code>NXHashTable</code> 使用<a href="/misc/goto?guid=4959672782601271013">拉链法</a>来实现哈希表，在存入表前对数据执行 hash，然后找到对应的 buckets，如果与 buckets 中的数据相同（使用 isEqual 判断），就替换原数据，否则将数据添加到链表中。</p>    </blockquote>    <p>HashBucket</p>    <p>在这里另一个需要注意的数据结构就是 <code>HashBucket</code>：</p>    <pre>  <code class="language-objectivec">typedef struct    {        unsigned count;      oneOrMany elements;  } HashBucket;  </code></pre>    <p><code>oneOrMany</code> 是一个 <code>union</code> 结构体：</p>    <pre>  <code class="language-objectivec">typedef union {        const void *one;      const void **many;  } oneOrMany;  </code></pre>    <blockquote>     <p>这么设计的主要原因是提升性能。</p>    </blockquote>    <p>如果 <code>HashBucket</code> 中只有一个元素，那么就直接访问 <code>one</code>，否则访问 <code>many</code>，遍历这个 <code>many</code> 列表。</p>    <h3>NXCountHashTable</h3>    <p><code>NXCountHashTable</code> 方法应该是我们要介绍的方法中的最简单的一个，它会直接返回 <code>NXHashTable</code> 结构体中的 <code>count</code>。</p>    <pre>  <code class="language-objectivec">unsigned NXCountHashTable (NXHashTable *table) {        return table->count;  }  </code></pre>    <h3>NXHashMember</h3>    <p><code>NXHashMember</code> 的函数签名虽然会返回 <code>int</code>，其实它是一个布尔值，会判断当前的 <code>NXHashTable</code> 中是否包含传入的数据：</p>    <pre>  <code class="language-objectivec">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>    <p>使用 <code>BUCKETOF</code> 对 <code>data</code> 进行 hash，将结果与哈希表的 <code>buckets</code> 数取模，返回 <code>buckets</code> 数组中对应的 <code>NXHashBucket</code>。</p>    <pre>  <code class="language-objectivec">#define BUCKETOF(table, data) (((HashBucket *)table->buckets)+((*table->prototype->hash)(table->info, data) % table->nbBuckets))  </code></pre>    <p>在获取了 <code>bucket</code> 之后，根据其中元素个数的不同，选择不同的分支：</p>    <pre>  <code class="language-objectivec">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 ++;  };  </code></pre>    <ul>     <li><code>count == 0</code>，直接返回</li>     <li><code>count == 1</code>，使用 <code>ISEQUAL</code> 比较查找的数据与 <code>bucket->elements.one</code></li>     <li> <p><code>count > 1</code>，依次与 <code>bucket->elements.many</code> 中的值进行比较</p>      <blockquote>       <p>你可能觉得到这里的时间复杂度比较糟糕，然而这个列表并不会很长，具体会在<a href="/misc/goto?guid=4959672782695249948">NXHashInsert</a> 中解释。</p>      </blockquote> </li>    </ul>    <h3>NXHashGet</h3>    <blockquote>     <p>其实我一直觉得这个方法可能用处不是很大，尤其是在使用默认的 <code>NXHashTablePrototype</code> 时，因为默认的 <code>NXHashTablePrototype</code> 中的 <code>isEqual</code> 函数指针只是比较两个数据的指针是否相同。</p>     <p>其最大作用就是查看当前 <code>data</code> 是不是在表中。</p>     <p>如果当前数据在表中，那么这个方法只会返回一个相同的指针，没有太多的意义。</p>    </blockquote>    <p>它的实现跟上面的 <code>NXHashMember</code> 区别并不大，这里就不过多介绍了：</p>    <pre>  <code class="language-objectivec">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>    <h3>NXHashInsert</h3>    <p><code>NXHashInsert</code> 是 <code>NXHashTable</code> 中比较重要的方法，其作用就是向表中插入数据：</p>    <pre>  <code class="language-objectivec">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>    <p>虽然这里的实现比上面的两个方法复杂得多，但是脉络仍然很清晰，我们将插入的过程分为三种情况：</p>    <ul>     <li><code>bucket->count == 0</code></li>     <li><code>bucket->count == 1</code></li>     <li><code>bucket->count > 1</code></li>    </ul>    <p>如果对应的 <code>bucket</code> 为空：</p>    <pre>  <code class="language-objectivec">if (! j) {        bucket->count++;       bucket->elements.one = data;      table->count++;      return NULL;  };  </code></pre>    <p>将数据直接填入 <code>bucket</code>，增加 <code>bucket</code> 中元素的数目，以及 <code>table</code> 中存储的元素的数目：</p>    <p><img alt="上古时代 Objective-C 中哈希表的实现" src="https://simg.open-open.com/show/eeef6d32633678045982055ec592ccf0.gif" width="800" height="600"></p>    <p>如果原来的 <code>buckets</code> 中有一个元素，它会替换或者使用 <code>many</code> 替换原来的 <code>one</code>：</p>    <pre>  <code class="language-objectivec">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>    <p>当前数据 <code>data</code> 如果与 <code>bucket</code> 中存储的数据相同，就会更新这个数据，否则就会使用 <code>ALLOCPAIRS</code> 初始化一个新的数组，然后将 <code>data</code> 和原来的数据传入。</p>    <p><img alt="上古时代 Objective-C 中哈希表的实现" src="https://simg.open-open.com/show/69dacd8a86abedd417c6fd3270c2dd76.gif" width="800" height="600"></p>    <p>但是如果原来的 <code>bucket</code> 中存储的元素大于 1，那么会在链表的头部追加一个新的元素：</p>    <pre>  <code class="language-objectivec">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++;    </code></pre>    <p>上面的代码使用 <code>bcopy</code> 将原链表中元素拷贝到新的数组 <code>newt</code> 中。</p>    <p><img alt="上古时代 Objective-C 中哈希表的实现" src="https://simg.open-open.com/show/360ab0b40bb9bc0abf26e85f4413d794.gif" width="800" height="600"></p>    <p>在每次添加完一个元素之后，都会进行下面的判断：</p>    <pre>  <code class="language-objectivec">if (table->count > table->nbBuckets) _NXHashRehash (table);    </code></pre>    <blockquote>     <p>上面的这行代码会保证哈希表中的元素数据小于等于表中的 bucket 数量。</p>    </blockquote>    <p>这就是 <code>buckets</code> 后面的列表非常短的原因，在理想情况下，每一个 <code>buckets</code> 中都只存储一个或零个元素。</p>    <p>_NXHashRehash</p>    <p>如果哈希表在添加元素后，其中的数据多于 <code>buckets</code> 数量，就会对 <code>NXHashTable</code> 进行 <code>_NXHashRehash</code> 操作。</p>    <pre>  <code class="language-objectivec">static void _NXHashRehash (NXHashTable *table) {        _NXHashRehashToCapacity (table, MORE_CAPACITY(table->nbBuckets));  }  </code></pre>    <p>它调用 <code>_NXHashRehashToCapacity</code> 方法来扩大 <code>NXHashTable</code> 的容量（<code>HashBucket</code> 的个数）。</p>    <pre>  <code class="language-objectivec">#define MORE_CAPACITY(b) (b*2+1)  </code></pre>    <p>而 <code>MORE_CAPACITY</code> 会将当前哈希表的容量翻倍，并将新的容量传入 <code>_NXHashRehashToCapacity</code> 中：</p>    <pre>  <code class="language-objectivec">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>    <ol>     <li>创建一个 <code>NXHashTable</code> 的指针指向原哈希表</li>     <li>改变哈希表的 <code>nbBuckets</code>，并重新初始化哈希表的 <code>buckets</code> 数组</li>     <li>重新将元素插入到哈希表中</li>     <li>释放原哈希表 <code>old</code> 以及 <code>buckets</code></li>    </ol>    <p>NXHashState</p>    <p>在将元素重新插入到哈希表中涉及了一个非常奇怪的结构体 <code>NXHashState</code>，这个结构体主要作用是遍历 <code>NXHashTable</code> 中的元素。</p>    <pre>  <code class="language-objectivec">typedef struct {        int i;      int j;  } NXHashState;  </code></pre>    <p>我们可以使用如下的代码对哈希表中的元素进行遍历：</p>    <pre>  <code class="language-objectivec"> unsigned count = 0;   MyData     *data;   NXHashState state = NXInitHashState(table);   while (NXNextHashState(table, &state, &data)) {      count++;   }  </code></pre>    <p>代码片段中调用了两个方法，分别是 <code>NXInitHashState</code> 以及 <code>NXNextHashState</code>：</p>    <pre>  <code class="language-objectivec">NXHashState NXInitHashState (NXHashTable *table) {        NXHashState    state;        state.i = table->nbBuckets;      state.j = 0;      return state;  };  </code></pre>    <p><code>NXInitHashState</code> 会将 <code>NXHashState</code> 指向哈希表的最末端：</p>    <p><img alt="上古时代 Objective-C 中哈希表的实现" src="https://simg.open-open.com/show/f10b5eae5ca2bc6ce2144cff64ab8dc3.png" width="484" height="447"></p>    <blockquote>     <p>这个位置其实并不属于 <code>NXHashTable</code>，它一定会为空。</p>    </blockquote>    <p>而每次调用 <code>NXNextHashState</code> 都会向『前』移动一次：</p>    <pre>  <code class="language-objectivec">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>    <p>下面的 gif 为我么么展示了每一次调用 <code>NXNextHashState</code> 方法之后当前的 <code>NXHashState</code>：</p>    <p><img alt="上古时代 Objective-C 中哈希表的实现" src="https://simg.open-open.com/show/4999d4426d010f4343613b1b94e38ec7.gif" width="800" height="600"></p>    <h3>NXHashRemove</h3>    <p>这里的 <code>NXHashRemove</code>在某种意义上是 <code>NXHashInsert</code> 的逆操作：</p>    <pre>  <code class="language-objectivec">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>    <p>它的实现也分为三种情况，不过在这里就不多说了。</p>    <h2>NXHashTable 的性能</h2>    <p>在已经熟悉了 <code>NXHashTable</code> 的具体实现之后，我们要分析插入不同数据量级的情况下，所需要的时间，这里是主程序的代码，分别测试了在</p>    <p><code>100, 1000, 10000, 100000, 1000000, 2000000, 3000000, 5000000, 10000000</code> 数据下 <code>NXHashTable</code> 的性能表现：</p>    <p> </p>    <pre>  <code class="language-objectivec">#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>    <p>代码中初始化了一个 <code>capacities</code> 存储需要测量的数据量级，然后调用 <code>NXHashInsert</code>方法将相当数量级的数据添加到哈希表中：</p>    <p>|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 |</p>    <p>在对 <code>NXHashTable</code> 的性能测试中，当数据量小于 5000000 时，执行时间的增长还是线性的，平均时间也基本稳定，但是一旦数据量达到了千万级，执行时间就会出现显著的增长。</p>    <p>如果仅仅在哈希表中插入数据，相信其时间增长应该都是线性的，这里出现问题的原因推测是在对哈希表进行 Rehash 的时候，迁移原数据至新的数组所造成的。</p>    <p>如何避免哈希表的 Rehash 呢，重新回顾一下创建哈希表的函数：</p>    <pre>  <code class="language-objectivec">NXHashTable *NXCreateHashTable (NXHashTablePrototype prototype, unsigned capacity, const void *info);    </code></pre>    <p>这个函数的签名中包含一个 <code>capacity</code> 的参数，我们在上面的代码中传入了 0，也就是最开始的 <code>buckets</code> 数为 0，但是它的数目并不是固定的，它会随着哈希表中数据的增多，逐渐变大。</p>    <blockquote>     <p><code>capacity</code> 只是一个提示，帮助 NXHashTable 了解其中会存储多少数据。</p>    </blockquote>    <p>如果在创建 <code>NXHashTable</code> 时传入 <code>capacity.integerValue</code>：</p>    <pre>  <code class="language-objectivec">  NXHashTable *hashTable = NXCreateHashTable(NXPtrPrototype, capacity.integerValue, NULL);  </code></pre>    <p>重新运行代码，测量性能：</p>    <p>|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 |</p>    <p>虽然在测试 <code>10,000,000</code> 数据时其平均时间依然是 <code>5,000,000</code> 时的二倍，不过整体的性能都有所提升，然而这部分性能的损耗暂时还不是很清楚原因。</p>    <p>如果我们使用 Instrument 对有无 <code>capacity</code> 的情况进行比较（这是在使用 <code>2,000,000</code> 数据时进行的测试）：</p>    <p><img alt="上古时代 Objective-C 中哈希表的实现" src="https://simg.open-open.com/show/125944ee4ecd4f79ce96b462a701e0d9.jpg" width="712" height="527"></p>    <p>没有传入 <code>capacity</code> 的哈希表会在多次插入之后出现一个峰值（由于 Rehash 引起的，其宽度就是 Rehash 使用的时间），而传入 <code>capacity</code> 的哈希表会在代码刚运行时就初始化足够大的数组。</p>    <h2>NSMutableArray 性能</h2>    <blockquote>     <p>这部分只算是一个小插曲，你可以选择跳过这一小节的内容。</p>    </blockquote>    <p><code>NSMutableArray</code> 的构造器</p>    <p><code>- (instancetype)initWithCapacity:(NSUInteger)numItems</code> 也有一个参数 <code>capacity</code>，虽然数组和哈希表是两种数据结构。</p>    <p> </p>    <blockquote>     <p>不过我们这里主要研究的是：传入 <code>capacity</code> 是否会对性能造成影响。</p>    </blockquote>    <p>首先是使用 <code>init</code> 创建的 <code>NSMutableArray</code> 数组，也就是没有传入 <code>capacity</code>：</p>    <p>|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|</p>    <p>下面是使用 <code>initWithCapacity:</code> 创建的数组：</p>    <p>|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|</p>    <p>你可以在表格中看到，两者在执行效率上并没有显著的差异或者区别。</p>    <p>但是如果使用 instrument 来查看两者的内存分配，可以很明显的看到，没有传入 <code>capacity</code> 的 <code>NSMutableArray</code> 会在可变数组内存占用增加前出现一个短暂的内存分配峰值。</p>    <p><img alt="上古时代 Objective-C 中哈希表的实现" src="https://simg.open-open.com/show/e9dd9ffc4271ea6b407ee8241a25b0cd.jpg" width="1034" height="723"></p>    <p>导致这一现象的原始可能是：在将原数组中的内容移入新数组时，临时变量申请了大量的内存控件。</p>    <blockquote>     <p>在之后关于 CoreFoundation 源代码分析的文中会介绍它们是怎么实现的。</p>    </blockquote>    <h2>NXHashTable 的应用</h2>    <p>在整个 objc/runtime 中，作为私有的数据结构 <code>NXHashTable</code>，直接使用了它的就是存储所有类或者元类的哈希表（在这里会忽略对元类的存储，因为实现几乎完全相同）：</p>    <pre>  <code class="language-objectivec">static NXHashTable *realized_class_hash = nil;    </code></pre>    <p>我么可以使用 <code>objc_copyClassList</code> 获取类的数组：</p>    <pre>  <code class="language-objectivec">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>    <ol>     <li>调用 <code>realizedClasses</code> 返回 <code>realized_class_hash</code> 哈希表</li>     <li>使用 <code>NSHashState</code> 遍历 <code>realized_class_hash</code> 中的类，并将所有的类存入 <code>result</code></li>    </ol>    <p>接下来使用上面的方法，打印出 <code>realized_class_hash</code> 中存储的所有类：</p>    <p><img alt="上古时代 Objective-C 中哈希表的实现" src="https://simg.open-open.com/show/bb66798f856bb298bdcf24fb04e500ae.jpg" width="1306" height="929"></p>    <h2>小结</h2>    <blockquote>     <p><code>NXHashTable</code> 在 OS X 10.1 中就已经标记为弃用了，但是依旧支持着 runtime 底层的工作。</p>    </blockquote>    <p><code>NXHashTable</code> 可以说有着非常非常久远的历史了，最早可以追溯到将近 30 多年前 NeXT 时代：</p>    <pre>  <code class="language-objectivec">// hashtable2.mm 文件中    hashtable2.m    Copyright 1989-1996 NeXT Software, Inc.    Created by Bertrand Serlet, Feb 89    </code></pre>    <p><code>NSHashTable</code> 对哈希表的实现还是非常优雅的，可以说非常标准的使用了<a href="/misc/goto?guid=4959672782601271013">拉链法</a>实现哈希表。</p>    <p>不过现在，我们会使用 <code>NSHashTable</code> 来取代这个上古时代的产物。</p>    <p>来自：<a href="/misc/goto?guid=4959672782784971021">http://draveness.me/hashtable/</a></p>