哈希表及在iOS中的应用

哈希表和哈希函数

哈希表（Hash table，也叫散列表），是根据关键码值而直接进行访问的数据结构，是一块连续的存储空间。

记录的存储位置=f(关键字)

这里的对应关系f称为哈希函数（散列函数），采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash table）。所以哈希表的关键就是哈希函数。

哈希函数的特征

1.不能通过哈希值反推到原始数据

2.对关键字敏感，即使关键字只有微小的不同，哈希值也会很不一样

3.冲突小，即针对不同的关键字，生成的哈希值相同的概率小

4.执行效率高，对于大量的访问哈希表的数据，也需要很快的计算出对应表中的位置

哈希函数常用设计

1.直接定址法：哈希函数为线性函数，eg: f(k)=ak+b，a和b为常数

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

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

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

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

哈希函数的冲突解决

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

解决冲突的常用方法：
1.开放定址法：使用某种探查(亦称探测)技术在散列表中寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到。

2.链地址法：哈希值相同的数据放在同一线性链表中

例如下面图上对需要储存的数据%11，那么12、23、34取余结果都一样是1，则采用链表的结构放在地址为1的空间，查找的时候通过哈希函数找到地址是1的链表，向后查找即可

哈希在OC中的应用

NSDictionary

1.使用 hash表来实现key和value之间的映射和存储

2.字典的key需要遵循NSCopying协议，重写hash和isEqual方法，如果不重写，hash方法默认返回对象的地址，两个值相同的对象地址不同在存储过程中会生成两个key，取值的时候调用isEqual也是通过地址判断，地址不同会取不到值。

3.NSString类作为key的时候不需要重写，系统已经重写过了，对于值相同的字符串得到的哈希值相同

NSDictionary实现原理

iOS底层原理：NSDictionary原理

runloop

kvo

weak指针

全局HashMap，用来储存某个对象的所有weak指针，key是所指对象的指针，value是weak指针的地址数组（一个对象可能被多个指针指向）

objc_clear_deallocating该函数的动作如下：

1、从weak表中获取废弃对象的地址为键值的记录

2、将包含在记录中的所有附有 weak修饰符变量的地址，赋值为nil

3、将weak表中该记录删除

4、从引用计数表中删除废弃对象的地址为键值的记录

APP签名，MD5加密