散列表-OC方法缓存

1、散列表

• 散列表（Hash table，也叫哈希表), 是根据关键码值(Key value)而直接进行访问的数据结构. 也就是说，它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度.这个映射函数叫做散列函数,存放记录的数组叫做散列表.

2、OC方法缓存

• oc的方法缓存结构如下图:

  
  缓存结构体.jpg

散列表.jpeg

3、OC散列表原理

• 首先生成一个空的数组如下图:

空的散列表.jpg

• 存取数据

比如我们有一个方法
- (void)cacheMethd {
}

key = @selector(cacheMethd) // 方法名
_mask                                          //  常量
index = @selector(cacheMethd) & _mask;
算出来比如说index = 2
存取数据都是通过算出数组下标  来存储或者获取数据

image.png

• 哈希冲突

// 存数据
如果index = @selector(cacheMethd) & _mask;
算出来的index已经存在数据

while(bucket[index]) {
       index --;
       if(index < 0) {
            index = 数组count - 1;
        }
}

// 取数据
算出index = @selector(cacheMethd) & _mask;
取出bucket_t

对比key是否相等
相等直接返回
不等
while(bucket[index]) {
       index --;
       if(index < 0) {
            index = 数组count - 1;
        }
}
继续判读