一、哈希表定义

• 哈希表（hash table，也叫散列表），是根据键（key）直接访问访问在内存储存位置的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度，这个映射函数叫做散列函数，存放记录的数组叫做散列表。
• 给定表 M，存在函数 f（key），对任意给定的关键字值 key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表 M 为哈希（Hash）表，函数f（key）为哈希（Hash）函数。
• 若关键字为 k，则其值存放在 f(k) 的存储位置上，由此不需比较便可直接取得所查记录，称这个对应关系 f 为散列函数，按这个思想建立的表为散列表。
• 对不同的关键字可能得到同一散列地址，即 k1≠k2，而 f(k1)=f(k2)，这种现象称为冲突（英译：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。
• 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。
• 哈希表本质是一个数组，数组中的每一个元素成为一个箱子，箱子中存放的是键值对，根据下标 index 从数组中取 value。关键是如何获取 index，这就需要一个固定的函数（哈希函数），将 key 转换成 index。
• 不论哈希函数设计的如何完美，都可能出现不同的 key 经过 hash 处理后得到相同的 hash 值，这时候就需要处理哈希冲突。

二、哈希表优缺点

• 优点：哈希表可以提供快速的操作。
• 缺点：
• • 哈希表通常是基于数组的，数组创建后难于扩展；
• • 没有一种简便的方法可以以任何一种顺序〔例如从小到大）遍历表中的数据项。
• 综上，如果不需要有序遍历数据，井且可以提前预测数据量的大小，那么哈希表在速度和易用性方面是无与伦比的。

三、哈希查找步骤

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

四、哈希表存储过程

• 使用 hash 函数根据 key 得到哈希值 h；
• 如果箱子的个数为 n，那么值应该存放在底(h%n)个箱子中，h%n 的值范围为 [0, n-1]；
• 如果该箱子非空（已经存放了一个值）即不同的 key 得到了相同的h产生了哈希冲突，此时需要使用拉链法或者开放定址线性探测法解决冲突。

五、常用哈希函数

• 哈希查找第一步就是使用哈希函数将键映射成索引，这种映射函数就是哈希函数。
• 如果有一个保存 0 ~ M 数组，那么就需要一个能够将任意键转换为该数组范围内的索引（0 ~ M-1）的哈希函数，哈希函数需要易于计算并且能够均匀分布所有键。
• 举个简单的例子，使用手机号码后三位就比前三位作为 key 更好，因为前三位手机号码的重复率很高；再比如使用身份证号码出生年月位数要比使用前几位数要更好。
• 在实际中，我们的键并不都是数字，有可能是字符串，还有可能是几个值的组合等，所以需要实现自己的哈希函数：
• • 直接寻址法；
• • 数字分析法；
• • 平方取中法；
• • 折叠法；
• • 随机数法；
• • 除留余数法。
• 要想设计一个优秀的哈希算法并不容易，根据经验，总结了需要满足的几点要求：
• • 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）；
• • 对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同；
• • 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小；
• • 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。

六、负载因子

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

七、哈希表扩容

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

八、哈希冲突的解决方法

① 拉链法

• 简单来说就是数组 + 链表，将键通过 hash 函数映射为大小为 M 的数组的下标索引，数组的每一个元素指向一个链表，链表中的每一个结点存储着 hash 出来的索引值为结点下标的键值对。
• Java 8 解决哈希冲突采用的就是拉链法，在处理哈希函数设计不合理导致链表很长时（链表长度超过 8 切换为红黑树，小于 6 重新退化为链表），将链表切换为红黑树能够保证插入和查找的效率，缺点是当哈希表比较大时，哈希表扩容会导致瞬时效率降低。
• Redis 解决哈希冲突采用的也是拉链法，通过增量式扩容解决了 Java 8 中的瞬时扩容导致的瞬时效率降低的缺点，同时拉链法的实现方式（新插入的键值对放在链表头部）带来了两个好处：
• • 头插法可以节省插入耗时，如果插到尾部，则需要时间复杂度为 O(n) 的操作找到链表尾部，或者需要额外的内存地址来保存尾部链表的位置；
• • 头插法可以节省查找耗时，对于一个数据系统来说，最新插入的数据往往可能频繁的被查询。
• 与开放定址线性探测发相比，拉链法有如下几个优点：
• • 拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
• • 由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
• • 开放定址线性探测法为减少冲突，要求装填因子 α 较小，故当结点规模较大时会浪费很多空间。而拉链法中可取 α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
• • 在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放定址线性探测发构造的散列表，删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放定址线性探测发中，空地址单元(即开放地址)都是查找失败的条件。因此在用开放定址线性探测发处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。
• 拉链法的缺点：指针需要额外的空间，故当结点规模较小时，开放定址线性探测发较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址线性探测发中的冲突，从而提高平均查找速度。

② 开放定址线性探测法

