哈希表
哈希表也叫散列表，是根据键值(Key value)而直接进行访问的数据结构。也就是说，它通过把键(Key)映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，映射函数得出的值叫哈希值或哈希码，存放记录的数组叫做哈希表。哈希表中存放数据占总空间比例叫做装填因子（负载因子）。
哈希函数的设计要达到输出值的平均分布化，这样能尽可能降低哈希冲突的概率。
一般情况下，哈希函数中输入值与输出值具有 N对1 关系。
哈希函数具有的特点：如果两个哈希码不同，则它们的键(Key)也一定不同。
该特点常用于优化比较两个对象是否相同，先判断hash码是否相同，若hash码不同则不需要进行对象比较。
哈希表优点：查找效率高，插入删除和查找时间复杂度为O(1)。
哈希表缺点：占用空间大，需要预留一定空间，否则哈希冲突概率会很大。哈希表无法记录插入顺序。
哈希冲突
哈希函数因为会N对1的关系，会触发哈希冲突。哈希冲突常见解决方式有有以下几种：
1. 开放寻址法
线性探测（偏移1，2，3..）
可能会导致数据堆积一起，降低插入删除和查找效率。
二次方探测（偏移1*1，2*2，3*3..）
相比线性探测不容易造成数据堆积，但当装填因子比较大时，可能会造成一次查询/插入中，同一位置多次被探测。
2. 拉链法
使用数组+链表解决哈希冲突问题。
开放寻址法缺点：
开放寻址法的缺点是在删除元素时，不能真的删除，否则会引起查找失败。需要在删除元素位置做个标记，代表该索引位置可以插入，但是搜索路过时不能中断搜索。
另一方面，开放寻址法因为在冲突时会占用其它哈希索引空间，所以扩容时装填因子不能太大。
哈希表扩容与缩容
当装填因子过大，会增大哈希冲突概率，需要对哈希表进行扩容，因此哈希表一般使用二级指针实现(iOS底层使用DisguisedPtr<void *>）。扩容时需要对所有数据进行重新映射（重哈希），一般每次空间*2。
当装填因子太小，且空间占用比较大，比如：if (装填因子 < 0.1 && num >1024) {缩容}。
哈希算法
哈希算法本质是一类安全性较高的哈希函数。Hash算法还具有一个特点，就是很难找到逆向规律。
哈希算法常用于密码安全领域，哈希算法中输入值与输出值具有 N对1 关系，常见的哈希算法包括MD5，SHA，CRC16，CRC32。
iOS中用到的哈希
1.StripedMap类（SideTables）
SideTables是个全局变量，是StripedMap（哈希表）类型。
StripedMap重载了[]，可通过下标的方式快速存取。
StripedMap事实上不是个常规的哈希表，我认为它可以叫做只读哈希表。它在创建之初就会以模版类型初始化满所有存储空间，且不支持修改和扩容。因此，模版类型传递指针是没有意义的。一般模版都设置为结构体，后续操作针对该结构体改值。
SideTables的哈希Key是对象地址addr，哈希函数是((addr >>4) ^ (addr >>9)) %StripeCount，Value是SideTable结构体。因此，SideTables存储着对象地址与SideTable的 N-1 关系。这样可以把对象信息分散到不同SideTable中，提升查找效率。
每个SideTable中存储一堆对象的弱引用表和引用计数表。
2. weak_table_t结构体
weak_table_t的哈希Key是对象地址，哈希函数如下：
static inline uint32_t ptr_hash(uint64_t key)
{
key ^= key >>4;
key *=0x8a970be7488fda55;
key ^=__builtin_bswap64(key);
return(uint32_t)key;
}
索引（下标） = 函数返回结果 & weak_table->mask
Value是weak_entry_t。weak_table_t可以通过对象指针快速找到对象存储的weak_entry_t。
weak_table_t可进行扩容与缩容。
当出现哈希冲突时，与weak_table_t配套的函数使用线性探测法查找。
每个weak_table_t中存储一堆对象的弱引用表。
3. weak_entry_t结构体
weak_entry_t只有当装载数据超过一定长度才会启用哈希表存储功能，out_of_line()返回是否启用哈希表。weak_entry_t的哈希Key是弱指针地址，value也是弱指针地址。哈希函数与weak_table_t相同。
weak_entry_t可进行扩容，不会进行缩容。
当出现哈希冲突时，与weak_entry_t配套的函数使用线性探测法查找。
每个weak_entry_t存储指向一个对象的所有弱指针地址（二级指针）。
4. RefcountMap类（DenseMap）
RefcountMap本质是DenseMap类按照指定模版typedef的类型。
RefcountMap的哈希Key是对象地址，Value是引用计数。
当value为0时，RefcountMap会自动清除这条记录。
当出现哈希冲突时，RefcountMap使用二次方探测法查找。
每个RefcountMap中存储一堆对象的引用计数。
5.StripedMap<SyncList>sDataLists
sDataLists是存储所有@synchronized锁的全局哈希表，key是@synchronized的参数。
6. StripedMap<spinlock_t> PropertyLocks
PropertyLocks是存储所有atomic锁的全局哈希表，key是属性生成的成员变量地址。
7. cache_t结构体
类对象的方法缓存cache_t使用哈希表存储bucket_t（sel+imp)，使用逆序线性探测（Index-1)解决哈希冲突。
cache_t扩容时会将所有方法缓存清空。
8. namedSelectors
static objc::ExplicitInitDenseSet<const char *> namedSelectors;
namedSelectors是个全局变量，存储所有的方法名SEL，内部结构是哈希表DenseMap。
9. AssociationsHashMap
typedef DenseMap<DisguisedPtr<objc_object>, ObjectAssociationMap> AssociationsHashMap;
AssociationsHashMap是AssociationsManager中存储所有关联对象的哈希表，内部结构是DenseMap。
10. [NSObject hash]
NSObject默认的hash方法是对象地址，即默认没有做优化。
uintptr_t_objc_rootHash(id obj)
{
return (uintptr_t)obj;
}
还有个方法isEqual:方法，NSObject默认实现返回该对象与参数对象指针地址是否相同。
hash方法的本质是该对象的哈希函数，需要子类去实现。hash方法主要有两个作用，这两个作用在NSDictionary和NSSet中体现出来。
1. 与isEqual:配合，优化比较
先调用hash方法进行比较，若值相同才调用isEqualTo:进行比较。这依赖于hash的 N-1 关系。
从CF源码中可以找到CFString的源码，即可以看到NSString内部重写的hash方法。
/* String hashing: Should give the same results whatever the encoding; so we hash UniChars.If the length is less than or equal to 96, then the hash function is simply the following (n is the nth UniChar character, starting from 0): hash(-1) = length hash(n) = hash(n-1) * 257 + unichar(n); Hash = hash(length-1) * ((length & 31) + 1)If the length is greater than 96, then the above algorithm applies to characters 0..31, (length/2)-16..(length/2)+15, and length-32..length-1, inclusive;thus the first, middle, and last 32 characters.Note that the loops below are unrolled; and: 257^2 = 66049; 257^3 = 16974593; 257^4 = 4362470401; 67503105 is 257^4 - 256^4If hashcode is changed from UInt32 to something else, this last piece needs to be readjusted. !!! We haven't updated for LP64 yetNOTE: The hash algorithm used to be duplicated in CF and Foundation; but now it should only be in the four functions below.Hash function was changed between Panther and Tiger, and Tiger and Leopard.*/
这句话的大意是：这个字符串的大小如果小于等于96，则保证哈希的安全；如果大小大于96，则会大幅度增加哈希冲突的概率。
2. 与哈希表配合，hash方法对应哈希表的哈希函数，但返回值需要经过转换对应存储索引（一般通过取余）。此时hash方法的设计就非常重要，应做到输出哈希码的平均分散化，否则会导致数据堆叠，增大哈希冲突概率。
常见的NSDictionary和NSSet内部就是哈希表，NSDictionary会使用Key作为哈希表的Key，NSSet使用元素作为Key。它们会对Key对象调用hash方法获得初步的哈希码，然后经过转变成为存储区域的索引（下标）。
NSDictionary和NSSet因为都使用哈希表存储，因此存储元素都是无序的。
NSDictionary和NSSet在插入新元素时具体步骤如下：
1. 插入新元素时，首先会调用hash方法再经过转换获得最终存储的索引（下标）。
2. 若该位置已经存在元素，则调用isEqual:方法和该位置的元素比较，若相同则替换，结束。若不同进入步骤3。若该位置不存在元素，则直接插入该元素，结束。
3. 找到下一个位置，重复步骤2。
注：两个相同元素指isEqual:返回true，而不是地址相同。
