哈希表结构及碰撞处理

为了为更好的阅读体验，可以阅读原文点击进行阅读

哈希一词源自英文单词hash的音译，通常的叫法还有散列与杂凑，而哈希表（Hash Table）所表示的则是以哈希值为键的数据结构，这种数据结构可以根据键(Key)直接查找到值的存储位置。这里有一点需要注意，平常我们讲哈希一词，一般由两种情况：

一种是哈希表这个数据结构，这种情况下，哈希可以被形象的解释为散列，因为在哈希表中我们希望元素尽量以降低碰撞的概率，在发生碰撞时需要进行针对处理，较为经典的应用就是C++中的unordered_set、unordered_map等
另一种就是哈希这个过程（或者哈希函数），这种情况下，将其称之为杂凑更为合适，此时我们更希望将原来的数据打乱生成固定长度的哈希值，一般不需要对碰撞进行处理，较为经典的应用就是MD5、SHA这种加密算法

本篇文章我们主要讨论的是第一种情况及在发生碰撞时的处理方案。

哈希表的构建过程

哈希表的底层是一个数组，构建哈希表时最重要的步骤就是计算将元素存储在什么位置，如果元素是一个数字类型那么可以直接对其数组长度进行取模得到一个下标位置，而如果元素是其他类型的值则需要将去通过一些处理转换成数字类型再对数组长度取模。假设我们哈希表的底层存储数组长度是20，某个元素经过哈希函数的计算后得到整数12345，那么这个元素就需要存放在数组索引为5的位置（12345%20=5）

哈希碰撞的解决方案

通过上面的过程很明显可以发现一个问题，多个元素在经过一系列的转换和取模后可能得到相同的索引，并且随着数组中存放的元素越来越多，发生碰撞的概率就越来越大。这就是我们下面要讨论的哈希碰撞问题，针对此问题，常规的解决方案由这几种：链表式解决、开放寻址法（线性探测、平方探测）及再哈希法

链表式解决法

这种方法在初始化存储时会将元素存储为一个链表结构，当碰撞发生时就会将元素放到其索引位置存放的链表元素的下一位。假设我们要存放的元素列表经过哈希运算后为[2, 5, 10, 13, 16, 20]，数组长度为8，此时哈希表的存放过程示例如下：

在这里插入图片描述

取模后发生了两次碰撞，此时数组中的存储结构是这样的：

在这里插入图片描述

用这种方式将元素存入哈希表后，在查找元素时会先查看原始位置是否可以找到，找不到则遍历链表，如果链表上也找不到就证明元素不存在于哈希表中

线性探测法

这种方法在碰撞发生时将元素的存储位置+1，如果+1的位置也已经被占用了，就继续看+2的位置，依此重复… 还是以上面的元素为例，来看下此时哈希表的存储过程：

在这里插入图片描述

通过示例可以看出，此方法容易导致“二次聚集”，即不同基地址的元素争夺同一个位置的情况，为了避免此情况，可以在重新寻址时将原位置+(冲突次数)²，也就是说先将位置+1，如果+1被占用了就再+4（冲突次数为2，2²=4），这种方法称之为平方探测法，它和线性探测法被统称为开放寻址法。现在我们换一个示例列表：[2, 5, 10, 12, 18]，数组长度同样为8，应用此方法时存储过程如下：

在这里插入图片描述

用这种方式处理哈希碰撞时候，如果要查找元素，会首先查看初始位置，然后依此将这个位置+1（或查找次数^2)直到找到一个空位置或找到数组的最后的位置，如果还找不到元素就证明其不存在于哈希表

再哈希法

这种方法就是在发生碰撞时，对值再进行一次哈希计算，使其与当前位置分散开，这里我们还是使用上方示例中的列表，此方法需要我们规定以下再哈希的算法，这里我们将其简单的规定为hash2(key) = L – 1 – (hash1 << 1) % L（L为数组长度，hash12为第一次哈希的结果），那么此时列表元素的存储过程如下：

在这里插入图片描述

可以发现使用这种方式处理哈希碰撞时，需要控制在哈希的次数阈值，不然存储时可能出现无限循环的情况，在查找元素时候会导致无法确定边界（不知道进行多少次哈希才算找不到元素）

哈希表满了怎么办

为了应对随着元素的增加碰撞几率越来越大这种情况，需要有一种扩容机制来加大存储存储数组的长度，针对这一问题不同的编程语言的处理可谓是百花齐放。这里我们可以讨论一种最简单的思路，当数组中存储的元素超过数组容量的70%时，就可以出发扩容机制，然后将旧哈希表中的元素迁移至新哈希表（这一过程可以对元素重新进行哈希）

当然我们这里讨论的是最简单的情况，实际中的哈希表扩容机制比这要复杂的多，比如Golang中对于map的扩容分成两大判断，在整体key-value对超过负载因子或溢出桶的数量与常规桶数量大致相同时发生扩容，而且为了一次性扩容导致的性能抖动，Go还采用了渐进扩容策略，即在涉及到某个桶的修改操作时才单独迁移某个桶，而不是一次性迁移整个哈希表。总之，完备的哈希表的扩容策略需要考虑到很多因素与边界情况，但无论是何种实现，哈希表都需要在满足某种条件时进行扩容，而不会发生哈希表被填满的情况

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/6cd3f93554.html