搞iOS的，面试官问Hash干嘛？原因远比我下面要介绍的多

在 iOS开发中 随处可见 Hash 的身影，难道我们不好奇吗？

下图只是列出了部分知识点（ Hash 在iOS中的应用分析整理）

摘自知乎的一句话：

算法、 数据结构 、 通信协议 、 文件系统 、 驱动 等，虽然自己不写那些东西，但是 了解其原理 对于 排错 、 优化自己的代码 有很大帮助，就好比虽然你不设计制造汽车，但如果你了解发动机、变速器、安全气囊等几项原理，对于你驾车 如何省油 、 延长使用寿命 、 保证自身安全 有很大好处学而不思则罔、思而不学则殆，开发人员就是个随波而进的行业，无论何时何地， 保持学习的深度和广度 对于自身发展是很重要的，谁都不想60岁退休了还停留在 增删查改 的层面。

1.1、关联对象的实现原理：

详细的原理可以查阅其他资料，这里只介绍一下实现中使用的基本数据结构。关联对象采用的是 HashMap 嵌套 HashMap 的结构存储数据的，简单来说就是根据对象从第一个 HashMap 中取出存储对象所有关联对象的第二个 HashMap ，然后根据属性名从第二个 HashMap 中取出属性对应的值和策略。

参考资料：

iOS底层原理总结 - 关联对象实现原理 关联对象 AssociatedObject 完全解析

1.2、weak的实现原理：

同样详细的原理可以查阅其他资料，这里只介绍一下实现中使用的基本数据结构。 weak 采用的是一个全局的 HashMap 嵌套数组的结构存储数据的，销毁对象（ weak 指针指向的对象）的时候，根据对象从 HashMap 中找到存放所有指向该对象的 weak 指针的数组，然后将数组中的所有元素都置为nil。

参考资料：

iOS 底层解析weak的实现原理（包含weak对象的初始化，引用，释放的分析） weak实现原理

1.3、KVO实现使用的基本数据结构

比较复杂，一个对象可以被n个对象观察，一对象的n个属性又可以分别被n个对象观察。

详细参考： GNUstep KVC/KVO探索（二）：KVO的内部实现

1.4、iOS App签名的原理

一句话： 一致性哈希算法 + 非对称加解密算法

详细参考： iOS App 签名的原理

1.5、对象的引用计数存储的位置

具体参考： 苹果iOS系统源码思考：对象的引用计数存储在哪里？--从runtime源码得到的启示

if 对象支持TaggedPointer {
	return 直接将对象的指针值作为引用计数返回
} 
else if 设备是64位环境 && Objective-C2.0 {
	return 对象isa指针的一部分空间(bits_extra_rc)
}
else {
	return hash表
}
复制代码

1.6、Runloop与线程的存储关系

线程和 RunLoop 之间是一一（ 子线程可以没有 ）对应的，其关系是保存在一个全局的 Dictionary 里。线程刚创建时并没有 RunLoop ，如果你不主动获取，那它一直都不会有。 RunLoop 的创建是发生在第一次获取时， RunLoop 的销毁是发生在线程结束时。你只能在一个线程的内部获取其 RunLoop （主线程除外）。

1.7、NSDictionary的原理：

解释完Hash表后，下面简单解释下

二、哈希表

桶排序

2.1、哈希表定义

哈希表 （ hash table ，也叫散列表），是根据键（ key ）直接访问访问在内存储存位置的数据结构。 哈希表本质是一个数组，数组中的每一个元素成为一个箱子，箱子中存放的是键值对。根据下标 index 从数组中取 value 。关键是如何获取 index ，这就需要一个固定的函数（哈希函数），将 key 转换成 index 。不论哈希函数设计的如何完美，都可能出现不同的 key 经过 hash 处理后得到相同的 hash 值，这时候就需要处理哈希冲突。

2.2、哈希表优缺点

优点：哈希表可以提供快速的操作。

缺点：哈希表通常是基于数组的，数组创建后难于扩展。 也没有一种简便的方法可以以任何一种顺序〔例如从小到大）遍历表中的数据项。

综上，如果不需要有序遍历数据，井且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

2.3、哈希查找步骤

• - 1、使用哈希函数将被查找的键映射（转换）为数组的索引，理想情况下（hash函数设计合理）不同的键映射的数组下标也不同，所有的查找时间复杂度为O(1)。但是实际情况下不是这样的，所以哈希查找的第二步就是处理哈希冲突。

• - 2、处理哈希碰撞冲突。处理方法有很多，比如拉链法、线性探测法。

2.4、哈希表存储过程：

