数据结构都可以从 苹果开源代码 里 ,objc4 源码 适配mac系统 macOS Big Sur 11.5 ~ 11.6.2
具体数据结构在 hashtable2.h 里面都有定义，嫌麻烦的可以直接看 这个github 。 这里只解读关键函数，其他的基本都比较容易看明白
调用顺序: NXHashInsert -> _NXHashRehash -> _NXHashRehashToCapacity
/* private data structure; may change */
_NXHashRehashToCapacity (table, MORE_CAPACITY(table->nbBuckets)); //扩容2倍 + 1
}
//newCapacity 扩容大小是原先2倍 + 1
void_NXHashRehashToCapacity(NXHashTable *table,unsigned newCapacity) {
/* Rehash: we create a pseudo table pointing really to the old guys,
extend self, copy the old pairs, and free the pseudo table */
NXHashTable *old;
NXHashState state;
void *aux;
__unusedvoid*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); //这里面
//newCapacity 扩容之后，同一个buckets里面取出来的数据 hash表计算出来的hash值索引和原来就不一定一致，这样同一个aux 在进行insert 就会开新的bucket来存放数据。所以不是无限循环操作，这个琢磨好久才明白，否则就是无限循环插入了。
while(NXNextHashState(old, &state, &aux)) //循环插入
(void)NXHashInsert(table, aux);
freeBuckets(old,NO);
if(old->count!= table->count)
_objc_inform("*** hashtable: count differs after rehashing; probably indicates a broken invariant: there are x and y such as isEqual(x, y) is TRUE but hash(x) != hash (y)\n");
free(old->buckets);
free(old);
}
//这就是二维数组， i 表示 buckets 数量即: hash 表开的数组数量， j 表示 每一个buckets 里面的元素数量
NXHashState NXInitHashState (NXHashTable *table) {NXHashState state;
state.i= table->nbBuckets;
state.j=0;
returnstate;
};
//从table.buckets表里面逆序查找hash非空bucket，返回当前bucket 链表最末端的数据,写入到 *data
int NXNextHashState(NXHashTable *table , NXHashState *state, void **data) {
HashBucket *buckets = (HashBucket*) table->buckets;
// j == 0 表示当前bucket 数据是空的， state -> i -- ，逆序向上在找一个bucket
while(state->j==0) {
if (state->i==0) return NO;
state->i--; state->j= buckets[state->i].count;
}
state-> j--; // j 数组数据的数量，j -- 表示数据在当前bucket 的真正下标
buckets += state->i;//移动数组指针！！！。逆序的从hash 表里面提取buckets
*data = (void*) ((buckets->count==1) ? buckets->elements.one : buckets->elements.many[state->j]);
return YES;
};
网友评论