数据结构-Hash

1. 什么是Hash表

先看一下hash表的结构图：

image.png

数组 + 链表

哈希表（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表都会遇到冲突，两种情况下解决冲突的方法应该一致。

解决hash冲突

开放定址法
这种方法也称再散列法，基本思想是：当关键字key的hash地址p=F(key)出现冲突时，以p为基础，产生另一个hash地址p1，如果p1仍然冲突，再以p为基础，再产生另一个hash地址p2，。。。知道找出一个不冲突的hash地址pi，然后将元素存入其中。
通用的再散列函数的形式：
H = (F(key) + di) MOD m
其中i=1，2，。。。，m-1 为碰撞次数
m为表长。
F(key)为hash函数。
di为增量序列，增量序列的取值方式不同，相应的再散列方式也不同。
1）线性探测再散列
di = 1，2，3，。。。，m-1
冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
2）二次探测再散列
di = 1^2, -1^2, 2^2, -2^2,..., k^2, -k^2 (k <= m-1)
发生冲突时，在表的左右进行跳跃式探测，比较灵活。
3）伪随机数探测再散列
di = 伪随机序列
下面有个网上的示列：
现有一个长度为11的哈希表，已填有关键字分别为17，60，29的三条记录。其中采用的哈希函数为f(key)= key MOD 11。现有第四个记录，关键字为38。根据以上哈希算法，得出哈希地址为5，跟关键字60的哈希地址一样，产生了冲突。根据增量d的取法的不同，有一下三种场景：

image.png

线性探测法：当发生冲突时，因为f(key) + d，所以首先5 + 1 = 6，得到下一个hash地址为6，又冲突，依次类推，最后得到空闲的hash地址是8，然后将数据填入hash地址为8的空闲区域。
二次探测法：当发生冲突时，因为d = 1^2，所以5 + 1 = 6，得到的下一个hash地址为6，又冲突，因为d = -1^2,所以5 + (-1) = 4，得到下一个hash地址为4，是空闲则将数据填入该区域。
伪随机数探测法：随机数法就是完全根据伪随机序列来决定的，如果根据一个随机数种子得到一个伪随机序列{1，-2，2，。。。，k}，那么首先得到的地址为6，第二个是3，依次类推，空闲则将数据填入。
链地址法（拉链法，位桶法）
将产生冲突的关键字的数据存储在冲突hash地址的一个线性链表中。实现时，一种策略是散列表同一位置的所有冲突结果都是用栈存放的，新元素被插入到表的前端还是后端完全取决于怎样方便。

image.png

4. 负载因子（load factor）

这里要提到两个参数：初始容量，加载因子，这两个参数是影响hash表性能的重要参数。
容量：表示hash表中数组的长度，初始容量是创建hash表时的容量。
加载因子：是hash表在其容量自动增加之前可以达到多满的一种尺度（存储元素的个数），它衡量的是一个散列表的空间的使用程度。
loadFactor = 加载因子 / 容量
一般情况下，当loadFactor <= 1时，hash表查找的期望复杂度为O(1).
对使用链表法的散列表来说，负载因子越大，对空间的利用更充分，然后后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75。

5. 扩容

当hash表中元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对数组进行扩容。而在数组扩容之后，最消耗性能的点就出现了，原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是扩容。
什么时候进行扩容呢？当表中元素个数超过了容量 * loadFactor时，就会进行数组扩容。

6. 集合NSSet、字典NSDictionary的底层实现原理

Foundation框架下提供了很多高级数据结构，很多都是和Core Foundation下的相对应，例如NSSet就是和_CFSet相对应，NSDictionary就是和_CFDictionary相对应。源码

hash

这里说的hash并不是之前说的hash表，而是一个方法。为什么要有hash方法？
这个问题需要从hash表数据结构说起，首先看下如何在数组中查找某个成员

先遍历数组中的成员
将取出的值与目标值比较，如果相等，则返回改成员

在数组未排序的情况下，查找的时间复杂度是O(n)（n为数组长度）。hash表的出现，提高了查找速度，当成员被加入到hash表中时，会计算出一个hash值，hash值对数组长度取模，会得到该成员在数组中的位置。
通过这个位置可以将查找的时间复杂度优化到O(1)，前提是在不发生冲突的情况下。
这里的hash值是通过hash方法计算出来的，且hash方法返回的hash值最好唯一
和数组相比，基于hash值索引的hash表查找某个成员的过程：

通过hash值直接查找到目标值的位置
如果目标上有很多相同hash值成员，在利用hash表解决冲突的方式进行查找

可以看出优势比较明显，最坏的情况和数组也相差无几。