• 使用两个大小为 N 的数组（一个存放 keys，另一个存放 values），使用数组中的空位解决碰撞，当碰撞发生时（即一个键的 hash 值对应数组的下标被两外一个键占用）直接将下标索引加一（index += 1），这样会出现三种结果：
• • 未命中（数组下标中的值为空，没有占用）：keys[index] = key，values[index] = value；
• • 命中（数组下标中的值不为空，占用）：keys[index] == key，values[index] == value；
• • 命中（数组下标中的值不为空，占用）：keys[index] != key，继续 index += 1，直到遇到结果 1 或 2 停止。
• 开放定址线性探测法缺点
• • 容易产生堆积问题；
• • 不适于大规模的数据存储；
• • 散列函数的设计对冲突会有很大的影响；
• • 插入时可能会出现多次冲突的现象，删除的元素是多个冲突元素中的一个，需要对后面的元素作处理，实现较复杂；
• • 结点规模很大时会浪费很多空间。

③ 再散列法

• Hi=RHi(key),i=1,2，…，k RHi 均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间；

④ 建立一个公共溢出区

九、Hash 表的平均查找长度

• Hash 表的平均查找长度包括查找成功时的平均查找长度和查找失败时的平均查找长度：
• • 查找成功时的平均查找长度=表中每个元素查找成功时的比较次数之和/表中元素个数；
• • 查找不成功时的平均查找长度相当于在表中查找元素不成功时的平均比较次数，可以理解为向表中插入某个元素，该元素在每个位置都有可能，然后计算出在每个位置能够插入时需要比较的次数，再除以表长即为查找不成功时的平均查找长度。
• 给定一组数据 {32，14，23，01，42，20，45，27，55，24，10，53}，假设散列表的长度为 13（最接近 n 的质数），散列函数为 H(k) = k，分别画出用“线性探测法”和“拉链法”解决冲突时构造的哈希表，并求出在等概率下情况，这两种方法查找成功和查找不成功的平均查找长度。
• • 拉链法：
• • • 查找成功时的平均查找长度：ASL = (16 + 24 + 31 + 41)/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。

十、Apple 方案选择

• 解决哈希冲突的拉链法和开放定址线性探测法，Apple 都在使用，具体使用哪一种是根据存储数据的生命周期和特性决定的：
• • @synchronized 使用的是拉链法，拉链法多用于存储的数据是通用类型，能够被反复利用，就像@synchronized 存储的是锁是一种无关业务的实现结构，程序运行时多个对象使用同一个锁的概率相当高，有效的节省了内存。
• • weak 对象 associatedObject 采用的是开放定址线性探测法，开放定址线性探测法用于存储的数据是临时的，用完尽快释放，就像 associatedObject，weak。

十一、字符串的 hash 方法

• [NSString hash] 出现同样的 hash 值问题：

At least there are special circumstances for which this unreliability kicks in.

Comparing [a hash] and [b hash] of two different NSString is safe when:

the strings' length is shorter or equal to 96 characters.
[a length] is different to [b length].
the concatinated first, middle, and last 32 characters of a differ to the concatinated components of b.
Otherwise every difference between the first and the middle 32 chars, as well as every difference between the middle and the last 32 characters, are not used while producing the [NSString hash] value.

• [NSString hash] 这个方法对 <=96 个字符的字符串是安全的，如果比 96 个字符长，会大大增加碰撞的概率：

#define HashEverythingLimit 96

#define HashNextFourUniChars(accessStart, accessEnd, pointer) \
    {result = result * 67503105 + (accessStart 0 accessEnd) * 16974593  + (accessStart 1 accessEnd) * 66049  + (accessStart 2 accessEnd) * 257 + (accessStart 3 accessEnd); pointer += 4;}

#define HashNextUniChar(accessStart, accessEnd, pointer) \
    {result = result * 257 + (accessStart 0 accessEnd); pointer++;}

CF_INLINE CFHashCode __CFStrHashCharacters(const UniChar *uContents, CFIndex len, CFIndex actualLen) {
    CFHashCode result = actualLen;
    // ****X 这里HashEverythingLimit = 96
    if (len <= HashEverythingLimit) {
        // ****X 若字符串长度在96以内，对所有的字符做hash运算得到一个结果
        
        const UniChar *end4 = uContents + (len & ~3);
        const UniChar *end = uContents + len;
        while (uContents < end4) HashNextFourUniChars(uContents[, ], uContents);    // First count in fours
        while (uContents < end) HashNextUniChar(uContents[, ], uContents);      // Then for the last <4 chars, count in ones...
    } else {
        // ****X 若字符串长度超过96
        
        const UniChar *contents, *end;
        // ****X 取前32个字符做hash运算
    contents = uContents;
        end = contents + 32;
        while (contents < end) HashNextFourUniChars(contents[, ], contents);
        // ****X 取中间32个字符做hash运算
    contents = uContents + (len >> 1) - 16;
        end = contents + 32;
        while (contents < end) HashNextFourUniChars(contents[, ], contents);
        // ****X 取最后32个字符做hash运算
    end = uContents + len;
        contents = end - 32;
        while (contents < end) HashNextFourUniChars(contents[, ], contents);
    }
    return result + (result << (actualLen & 31));
}

