散列表中的方法缓存

Class内部结构中有个方法缓存(cache_t)

image.png

那么这个cache_t是什么呢?
源码中cache_t跟以前相比发生了很大的变化, 它的内存布局也用了联合体, 那得到内存的最大优化

image.png
cache_t第一个成员变量是:
_bucketsAndMaybeMask, 它是什么呢?
image.png

从上图中就可以看到, 注释中写道:

_bucketsAndMaybeMask is a buckets_t pointer

它是指向buckets_t的指针, cache_t()的建议构造函数(仅为测试用), 就简单地传了0, 表明指针地址从0开始, 仅供测试用
既然_bucketsAndMaybeMask是指向buckets_t的指针, 那么, buckets_t又是什么呢? 它就是缓存方法的散列表

这个结构体里声明了一些方法

image.png
其中有一些很关键的方法, 比如insert, 这个方法表明了底层是怎么往散列表里存数据的. 我们来简单看一下: image.png
首先, 是判断缓存是不是空的, 如果是空的, 就开辟一个初始空间大小的缓存空间.
如果空间没占满, 不管它, 程序继续运行
如果占满了, 就重新开辟2倍之前的空间, 并清空以前缓存中的数据, 最主要的函数就是reallocate:
image.png
上图的allocateBuckets方法先开辟内存空间, 然后将空间的内存地址返回.再调用方法setBucketsAndMask(newBuckets, newCapacity - 1);让结构体的_bucketsAndMaybeMask拿到那片内存空间的值. 你可以简单理解为这片内存空间的地址值就指向了散列表.

开辟内存空间之后:

image.png

先拿到散列表的地址, 就是调用buckets()函数:

image.png
可以理解为就是返回_bucketsAndMaybeMask的地址

然后拿到m变量, m的值就是散列表(数组)的容量-1,
然后将方法sel和m进行哈希, 得到一个初始值.

image.png

拿到这个初始值begin之后, 先去散列表中对应的元素中去找selector,

• 如果没找到, 就直接添加进去. 调用

b[i]. set<Atomic, Encoded> (b, sel, imp, cls());

将散列表地址, selector, 函数指针, 类对象都作为参数传进去, 也就是说, 散列表中存储了这些数据

• 如果找到了, 且从散列表中取出来的selector刚好就等于传进来的selector, 那就直接return, 因为不需要insert
• 如果没找到, 就调用cache_next函数, 拿到下一个不等于初始值begin的索引
  在arm64架构下, cache_next函数是这样实现的:
  image.png

直接i-1, 比如之前begin=6, 那么发现散列表索引6取出来的selector并不等于传进来的参数selector, 表明这个散列表位置已经占用了, 那就直接6-1, 索引5, 如果还是一样, 就一直取, 取到等于0, 发现还没有.那就直接将索引置为mask, 因为mask就是容量-1, 所以就相当于取了散列表的最后一个元素, 到目前为止, 就相当于把散列表整个遍历了一遍. 当然, 这是最不济的情况.

这是往散列表里存值的情况, 那么取值也是一样:
先将m和selector进行hash, 用hash过后的值作为索引, 去取散列表里存的值. 如果为空, 表明没有存值; 如果散列表里存的selector和传进来的selector一致, 表明找到;如果不一致, 表明产生了哈希碰撞, 重复了, 这个时候, 直接将索引值-1, 再去找. 一直找, 当索引等于0时还没找到, 就直接将索引值变成mask, 也就是容量-1. 这个时候就把散列表整个遍历了一遍. 当然, 这也是最不济的情况. 运气好, 第一次就能找到

这种方法就是用空间换取效率, 因为散列表里并不是每一个元素都存值了, 有的可能为空.

这种方法也叫做开放定址法.