OC数据结构03：哈希表的探索

哈希表定义

• 哈希表（hash table，也叫散列表），是根据 键（key） 直接访问在内存存储位置的数据结构。也就是说，它通过 把关键码值映射到表中一个位置来访问记录，以加快查找速度，这个 映射函数 叫做 散列函数，存放记录的数组叫做散列表。

• 给定一个 键key，存在 函数f(x) 和 表M，将 键key 代入 函数f(key)，若能得到 包含键key记录在表中的地址，则称 表M为哈希（Hash）表，函数f(key)为哈希(Hash)函数

哈希冲突定义

• 对不同的 key 可能得到同一个 哈希地址，即 k1≠k2，而f(k1)=f(k2)，这种现象称为哈希冲突，即 不同的key 经过 hash 处理后都可能得到相同的 hash 值。

哈希表的本质

• 哈希表本质是一个 数组，数组中每一个元素称为 箱子，箱子中存放的是 键值对，根据 下标index 从数组中取 value。关键是如何获取 index，这就需要一个固定的函数（哈希函数），将 key 转换为 index

哈希查找步骤

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

常用哈希函数

• 哈希查找第一步就是使用哈希函数将 键 映射成 索引，这种映射函数就是哈希函数。

• 如果有一个保存 M个元素的 数组，那么就需要一个能够将任意键转换为该数组范围内的索引（0 ~ M-1）的哈希函数，哈希函数需要易于计算并且能够均匀分布所有键。

• 在实际中，我们的键并不都是数字，有可能是字符串，还有可能是几个值的组合等，所以需要实现自己的哈希函数：

  • 直接寻址法：哈希函数为线性函数， f(k)=ak+b，a和b为常数

  • 数字分析法；

  • 平方取中法：将关键字平方以后取中间几位

  • 折叠法：先按照一定规则拆分再组合，例如书的索引ISBN 978-7-121-33637-9，可以拆合为97+87+12+13+36+37+9=291，哈希值为291

  • 随机数法：选择一个随机函数，把关键字的随机函数值作为它的哈希值。通常当关键字的长度不等时用这种方法。

  • 除留余数法：f(k)=k%n，假设哈希表的长度为m，则n一般为不超过m的最大质数，用于关键字位数较多，并且关键字中每一位上数字分布大致均匀。

哈希函数的特征

• 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）；

• 对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同；

• 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小；

• 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。

哈希碰撞冲突的解决方法

哈希碰撞冲突 就是对于不同的关键字，经过哈希函数计算以后的哈希值相同。

1. 开放寻址法：使用数组中的空位解决碰撞，当碰撞发生时（即一个键的hash值对应数组的下标被另外一个键占用）直接将下标索引加一（inde += 1），这样出现三种情况：

   • 未命中（数组下标中的值为空，没有占用）：存入
   • 命中（数组下标中的值不为空，占用）：继续 index+=1 ，直到遇到没有占用的

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

3. 再散列法

不同的散列函数，地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间；

4. 建立一个公共溢出区

Apple方案选择

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

• @synchronized 使用的是 链地址法，链地址法多用于存储的数据是通用类型，能够被反复利用，就像 @synchronized 存储的是锁是一种无关业务的实现结构，程序运行时多个对象使用同一个锁的概率相当高，有效的节省了内存。

• weak 对象 associatedObject 采用的是开放定址法，开放定址线性探测法用于存储的数据是临时的，用完尽快释放，就像 associatedObject，weak。

Hash 在 iOS 中的应用分析

1. 关联对象 AssociatedObject 的底层实现采用的数据存储结构（Hash 表 + Hash 表）

关联对象采用的是 HashMap 嵌套 HashMap 的结构存储数据的，简单来说就是根据对象从第一个 HashMap 中取出存储对象所有关联对象的第二个 HashMap，然后根据属性名从第二个 HashMap 中取出属性对应的值和策略。

• 已知条件一：对象，因此引出第一个 HashMap（AssociationsHashMap），用一个能唯一代表对象的值作为 key，用存储对象的所有关联对象的结构（名字：值+策略）作为 value；

• 已知条件二：属性名字，因此引出第二个 HashMap（ObjectAssociationMap），用属性名字作为key，用属性名字对应的结构体（值+策略）作为 value。

2. weak 底层实现采用的数据存储结构 （Hash 表 + 数组）

weak 采用的是一个全局的 HashMap 嵌套数组的结构存储数据的，销毁对象（weak 指针指向的对象）的时候，根据对象从 HashMap 中找到存放所有指向该对象的 weak 指针的数组，然后将数组中的所有元素都置为 nil。

weak 的最大特点就是在对象销毁时，自动置 nil，减少访问野指针的风险，这也是设计 weak 的初衷。

方案设计实现好后，weak 指针置 nil 的基本步骤：

对象 dealloc 的时候，从全局的 HashMap 中，根据一个唯一代表对象的值作为 key，找到存储所有指向该对象的 weak 指针的数组；将数组中的所有元素都置为 nil。

3. KVO 底层实现采用的数据存储结构（Hash 表 + 数组）

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

4. iOS App 签名的原理（MD5 + 哈希表 + 非对称加密 RSA）

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

• 数字签名：传递数据时会将原始的数据和数字签名一起发送，对方拿到数据后，通过同样的 Hash 算法得到原始数据的 Hash 的值，然后通过非对称加密，将数字签名中的校验 Hash 值解密出来，最后对比两个 Hash 值是否一致。

• 代码签名：代码签名就是对可执行文件或脚本进行数字签名，用来确认软件在签名后未被修改或损坏的措施。它的原理和数字签名类似，只不过把签名的不是数据，而是代码。

1. 对象的引用计数存储的位置（Hash 表）

2. NSDictionary 的实现原理（Hash 表）

3. Runloop 与 线程 的存储关系

• 线程和 Runloop 之间是一一（子线程可以没有）对应的，其关系是保存在一个全局的 Dictionary 里。

• Runloop 保存在一个 全局的可变字典 中，key 是 pthread_t，value 是 cfrunloopref，即 Hash 表。