• 如果长度大于 96，只有前、中、后 32 个字符做了哈希运算，也就是说在这些字符相同的情况下，其他任意位置的字符发生改变，Hash 值都不会变。
• 在工程中使用字符串的 hash 方法作为数据是否发生改变的依据，发现方法返回的 hash 值为一个很大的负数，这是因为数值大小超出了数据类型能够表达的范围。可以使用 md5 算法代替系统的 hash 算法。

十二、Hash 在 iOS 中的应用分析

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

• 关联对象采用的是 HashMap 嵌套 HashMap 的结构存储数据的，简单来说就是根据对象从第一个 HashMap 中取出存储对象所有关联对象的第二个 HashMap，然后根据属性名从第二个 HashMap 中取出属性对应的值和策略。
• 设计关联对象的初衷：通过传入对象 + 属性名字，就可以找到属性值，方案设计实现好后，查找一个对象的关联对象的基本步骤：
• • 已知条件一：对象，因此引出第一个 HashMap（AssociationsHashMap），用一个能唯一代表对象的值作为 key，用存储对象的所有关联对象的结构（名字：值+策略）作为 value；
• • 已知条件二：属性名字，因此引出第二个 HashMap（ObjectAssociationMap），用属性名字作为key，用属性名字对应的结构体（值+策略）作为 value。

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

• weak 采用的是一个全局的 HashMap 嵌套数组的结构存储数据的，销毁对象（weak 指针指向的对象）的时候，根据对象从 HashMap 中找到存放所有指向该对象的 weak 指针的数组，然后将数组中的所有元素都置为 nil。
• weak 的最大特点就是在对象销毁时，自动置 nil，减少访问野指针的风险，这也是设计 weak 的初衷。
• 方案设计实现好后，weak 指针置 nil 的基本步骤：
• • 对象 dealloc 的时候，从全局的 HashMap 中，根据一个唯一代表对象的值作为 key，找到存储所有指向该对象的 weak 指针的数组；
• • 将数组中的所有元素都置为 nil。
• 深入了解请参考：iOS之深入解析weak关键字的底层原理。

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

• 一个对象可以被 n 个对象观察，一对象的 n 个属性又可以分别被 n 个对象观察。
• 深入了解请参考：iOS之深入解析KVO的底层原理。

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

• 一致性哈希算法 + 非对称加解密算法：
• • 数字签名：传递数据时会将原始的数据和数字签名一起发送，对方拿到数据后，通过同样的 Hash 算法得到原始数据的 Hash 的值，然后通过非对称加密，将数字签名中的校验 Hash 值解密出来，最后对比两个 Hash 值是否一致。
• • 代码签名：代码签名就是对可执行文件或脚本进行数字签名，用来确认软件在签名后未被修改或损坏的措施。它的原理和数字签名类似，只不过把签名的不是数据，而是代码。
• 深入了解请参考：iOS逆向之深入解析App签名的双向验证机制和原理。

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

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

• 深入了解请参考：
• • iOS之深入解析内存管理的引用计数retainCount的底层原理；
• • iOS之深入解析内存管理散列表SideTables和弱引用表weak_table的底层原理。

⑥ NSDictionary 的实现原理（Hash 表）

• NSMapTable 实现：
• • 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 存放到链表中，遍历链表的时间。
• • 上面的结论和对应的解释似乎很合理？下面我们继续分析。
• _CFDictionary 封装：
  – 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 在使用过程中总是会很快的被释放，不会长期占用内存。
• NSDictionary 的存储过程：
• • 通过方法 - (void)setObject:(id)anObject forKey:(id)aKey; 可以看出 key 必须遵循 NSCopy 协议，也就是说 NSDictionary 的 key 是 copy 一份新的，而 value 是浅拷贝的（如果想深拷贝可以使用 NSMapTable）。
• • key 还必须要继承 NSObject，并且重写 -(NSUInteger)hash; 和 -(BOOL)isEqual:(id)object; 两个方法：
• • • 第一个函数用于计算 hash 值；
• • • 第二个函数用来判断当哈希值相同的时候 value 是否相同（解决哈希冲突）。

⑦ Runloop 与线程的存储关系

• 线程和 Runloop 之间是一一（子线程可以没有）对应的，其关系是保存在一个全局的 Dictionary 里。
• 线程刚创建时并没有 Runloop，如果你不主动获取，那它一直都不会有。
• Runloop 的创建是发生在第一次获取时，Runloop 的销毁是发生在线程结束时，只能在一个线程的内部获取其 Runloop（主线程除外）。
• Runloop 保存在一个全局的可变字典中，key 是 pthread_t，value 是 cfrunloopref，即 Hash 表。
• 深入了解请参考：iOS之深入解析Runloop的底层原理。