iOS cache_t 的散列表原理（哈希表）
上篇我们提到，iOS 会将我们调用得方法放到我们当前的类对象的 cache_t 中，他是一个结构体，我们的方法是放在 struct bucket_t *_buckets;这个里面，他是一个散列表,以后我们调用的方法都会从这个散列表当中去查找。
散列表的原理（空间换时间）
我们来看下结构体
struct cache_t {
struct bucket_t *_buckets;
mask_t _mask;
mask_t _occupied;
系统是怎么做的呢？
比如我们现在要去调用 -(void)test;这个方法，但我们来查找方法的时候，前面我们提到，key就是sel，也就是 @selector(test),系统是通过 key&mask 的形式来生成索引的，mask 前面有提到是当前的 buckets 的长度减1，比如我们的长度为为5，当我们调用这个方法的时候，其实是这么做的 @selector(test) & mask(4) = 索引，会生成一个索引，比如生成索引为1，那么他就会去buckets取出来1位置的结构体，这就是我们以后调用的方法的结构体，不用循环遍历。
其实当我们调用方法的时候，比如上面的test方法，当我们要放到缓存里面的时候，系统就会通过 @selector(test) & mask 来生成一个索引，比如生成的索引为5，那么，就会直接将这个方法放到索引为5的位置里面，这样在我们取得时候，就可以精确的取出来了，那么前面的位置怎么办？前面的位置，系统会将 null 放进去，是不是很巧妙？加快了查找效率。
上面这种做法其实是空间换时间的一种方法，但是我们可以知道，通过这个 & mask,的运算，最后得到的索引值，一定是小于等于 mask 的值得，不信自己可以测试下看看。
经过运算之后，生成的索引一样怎么办？
这段代码为源码
bucket_t * cache_t::find(SEL s, id receiver)
{
assert(s != 0);
bucket_t *b = buckets();
mask_t m = mask();
mask_t begin = cache_hash(s, m);
mask_t i = begin;
do {
if (b[i].sel() == 0 || b[i].sel() == s) {
return &b[i];
}
} while ((i = cache_next(i, m)) != begin);
// hack
Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
cache_t::bad_cache(receiver, (SEL)s, cls);
}
这段代码什么意思呢？前面都能明白，我们直接看 dowhile就可以了，从代码中可以看到，当我们通过 hash 算法，算出一个index之后，如果我们的散列表中的这个位置为空或者这个位置的sel和我们传进来的sel一样，那么直接返回散列表中的这个位置的结构体，如果没找到相同的，也就是说，可能当前别的方法和我们mask进行hash运算生成的index形成了冲突，这个位置的方法，不是我们当前传进来的方法，那么怎么办呢？看源码
static inline mask_t cache_next(mask_t i, mask_t mask) {
return i ? i-1 : mask;
}
我们通过查看 cache_next 方法，这个方法一看就知道了，比如我们这时候 i 为 4，发现冲突，那么直接返回 i - 1，将新传进来的方法放到 3 的位置，如果减到0还找不到，那么就放到 mask 位置，也就是数组长度的最大值，相当于 append ，然后再重新查找，当我们 mask 的值发生变化的时候，比如扩容，系统会为我们扩容，并清空我们的散列表，重新来，扩容，相当于当前的容量 * 2，一开始我们的散列表是有预设值得，比如一开始上来，长度就为10，先用，发现不够，变成20，清空，扩容。
hash 表的原理其实就是 f(key)=index,给定一个值生成一个索引。
网友评论