hash方法什么时候被调用

    NSMutableArray *array1 = [NSMutableArray array];
    [array1 addObject:person1];
    NSMutableArray *array2 = [NSMutableArray array];
    [array2 addObject:person2];
    NSLog(@"array end -------------------------------");
    
    NSMutableSet *set1 = [NSMutableSet set];
    [set1 addObject:person1];
    NSMutableSet *set2 = [NSMutableSet set];
    [set2 addObject:person2];
    NSLog(@"set end -------------------------------");
    
    NSMutableDictionary *dictionaryValue1 = [NSMutableDictionary dictionary];
    [dictionaryValue1 setObject:person1 forKey:@"kKey1"];
    NSMutableDictionary *dictionaryValue2 = [NSMutableDictionary dictionary];
    [dictionaryValue2 setObject:person2 forKey:@"kKey2"];
    NSLog(@"dictionary value end -------------------------------");
    
    NSMutableDictionary *dictionaryKey1 = [NSMutableDictionary dictionary];
    [dictionaryKey1 setObject:@"kValue1" forKey:person1];
    NSMutableDictionary *dictionaryKey2 = [NSMutableDictionary dictionary];
    [dictionaryKey2 setObject:@"kValue2" forKey:person2];
    NSLog(@"dictionary key end -------------------------------");

重写person的hash方法和copyWithZone方法，方便查看hash方法是否被调用：

- (id)copyWithZone:(NSZone *)zone{
    //这里必须是self本身对象
    return self;
}

- (NSUInteger)hash {
    NSUInteger hash = [super hash];
    NSLog(@"走过 hash：%ld", hash);
    return hash;
}

打印结果：

 array end -------------------------------
 走过 hash：105553148651392
 走过 hash：105553148651328
 set end -------------------------------
 dictionary value end -------------------------------
 走过 hash：105553148651392
 走过 hash：105553148651328
 dictionary key end -------------------------------

可以了解到：hash方法只在对象被添加到NSSet和设置为NSDictionary的key时被调用
NSSet添加新成员时，需要根据hash值来快速查找成员，以保证集合中是否已经存在该成员。
NSDictionary在查找key时，也是利用了key的hash值来提高查找的效率。
这里可以得到这个结论：
相等变量的hash结果总是相同的，不相等变量的hash结果有可能相同

NSSet

struct __CFSet {
    CFRuntimeBase _base;
    CFIndex _count;     /* number of values */
    CFIndex _capacity;      /* maximum number of values */
    CFIndex _bucketsNum;    /* number of slots */
    uintptr_t _marker;
    void *_context;     /* private */
    CFIndex _deletes;
    CFOptionFlags _xflags;      /* bits for GC */
    const void **_keys;     /* can be NULL if not allocated yet */
};

根据数据结构可以发现set内部使用了指针数组来保存keys，可以从源码中了解到采用的是连续存储的方式存储。

NSSet添加key，key值会根据特定的hash函数算出hash值，然后存储数据的时候，会根据hash函数算出来的值，找到对应的下标，如果该下标下已有数据，开放定址法后移动插入，如果数组到达阈值，这个时候就会进行扩容，然后重新hash插入。查询速度就可以和连续性存储的数据一样接近O(1)了。

NSDictionary

struct __CFDictionary {
    CFRuntimeBase _base;
    CFIndex _count;     /* number of values */
    CFIndex _capacity;      /* maximum number of values */
    CFIndex _bucketsNum;    /* number of slots */
    uintptr_t _marker;
    void *_context;     /* private */
    CFIndex _deletes;
    CFOptionFlags _xflags;      /* bits for GC */
    const void **_keys;     /* can be NULL if not allocated yet */
    const void **_values;   /* can be NULL if not allocated yet */
};

和上面的集合NSSet相比较，多了一个指针数组values。

通过比较集合NSSet和字典NSDictionary的源码可以知道两者实现的原理差不多，而字典则用了两个数组keys和values，说明这两个数据是被分开存储的。

通过源码可以看到，当有重复的key插入到字典NSDictionary时，会覆盖旧值，而集合NSSet则什么都不做，保证了里面的元素不会重复。
大家都知道，字典里的键值对key-value是一一对应的关系，从数据结构可以看出，key和value是分别存储在两个不同的数组里，这里面是如何对key、value进行绑定的呢？
首先key利用hash函数算出hash值，然后对数组的长度取模，得到数组下标的位置，同样将这个地址对应到values数组的下标，就匹配到相应的value。 注意到上面的这句话，要保证一点，就是keys和values这两个数组的长度要一致。所以扩容的时候，需要对keys和values两个数组一起扩容。

对于字典NSDictionary设置的key和value，key值会根据特定的hash函数算出hash值，keys和values同样多，利用hash值对数组长度取模，得到其对应的下标index，如果下标已有数据，开放定址法后移插入，如果数组达到阈值，就扩容，然后重新hash插入。这样的机制就把一些不连续的key-value值插入到能建立起关系的hash表中。
查找的时候，key根据hash函数以及数组长度，得到下标，然后根据下标直接访问hash表的keys和values，这样查询速度就可以和连续线性存储的数据一样接近O(1)了。

参考文章：笔记-数据结构之 Hash（OC的粗略实现）