Hash表(一)——Hash函数

↑点击上面"算法半岛"

关注"算法半岛"第一时间接收最新文章

Hash表的理解

Hash表也叫 散列表，具有像数组那样根据随机访问的特性，可以根据 key来获得 value。

我们通过一个具体实例来理解散列表。当学校举办校运动会，每个运动员都有一个号码牌，这个号码牌的是根据“年级+班级+需序号”组成，比如初一三班的小岛的号码牌为 070311，其中 07表示七年级即初一， 03表示三班, 11表示班上第11个班上参加运动会的序号。这个时候我们如何存储运动员的信息，来实现通过号码牌来查找运动员的信息？

按照以往的经验，我们可以通过使用数组来存储，其中号码牌即为数组的下标，数组的值为运动员的信息。但是这里有一个问题，运动员的号码牌不是连续的，而申请数组的时候内存空间是连续的，因此会有很多内存空间浪费。

这个时候就可以使用散列表，处理过程如下所示：

从上图可以观察到，我们在存储运动员信息的时候，不是将整个号码牌作为数组的下标，而是将号码牌先进行 hash函数（对100取余）处理后得到的数作为数组的下标，这样就可以数组的大小大大减小，并且在查找到时候也可以通过号码牌来查找对应的运动员的信息。

细心的小伙伴观察到，如果 hash函数处理后的余数一样该怎么办？比如，号码牌为 080211的运动员就会和 070311运动员在 hash函数处理后得到的数是一样，因此会发生冲突，这个就是散列冲突的问题，在后续的讲解中会有相应的解决方案。这里先讲解 Hash函数。

Hash函数

从上面的图可以观察到，中间的部分的部分为 Hash函数，也称为散列函数。它在散列表中起着关键作用。

Hash函数一般使用 hash(key)表示，其中 key表示元素的键值部分， hash(key)的表示经过 Hash函数计算得到的 Hash值（散列值）。

对于上面运动会的问题，我们的 Hash函数是将号码牌转为整型后对 100取余。不同的应用实例 Hash函数不同，该怎么去构造 Hash函数，一般遵循一下三条：

• Hash函数计算得到的散列值是一个非负整数；
• 如果 key1==key2，那么 hash(key1)==hash(key2);
• 如果 key1!=key2，那么 hash(key1)!=hash(key2).

对于第一条很好理解，因为数组的下标是从0开始，所以 Hash函数生成的 Hash值也需要是非负整数。

对于第二条，相同的 key经过 Hash函数处理后得到的 Hash值应该也是相同的。

对于第三条，逻辑上应该是这样的，不同的 key经过 Hash函数处理后得到的 Hash值应该是不相同的，但是想要找到一条不同的 key对应的 Hash值都不一样几乎为不可能的，数组的存储空间是有限的，会加大散列冲突的概率。对于散列冲突，我们需要通过其他的方式来解决。