1:哈希表 的数据结构，底层实现原理
底层实现：数组 + 链表
哈希表（Hash table，也叫散列表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表
白话一点的说就是通过把Key通过一个固定的算法函数（hash函数）转换成一个整型数字，然后就对该数字对数组的长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。
当使用hash表查询时，就是使用hash函数将key转换成对应的数组下标，并定位到该下标的数组空间里获取value，这样就充分利用到数组的定位性能进行数据定位。
先了解一下下面几个常说的几个关键字是什么：
key：我们输入待查找的值
value：我们想要获取的内容
hash值：key通过hash函数算出的值（对数组长度取模，便可得到数组下标）
hash函数（散列函数）：存在一种函数F，根据这个函数和查找关键字key，可以直接确定查找值所在位置，而不需要一个个遍历比较。这样就预先知道key在的位置，直接找到数据，提升效率。
即
地址index=F(key)
hash函数就是根据key计算出该存储地址的位置，hash表就是基于hash函数建立的一种查找表。
2:Hash函数的构造方法
方法
方法有很多种，比如直接定址法、数字分析法、平方取中法、折叠法、随机数法、除留余数法等，网上相关介绍有很多，这里就不重点说这个了
hash函数设计的考虑因素
计算hash地址所需时间（没有必要搞一个很复杂的函数去计算）
关键字的长度
表长
关键字分布是否均匀，是否有规律可循
尽量减少冲突
3:hash冲突
什么是hash冲突
对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，或f(k1) MOD 容量 =f(k2) MOD 容量，这种现象称为碰撞，亦称冲突。
通过构造性能良好的hash函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是hash表的另一个关键问题。
创建和查找hash表都会遇到冲突，两种情况下解决冲突的方法应该一致。
哈希表还有一个重要的属性: 负载因子(load factor)，它用来衡量哈希表的 空/满 程度，一定程度上也可以体现查询的效率，计算公式为:
负载因子 = 总键值对数 / 箱子个数
负载因子越大，意味着哈希表越满，越容易导致冲突，性能也就越低。因此，一般来说，当负载因子大于某个常数(可能是 1，或者 0.75 等)时，哈希表将自动扩容。
解决hash冲突 常用四种办法
1， 开放定址法：
这种方法也称再散列法，基本思想是：当关键字key的hash地址p=F(key)出现冲突时，以p为基础，产生另一个hash地址p1，如果p1仍然冲突，再以p为基础，再产生另一个hash地址p2，。。。知道找出一个不冲突的hash地址pi，然后将元素存入其中。
2， 再哈希法：
再哈希法又叫双哈希法，有多个不同的Hash函数，当发生冲突时，使用第二个，第三个，….，等哈希函数
计算地址，直到无冲突。虽然不易发生聚集，但是增加了计算时间。
3， 链地址法：
链地址法的基本思想是：每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向
链表连接起来，如：
键值对k2, v2与键值对k1, v1通过计算后的索引值都为2，这时及产生冲突，但是可以通道next指针将k2, k1所在的节点连接起来，这样就解决了哈希的冲突问题
4， 建立公共溢出区：
这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表
4: 数组，链表，哈希表
数组：存储区间是连续的，二分查找时间复杂度小，为O(1)，寻址容易，插入和删除困难；
链表：存储区间离散，时间复杂度很大，达O（N），寻址困难，插入和删除容易；
哈希表：是一种寻址容易，插入删除也容易的数据结构，既满足了数据的查找方便，同时不占用太多的内容空间，使用也十分方便。
Hash表实现原理：使用哈希函数将被查找的Key转换为数组的索引，如果发生hash索引值碰撞冲突，则拉链法(开放定址法)和线性探测法等方法解决冲突，直到找出一个不冲突的哈希地址。
5:字典实现原理
一、NSDictionary使用原理
1.NSDictionary(字典)是使用 hash表来实现key和value之间的映射和存储的，hash函数设计的好坏影响着数据的查找访问效率。
- (void)setObject:(id)anObject forKey:(id )aKey;
2.Objective-C 中的字典 NSDictionary 底层其实是一个哈希表，实际上绝大多数语言中字典都通过哈希表实现，
