数据结构-②哈希表

[toc]

二、Hash

1、背景

为了提高在一堆数据中查找指定数据的速度，我们引入hash。

问：为什么需要hash？

答：为了提高查找的速度。(附：主要是用于在Hash Table查询成员用的)

问：和数组相比，基于hash值索引的Hash Table【查找某个成员的过程】就是

Step 1: 通过hash值直接找到查找目标的位置；
Step 2: 如果目标位置上有多个相同hash值得成员, 此时再按照数组方式进行查找。

问：基于hash值索引的Hash Table在【查找某个成员的过程】如何确定找的对象是我们想要的？或hash方法与isEqual的关系?（优化判等）

答：我们以基于hash的NSSet和NSDictionary举例，其在判断成员是否相等时, 为了优化判等的效率，会这样做
Step 1: 集成成员的hash值是否和目标hash值相等, 如果相同进入Step 2, 如果不等, 直接判断不相等；
Step 2: hash值相同(即Step 1)的情况下, 再进行对象判等, 作为判等的结果。

2、Hash 表的实际应用

  • 应用1：找出两文件找出重复的元素

假设有两个文件，文件中均包含一些短字符串，字符串个数分别为n。它们是有重复的字符串，现在需要找出所有重复的字符串。
最笨的解决办法可能是：遍历文件 1 中的每个元素，取出每一个元素分别去文件 2 中进行查找，这样的时间复杂度为O（n^2）。
但是借助 Hash 表可以有一种相对巧妙的方法，我们知道相同元素的 Hash 值相同。所以我们分别遍历文件 1 中的元素和文件 2 中的元素，然后放入 Hash Table 中，对于遍历的每一个元素我们只要简单的做一下计数处理即可。最后遍历整个 Hash 列表，找出所有个数大于 1 的元素即为重复的元素。

  • 应用2：找出两文件找出出现次数最多的元素

同找出两文件找出重复的元素这样的问题解决方案类似，只是在最后遍历的时找计数最大的元素，即为出现次数最多的元素。

3、hash什么时候调用

hash方法只在对象被添加至NSSet和设置为NSDictionary的key时会调用。

HashTable是一种基本数据结构，NSSet和NSDictionary都是使用HashTable存储数据的，因此可以可以确保他们查询成员的速度为O(1)。而NSArray使用了顺序表存储数据，查询数据的时间复杂度为O(n)。

三、哈希(Hash)表/散列表

参考文章：

哈希（Hash）的本质是一种算法，它能够将任意长度的输入（通常是字符串）通过一系列复杂的计算转换成固定长度的输出，这个输出被称为哈希值或哈希码。

NSDictionary 通常是基于哈希表的数据结构。在 NSDictionary 中，键（key）通过哈希函数转换成一个哈希值，然后使用这个哈希值来找到键值对在内存中的存储位置。

哈希表提供了快速的查找、插入和删除操作，这些操作的平均时间复杂度是 O(1)。

1、哈希函数 & Hash地址

要想知道什么是哈希表，那得先了解哈希函数。

hash函数就是根据key计算出应该存储地址的位置，而哈希表是基于哈希函数建立的一种查找表

地址index=H（key）

通过Hash函数和关键字计算出来的存储位置（注意这里的存储位置只是表中的存储位置，并不是实际的物理地址）称作为Hash地址。

重要：相同元素的 Hash 值相同。附：两个相等的实例，他们的hash值一定相等。但是hash值相等的两个实例，不一定相等。

2、哈希函数的构造方法

除留余数法用的较多，H（key）=key MOD p （p<=m，m为表长，p为质数时候可以减少地址冲突）

比如key = 7，39，18，24，33，21时取表长m为9，p为7 那么存储如下

index 0 1 2 3 4 5 6 7 8
key 7 21(冲突后移) 24 39 18(冲突后移) 33(冲突后移)

哈希冲突的解决

哈希冲突即不同key值产生相同的地址，H（key1）=H（key2）。

比如我们上面说的存储7和21，p取7时 7 MOD 7 == 21MOD 7。此时7和21都发生了hash冲突。上面的哈希冲突解决方案我们使用的是开放寻址法（Open Addressing）：当发生冲突时，会寻找表中的下一个空闲位置来存储元素。这通常通过某种探测序列（如线性探测、二次探测或双重散列）来实现。开放寻址法处理冲突的基本原则就是出现冲突后按照一定算法查找一个空位置存放。

其他哈希冲突解决方案：

链地址法（Chaining）：每个哈希表槽位（或称为“桶”）都关联一个链表，所有映射到该索引的元素都存储在这个链表中。这种方法在处理冲突时比较简单，且无堆积现象，非同义词决不会发生冲突，因此平均查找长度较短。链地址法适用于经常进行插入和删除的情况，且在用链地址法构造的散列表中，删除结点的操作易于实现。

哈希表的扩容：

哈希表的大小，即桶（buckets）的数量，是根据存储在其中的对象数量动态变化的。当字典中的元素数量增加到某个阈值时，哈希表会进行扩容，通常是通过增加桶的数量来实现的，以保持操作的效率。

当哈希表进行扩容时，表中的桶（buckets）数量会增加，这意味着原有的哈希值可能不再适用于新的桶数组。因此，当扩容发生时，存储在哈希表中的所有键值对的哈希值通常会重新计算，以便将它们分配到新的桶位置。

在处理哈希冲突时，可能使用开放定址法来解决冲突，这种方法会在哈希表中寻找下一个空闲的桶来存储新的键值对。当哈希表的负载因子（即已使用的桶与总桶数量的比率）达到一定阈值时，哈希表会进行扩容，通常是通过增加桶的数量来实现的。这样可以保持哈希表的操作效率，使得查找、插入和删除操作的平均时间复杂度接近 O(1)。附：数组查找元素需要 O(n) 的时间复杂度，因为它可能需要遍历整个数组。所以哈希表相比数组，查找效率更高。除此之外，哈希表可以在插入时快速检查重复，这对于确保集合中元素的唯一性非常有用。

4、hash表的查找

查找过程和造表过程一致，假设采用开放定址法处理冲突，则查找过程为：
对于给定的key，计算hash地址index = H（key）
如果数组arr【index】的值为空 则查找不成功
如果数组arr【index】== key 则查找成功
否则 使用冲突解决方法求下一个地址，直到arr【index】== key或者 arr【index】==null

哈希表（hash table，也叫散列表），是根据键（key）直接访问访问在内存储存位置的数据结构。

哈希表本质是一个数组，数组中的每一个元素成为一个箱子，箱子中存放的是键值对。根据下标index从数组中取value。关键是如何获取index，这就需要一个固定的函数（哈希函数），将key转换成index。

哈希表—什么是哈希表 有助于理解哈希表