[iOS开发]iOS中的Hash

文章目录

• 前言
• • 关联对象的底层原理
  • weak的实现原理
  • KVO的实现原理
  • iOS App签名的原理
  • 对象引用计数存储的位置
  • Runloop与线程的存储关系
  • NSDictionary的原理
• 哈希表
• • 哈希表定义
  • 哈希表优缺点
  • 哈希查找步骤
  • 哈希表的存储过程
  • 哈希表的实现
  • 负载因子 = 总键值对数/数组的个数
  • 哈希冲突的解决方法
  • • 开散列
    • 闭散列
    • 再哈希法
    • 建立公共溢出区
    • 开闭散列二者的比较
    • • 拉链法的优点：
      • 拉链法的缺点：
      • 线性探测法的缺点
• NSDictionary

前言

天天听安卓的同学整Hash，猛的发现iOS也有很多底层原理也是Hash来实现的，好好学一下。

iOS中也用到了很多Hash表。

关联对象的底层原理

[iOS开发]Category、Extension和关联对象

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

问题：为什么关联对象没有weak属性？

weak的实现原理

weak底层原理

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

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

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

苹果对于weak的实现其实类似于通知的实现，指明谁（weak指针）要监听谁（赋值对象）什么事件（dealloc操作）执行什么操作（置nil）

KVO的实现原理

GNUstep KVC/KVO探索（二）：KVO的内部实现

iOS App签名的原理

一致性Hash算法 + 非对称加密算法

iOS App 签名的原理

对象引用计数存储的位置

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

Runloop与线程的存储关系

线程和Runloop之间是一一对应的关系，其关系是保存在一个全局的Dictionary里。

线程在刚创建是没有RunLoop,如果我们不主动获取，那他就一直都不会有。RunLoop的创建是发生在第一次获取时，RunLoop的销毁时发生在线程结束时。我们只能在一个线程内部获取其RunLoop。

NSDictionary的原理

学完Hash之后我们来学习具体的实现

哈希表

前面说了那么多的底层原理都与Hash表有关，我们来详细学一下哈希表

哈希表定义

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

哈希表优缺点

优点：把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。

缺点：哈希表通常是基于数组，数组创建后难于扩展。也没有一种简便的方法可以以任何一种顺序来遍历哈希表。

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

哈希查找步骤

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

哈希表的存储过程

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

哈希表的实现

哈希表的底层实际上是基于数组来存储的，当插入键值对时，并不是直接插入该数组中，而是通过对键进行Hash运算得到Hash值，然后和数组容量取模，得到在数组中的位置后再插入。取值时，先对指定的键求Hash值，再和容量取模得到底层数组中对应的位置，如果指定的键值与存贮的键相匹配，则返回该键值对，如果不匹配，则表示哈希表中没有对应的键值对。这样做的好处是在查找、插入、删除等操作可以做到 O ( 1 ) O(1) O(1)，最坏的情况是 O ( n ) O(n) O(n)，当然这种是最极端的情况，极少遇到。

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

负载因子是哈希表的一个重要属性，用来衡量哈希表的空/满成都，一定程度也可以体现查询的效率。负载因子越大，意味着哈希表越满，越容易导致冲突，性能也就越低。所以当负载因子大于某个常数（一般是0.75）时，哈希表将自动扩容。哈希表扩容是，一般会创建两倍于原来的数组长度。这个过程被称为重哈希(rehash)。

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

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

哈希冲突的解决方法

大类分为四种 开散列、闭散列、再哈希法、建立公共溢出区

开散列

开散列也叫链地址法，也叫拉链法、哈希桶。

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

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

Redis解决哈希冲突采用的也是拉链法。通过增量式扩容解决了java 8中的瞬时扩容导致的瞬时效率降低的缺点，同时拉链法的实现方式（新插入的键值对放在链表头部）带来了两个好处：
一、 头插法可以节省插入耗时。如果插到尾部，则需要时间复杂度为O(n)的操作找到链表的尾部，或者需要额外的内存地址来保存尾部链表的位置。
二、头插法可以节省查找耗时。最新插入的数据往往可能频繁的被查询。

闭散列

闭散列也叫开放地址法、线性探测法。

当发生哈希冲突时，且哈希表未满，可以通过探测的方法吧key存放在冲突位置的下一个位置中。

方法一：线性探测
从发生冲突的位置开始，一次向后探测，直到寻找到下一个空位置为止。当然这种方法比较简单，也有很大的缺陷，就是容易造成数据的堆积，使得关键字需要多次比较，这样以来就导致搜索效率低

方法二：二次探测

方法三：伪随机探测
建立一个伪随机数发生器（如 i = (i + p) % m），生成一个伪随机序列，并给定一个随机数做起点，每次加上这个伪随机数，++就可以了。

再哈希法

再哈希法其实很简单，就是再使用哈希函数去散列一个输入的时候，输出是同一个位置就再次哈希，直至不发生冲突位置

缺点：每次冲突都要重新哈希，计算时间增加。

建立公共溢出区

这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

开闭散列二者的比较 拉链法的优点：

与线性探测法相比，拉链法有如下几个优点：

• 处理冲突简单，且无堆积现象，即非同义词绝不会发生冲突，因此平均查找长度较短；
• 由于拉链法中各链表上的结点空间是动态申请的，所以更适合于造表钱无法确定表长的情况
• 线性探测法为减少冲突，要求装填因子较小，故当结点规模较大时会浪费很多空间。二拉链法中可取a>=1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间
• 在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放定址线性探测发构造的散列表，删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放定址线性探测发中，空地址单元(即开放地址)都是查找失败的条件。因此在用开放定址线性探测发处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

拉链法的缺点：

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

线性探测法的缺点

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

NSDictionary