hash 表的定义

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

哈希表优缺点

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

哈希查找步骤

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

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

weak 采用的是一个全局的 hashmap 嵌套数组的结构存储数据的，销毁对象（weak 指针指向的对象）的时候，根据对象从 hashmap 中找到存放所有指向该对象的 weak 指针的数组，然后将数组中的所有元素都置为 nil； weak 的最大的特点就是在对象销毁的时候，自动置为nil，减少访问野指针的风向，这也是设计 weak 的初衷；方案设计好后，weak 指针置为 nil 的基本步骤：

1、对象 dealloc的时候，从全局的 hashmap 中，根据一个唯一代表对象的值作为 key，找到存储所有指向该对象的 weak 指针的数组； 2、将数组中所有元素都置为 nil 实现原理的概括

RunTime维护一个weak表，用于存储指向某个的所有 weak 指针。weak 表其实是一个hash 表，key是所指对象的地址，value是 weak 指针的地址（这个地址的值是所指对象的地址）数组； 实现原理可以概括为以下三步：

1、初始化时：runtime 会调用objc_initWeak函数，初始化一个新的 weak 指针指向对象的地址 （注意：objc_initWeak函数有一个前提条件：就是object必须是一个没有被注册为__weak对象的有效指针。而value则可以是null，或者指向一个有效的对象。） 2、添加引用时：objc_initWeak函数会调用objc_storeWeak()函数，objc_storeWeak()的作用是更新指针指向，创建对应的弱引用表； 3、释放时，调用clearDeallocation函数；clearDeallocating函数首先根据对象地址获取所有 weak 指针地址的数组，然后遍历这个数组把其中的数据设为 nil，最后把这个entry从 weak 表中删除，最后亲历对象的记录；