• - 1、使用hash函数根据key得到哈希值h

• - 2、如果箱子的个数为n，那么值应该存放在底(h%n)个箱子中。h%n的值范围为[0, n-1]。

• - 3、如果该箱子非空（已经存放了一个值）即不同的key得到了相同的h产生了哈希冲突，此时需要使用拉链法或者开放定址线性探测法解决冲突。

hash("张三") = 23;
hash("李四") = 30;
hash("王五") = 23;
复制代码

2.5、常用哈希函数：

2.6、负载因子 = 总键值对数/数组的个数

负载因子是哈希表的一个重要属性，用来衡量哈希表的空/满程度，一定程度也可以提现查询的效率。负载因子越大，意味着哈希表越满，越容易导致冲突，性能也就越低。所以当负载因子大于某个常数（一般是0.75）时，哈希表将自动扩容。哈希表 扩容 时，一般会创建两倍于原来的数组长度。因此即使key的哈希值没有变化，对数组个数取余的结果会随着数组个数的扩容发生变化，因此键值对的位置都有可能发生变化，这个过程也成为 重哈希 （ rehash ）。

哈希表扩容在数组比较多的时候，需要重新哈希并移动数据，性能影响较大。

哈希表扩容虽然能够使负载因子降低，但并不总是能有效提高哈希表的查询性能。比如哈希函数设计的不合理，导致所有的 key 计算出的哈希值都相同，那么即使扩容他们的位置还是在同一条链表上，变成了 线性表 ，性能极低，查询的时候时间复杂度就变成了 O(n) 。

2.7、哈希冲突的解决方法：

方法一：拉链法

简单来说就是 数组 + 链表 。将键通过hash函数映射为大小为M的数组的下标索引，数组的每一个元素指向一个链表，链表中的每一个结点存储着hash出来的索引值为结点下标的键值对。

Java 8 解决哈希冲突采用的就是 拉链法 。在处理哈希函数设计不合理导致链表很长时（链表长度超过 8 切换为红黑树，小于 6 重新退化为链表）。将链表切换为红黑树能够保证插入和查找的效率，缺点是当哈希表比较大时， 哈希表扩容 会导致瞬时效率降低。

方法二：开放定址线性探测发

拉链法的优点

拉链法的缺点

指针需要额外的空间，故当结点规模较小时， 开放定址线性探测发 较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了 开放定址线性探测发 中的冲突，从而提高平均查找速度。

开放定址线性探测法缺点

• - 1、容易产生堆积问题；
• - 2、不适于大规模的数据存储；
• - 3、散列函数的设计对冲突会有很大的影响；
• - 4、插入时可能会出现多次冲突的现象，删除的元素是多个冲突元素中的一个，需要对后面的元素作处理，实现较复杂；
• - 5、结点规模很大时会浪费很多空间；

2.8、Hash表的平均查找长度

Hash表的 平均查找长度 包括 查找成功时的平均查找长度 和 查找失败时的平均查找长度 。

查找成功时的平均查找长度=表中每个元素查找成功时的比较次数之和/表中元素个数；

查找不成功时的平均查找长度相当于在表中查找元素不成功时的平均比较次数，可以理解为向表中插入某个元素，该元素在每个位置都有可能，然后计算出在每个位置能够插入时需要比较的次数，再除以表长即为查找不成功时的平均查找长度。

例子：

给定一组数据 {32，14，23，01，42，20，45，27，55，24，10，53} ，假设散列表的长度为13（最接近n的质数），散列函数为 H(k) = k%13 。分别 画出 用 线性探测法 和 拉链法 解决冲突时构造的哈希表，并求出在等概率下情况，这两种方法查找成功和查找不成功的平均查找长度。

一、拉链法

ASL = (1*6+2*4+3*1+4*1)/12 = 7/4
复制代码

查找不成功时的平均查找长度：

ASL = (4+2+2+1+2+1)/13
复制代码

二、线性探测法

查找成功时查找次数=插入元素时的比较次数， 查找成功的平均查找长度 ：

ASL = (1+2+1+4+3+1+1+1+3+9+1+1+3)/12=2.5
复制代码

查找不成功时的查找次数=第n个位置不成功时的比较次数为，第n个位置到第1个没有数据位置的距离：如第0个位置取值为1，第1个位置取值为2. 查找不成功时的平均查找长度：

ASL = （1+2+3+4+5+6+7+8+9+10+11+12）/ 13 = 91/13
复制代码

2.9、NSDictionary解释版本一：是使用 NSMapTable 实现的，采用 拉链法 解决哈希冲突

