散列表的理解

散列表也叫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值都不一样几乎为不可能的，数组的存储空间是有限的，会加大散列冲突的概率。对于散列冲突，我们需要通过其他的方式来解决。

更多秋招资料和秋招面试题，请关注公众号[算法半岛]