算法小专栏：散列表（二）

深碍√TFBOYSˉ_ 2022-01-19 02:21 180阅读 0赞

> 级别： ★☆☆☆☆  
> 标签：「算法」「Hash」「散列表」「哈希表」  
> 作者： [MrLiuQ][]  
> 审校： [QiShare团队][QiShare]

--------------------

接上篇[散列表（一）][Link 1]，本篇将重点介绍：解决散列冲突的四种方案。

#### 一、开放定址法： ####

##### 1.1 定义： #####

> 描述：为产生冲突的地址`H(key)`求得一个新的地址序列：`Hi =（H(key)+ di）% m` （i=1，2，3，...，m-1），其中`H(key)`为哈希函数，`m`为表长，`di`称为增量序列。

增量序列通常有以下3种取法：

*  线性探测再散列：di = 1，2，3，...，m-1
 *  二次探测再散列：di = 12，-12，22，-22，32，-32，...，k2（k<=m/2）
 *  伪随机探测再散列：di = 伪随机数序列

##### 1.2 举例： #####

例如，在长度为11的哈希表中，已填入关键字 `17`，`29`，`60`的记录，哈希函数为：`H(key) = key % 11`。

计算：  
H(17) = 17 % 11 = 6。故将\*\*关键字“17”**存在下标为6的位置，位置空着，所以存入未冲突。  
H(29) = 29 % 11 = 7。故将**关键字“29”**存在下标为7的位置，位置空着，所以存入未冲突。  
H(60) = 60 % 11 = 5。故将**关键字“60”\*\*存在下标为5的位置，位置空着，所以存入未冲突。

所以，现在的表的存储状态如下图：

这时存入第四个关键字：**38**.

计算：H(38) = 38 % 11 = 5。出现冲突，下标为5的位置已存有60。

*  方式一：线性探测再散列。

开始尝试逐次追加`di = 1，2，3，...，m-1`

得到地址6 => 依然冲突， 得到地址7 => 仍然冲突， 得到地址8 => 不冲突，存入。

最终结果，如下图：

*  方式二：二次探测再散列。

尝试追加 di = 12，-12，22，-22，32，-32，...，k2（k<=m/2）

首先，追加12，地址6仍然冲突。 再，追加-12，地址4无冲突，可以存入。

最终结果，如下图：

*  方式三：伪随机探测再散列。

假设伪随机数为9，

H(38) = (38+9)%11 = 3。地址3不冲突，存入。

最终结果，如下图：

#### 二、链地址法： ####

##### 2.1 定义： #####

> 描述：将所有哈希地址相同的记录都链接在同一**链表**中，以此来解决冲突。

##### 2.2 举例： #####

已知一组关键字为（19，14，23，01，20，68，84，27，55，11，10，79）。 则按哈希函数`H(key) = key % 13`，链地址处理冲突如下图：

#### 三、再哈希法： ####

> 描述：产生冲突时计算\*\*另一个哈希函数（散列函数）\*\*的地址，直到冲突不再发生为止。

优点：这种方法不容易产生聚集。 缺点：增加了计算的时间成本。

#### 四、建立公共溢出区： ####

> 描述：把冲突的都放在另一个溢出表中，而不会存在基本表里。

这也是解决哈希冲突的一种办法，假设哈希函数的值域为`[0，m-1]`，那就创建一个`[0，m-1]`的基本数组，每块内存存放一个记录，另外创建一个溢出数组，一旦发生哈希冲突，就将冲突的值添加至溢出表。

--------------------

小编微信：可加并拉入《QiShare技术交流群》。

> 关注我们的途径有：  
> [QiShare(简书)][QiShare 1]  
> [QiShare(掘金)][QiShare 2]  
> [QiShare(知乎)][QiShare 3]  
> [QiShare(GitHub)][QiShare_GitHub]  
> [QiShare(CocoaChina)][QiShare_CocoaChina]  
> [QiShare(StackOverflow)][QiShare_StackOverflow]  
> QiShare(微信公众号)

> 推荐文章：  
> [iOS UIButton根据内容自动布局][iOS UIButton]  
> [iOS 指定初始化方法][iOS]  
> [UIView中的hitTest方法][UIView_hitTest]  
> [奇舞周刊][Link 2]

转载于:https://juejin.im/post/5ce673f6f265da1bba58dd42

[MrLiuQ]: https://link.juejin.im?target=https%3A%2F%2Fwww.jianshu.com%2Fu%2F6663b66c3df3
[QiShare]: https://link.juejin.im?target=https%3A%2F%2Fwww.jianshu.com%2Fc%2Fb3bd94559163
[Link 1]: https://link.juejin.im?target=https%3A%2F%2Fwww.jianshu.com%2Fp%2Fa05a60874772
[QiShare 1]: https://link.juejin.im?target=https%3A%2F%2Fwww.jianshu.com%2Fu%2F3db23baa08c7
[QiShare 2]: https://juejin.im/user/5b542b76e51d4533d2042b62
[QiShare 3]: https://link.juejin.im?target=https%3A%2F%2Fwww.zhihu.com%2Fpeople%2Fedit
[QiShare_GitHub]: https://link.juejin.im?target=https%3A%2F%2Fgithub.com%2FQiShare
[QiShare_CocoaChina]: https://link.juejin.im?target=http%3A%2F%2Fwww.cocoachina.com%2Fbbs%2Fu.php%3Ftid%3D658244
[QiShare_StackOverflow]: https://link.juejin.im?target=https%3A%2F%2Fstackoverflow.com%2Fusers%2F10118400%2Fqishare
[iOS UIButton]: https://link.juejin.im?target=https%3A%2F%2Fwww.jianshu.com%2Fp%2F0455f7a9ebe8
[iOS]: https://link.juejin.im?target=https%3A%2F%2Fwww.jianshu.com%2Fp%2F31aad4b01606
[UIView_hitTest]: https://link.juejin.im?target=https%3A%2F%2Fwww.jianshu.com%2Fp%2Fccde97aae849
[Link 2]: https://link.juejin.im?target=https%3A%2F%2Fweekly.75team.com