typedef struct {
   NSMapTable        *table;
   NSInteger          i;
   struct _NSMapNode *j;
} NSMapEnumerator;
复制代码

上述结构体描述了遍历一个 NSMapTable 时的一个指针对象，其中包含 table 对象自身的指针，计数值，和节点指针。

typedef struct {
   NSUInteger (*hash)(NSMapTable *table,const void *);
   BOOL (*isEqual)(NSMapTable *table,const void *,const void *);
   void (*retain)(NSMapTable *table,const void *);
   void (*release)(NSMapTable *table,void *);
   NSString  *(*describe)(NSMapTable *table,const void *);
   const void *notAKeyMarker;
} NSMapTableKeyCallBacks;
复制代码

上述结构体中存放的是几个函数指针，用于计算 key 的 hash 值，判断 key 是否相等， retain ， release 操作。

typedef struct {
   void       (*retain)(NSMapTable *table,const void *);
   void       (*release)(NSMapTable *table,void *);
   NSString  *(*describe)(NSMapTable *table, const void *);
} NSMapTableValueCallBacks;
复制代码

上述存放的三个函数指针，定义在对 NSMapTable 插入一对 key－value 时，对 value 对象的操作。

@interface NSMapTable : NSObject {
   NSMapTableKeyCallBacks   *keyCallBacks;
   NSMapTableValueCallBacks *valueCallBacks;
   NSUInteger             count;
   NSUInteger             nBuckets;
   struct _NSMapNode  **buckets;
}
复制代码

从上面的结构真的能看出 NSMapTable 是一个 哈希表 + 链表 的数据结构吗？在 NSMapTbale 中插入或者删除一个对象的寻找时间 = O(1) + O(m) ，m为最坏时可能为n。

O(1)：对 key 进行 hash 得到 bucket 的位置

O(m)：不同的 key 得到相同的 hash 值的 value 存放到链表中，遍历链表的时间

上面的结论和对应的解释似乎很合理？看看下面的分析再说也不迟！

2.10、NSDictionary解释版本二：是对_CFDictionary的封装，解决哈希冲突使用的是 开放定址线性探测法

struct __CFDictionary {
    CFRuntimeBase _base;
    CFIndex _count;
    CFIndex _capacity;
    CFIndex _bucketsNum;
    uintptr_t _marker;
    void *_context;
    CFIndex _deletes;
    CFOptionFlags _xflags;
    const void **_keys;	
    const void **_values;
};
复制代码

从上面的数据结构可以看出 NSDictionary 内部使用了两个 指针数组 分别保存 keys 和 values 。采用的是连续方式存储键值对。 拉链法 会将 key 和 value 包装成一个结果存储（链表结点），而 Dictionary 的结构拥有 keys 和 values 两个数组（ 开放寻址线性探测法 解决哈希冲突的用的就是两个数组），说明两个数据是被分开存储的，不像是 拉链法 。

NSDictionary使用开放定址线性探测法解决哈希冲突的原理：

可以看到， NSDictionary 设置的 key 和 value ， key 值会根据特定的hash函数算出建立的空桶数组， keys 和 values 同样多，然后存储数据的时候，根据 hash函数 算出来的值，找到对应的 index 下标，如果下标已有数据，开放定址法后移动插入，如果空桶数组到达 数据阀值 ，这个时候就会把 空桶数组扩容 ，然后重新哈希插入。

这样把一些不连续的 key-value 值插入到了能建立起关系的 hash 表中，当我们查找的时候， key 根据哈希>值算出来，然后根据索引，直接 index 访问 hash 表 keys 和 hash 表 values ，这样查询速度就可以和连续线性存储的数据一样接近 O(1) 了，只是占用空间有点大，性能就很强悍。

如果删除的时候，也会根据_maker标记逻辑上的删除，除非 NSDictionary （ NSDictionary 本体的 hash 值就是 count ）内存被移除。

NSDictionary 之所以采用这种设计， 其一出于查询性能的考虑； 其二 NSDictionary 在使用过程中总是会很快的被释放，不会长期占用内存;

2.11、Apple方案选择：

解决哈希冲突的拉链法和开放定址线性探测法，Apple都是用了。具体使用哪一种是根据存储数据的生命周期和特性决定的。

• @synchronized 使用的是 拉链法 。拉链法多用于存储的数据是通用类型，能够被反复利用，就像@synchronized存储的是锁是一种无关业务的实现结构，程序运行时多个对象使用同一个锁的概率相当高，有效的节省了内存。
• weak对象 associatedObject 采用的是 开放定址线性探测法 。开放定址线性探测法用于存储的数据是临时的，用完尽快释放，就像associatedObject，weak。