iOS散列表缓存窥探

1.

1

2. 散列表（哈希表）是以空间换时间.

刚开始为cache_t分配一定的内存, 如10, 当内存不够用时, 内存扩大2倍, 依次类推

3. 表格大概如下:

2

• 左边是索引, 右边是 bucket_t 结构体

• 如上图所示, bucket_t包括 _key 与 IMP, _key 就是SEL

4.iOS arm64 散列表存储原理:

• 1. 初始时, 为对象的cach_t分配一个空间, 值为NULL
• 2. 调用方法时, 为对象发送一个 SEL 消息, 如 @selector(personTest), 将这个方法缓存
• 3. 系统用 SEL 与 _mask 作按位与计算: @selector(personTest) & _mask , 假设其值==2,
• 4. 检查索引2 对应的空间是否为NULL , 如果为NULL 就将这个bucket_t 缓存在索引2对应空间
• 5. 如果不为空, 索引减1, 再检查是否为NULL, 依次类推. 如果索引<0, 则使索引 =_mask - 1, 直至找到索引对应空间为NULL, 再缓存

5. 对应的查找步骤:

• 1. 调用方法时, 为对象发送一个 SEL 消息, 如 @selector(personTest)
• 2. 系统用SEL 与 _mask 作按位与计算: @selector(personTest) & _mask , 假设其值==2,
• 3. 得到索引2 的bucket_t , 判断其中的 SEL 是否与传过来的 SEL 相同, 如果相同, 这个_imp就是寻找的方法
• 4. 如果不相同, 索引减1, 再比较SEL, 依次类推. 如果索引<0, 则使索引 = _mask - 1, 直至找到_imp

6. 为什么按位&_mask?

按位与 可保证得到的值 <= _mask, 这样就不会超出分配的空间.

注: 有的系统是求余 %, 如java, 这样也能保证 <= _mask

7. 为什么有 -1 的算法, 也是因为按位与, 因为不同的值 & _mask, 可能结果相同. 如果已经被占了, 就-1:

3

8. 如果空间超出原来的_mask, 则 _mask *= 2.

每一次_mask 扩容, 散列表清空, 只留下一个方法占用, 是导致它扩容的方法.

• 1. 源码:

4

• 2. 实例:

5

9.打印散列表:

9.1 9.2

• 1. 可看到有的空间为NULL

10. 测试 & _mask 得到方法:

10.1

打印:

10.2

注: selector 转化成数字类型才能 & , 所以强转成 long long.

11. 将地址 转化 成方法名:

11