零、写在前面

这是《算法零基础100讲》专栏打卡学习的第五十五了。
每天打卡的题，做不出来没关系，因为困难的题涉及知识点较多，后面还是会开放出来的，就像昨天的最大公约数那道题今天还是会有，所以不要着急，内容能看懂，能自己分析，能做出简单题，就可以打卡。
在刷题的过程中，总结自己遇到的坑点，写出 「解题报告」 供他人学习，也是一种自我学习的方式。这就是经典的帮助他人的同时，成就自己。目前， 「万人千题」 社区每天都会有五六篇高质量的 「解题报告」 被我 「加精」。如果觉得自己有能力的，也可以来发布你的 「解题报告」。千万级流量，你我共同拥有。

一、概念定义

1、哈希表的定义

哈希表，所以很多数据结构书上称之为 散列表，下文会统一采用 哈希表 的形式来说明，作为读者，只需要知道这两者是同一种数据结构即可。
我们把需要查找的数据，通过一个 函数映射，找到 存储数据的位置 的过程称为哈希。这里涉及到几个概念：
a）需要 查找的数据 本身被称为 关键字；
b）通过 函数映射 将 关键字 变成一个 哈希值 的过程中，这里的函数被称为 哈希函数；
c）生成 哈希值 的过程过程可能产生冲突，需要进行 冲突解决；
d）解决完冲突以后，实际 存储数据的位置 被称为 哈希地址，通俗的说，它就是一个数组下标；
e）存储所有这些数据的数据结构就是 哈希表，程序实现上一般采用数组实现，所以又叫 哈希数组。整个过程如下图所示：

2、哈希数组

为了方便下标索引，哈希表 的底层实现结构是一个数组，数组类型可以是任意类型，每个位置被称为一个槽。如下图所示，它代表的是一个长度为 8 的 哈希表，又叫 哈希数组。

3、关键字

关键字 是哈希数组中的元素，可以是任意类型的，它可以是整型、浮点型、字符型、字符串，甚至是结构体或者类。如下的 A、C、M 都可以是关键字；

int A = 5;
char C[100] = "Hello World!";
struct Obj { };
Obj M;

哈希表的实现过程中，我们需要通过一些手段，将一个非整型的 关键字 转换成 数组下标，也就是 哈希值，从而通过 $O (1)$ 的时间快速索引到它所对应的位置。
而将一个非整型的 关键字 转换成整型的手段就是 哈希函数。

4、哈希函数

哈希函数可以简单的理解为就是小学课本上那个函数，即 $y = f (x)$ ，这里的 $f (x)$ 就是哈希函数， $x$ 是关键字， $y$ 是哈希值。好的哈希函数应该具备以下两个特质：
a）单射；
b）雪崩效应：输入值 $x$ 的 $1$ 比特的变化，能够造成输出值 $y$ 至少一半比特的变化；
单射很容易理解，图 $(a)$ 中已知哈希值 $y$ 时，键 $x$ 可能有两种情况，不是一个单射；而图 $(b)$ 中已知哈希值 $y$ 时，键 $x$ 一定是唯一确定的，所以它是单射。由于 $x$ 和 $y$ 一一对应，这样就从本原上减少了冲突。
雪崩效应是为了让哈希值更加符合随机分布的原则，哈希表中的键分布的越随机，利用率越高，效率也越高。
常用的哈希函数有：直接定址法、除留余数法、数字分析法、平方取中法、折叠法、随机数法 等等。有关哈希函数的内容，会在下一篇文章进行详细讲解。

5、哈希冲突

哈希函数在生成 哈希值 的过程中，如果产生 不同的关键字得到相同的哈希值 的情况，就被称为 哈希冲突。
即对于哈希函数 $y = f (x)$ ，当关键字 $x_1 \neq x_2$ ，但是却有 $f(x_1) = f(x_2)$ ，这时候，我们需要进行冲突解决。
冲突解决方法有很多，主要有：开放定址法、再散列函数法、链地址法、公共溢出区法 等等。有关解决冲突的内容，会在下一篇文章进行详细讲解。

6、哈希地址

哈希地址 就是一个 数组下标 ，即哈希数组的下标。通过下标获得数据，被称为索引。通过数据获得下标，被称为哈希。

二、题目描述

给你一个未排序的整数数组 nums，请你找出其中没有出现的最小的正整数。

三、算法详解

思路如下：
1）如果在 1 到 maxn之间的数字，映射到哈希数组中；
2）然后从 1 开始遍历哈希数组，第一个没有被哈希的就是答案；
3）所有数字都遍历完毕，仍然没有找到，则答案为 $n + 1$ 。

四、源码剖析

#define maxn 500001
int hash[500001], cases = 0;

int firstMissingPositive(int* nums, int numsSize){
    int i;
    ++cases;                                // (1) 
    for(i = 0; i < numsSize; ++i) {
        if(nums[i] > 0 && nums[i] < maxn)
            hash[ nums[i] ] = cases;        // (2) 
    }
    for(i = 1; i <= numsSize; ++i) {
        if(hash[i] < cases) {
            return i;                       // (3) 
        }
    }
    return numsSize + 1;                    // (4) 
}

$(1)$ 这里教大家一个奇技淫巧，就是用cases变量来标记是第几组cases，这样就可以放心用全局变量hash[]而不用每次都memset了；
$(2)$ 如果在 1 到 maxn之间的数字，映射到哈希数组中；
$(3)$ 然后从 1 开始遍历哈希数组，第一个没有被哈希的就是答案；
$(4)$ 所有数字都遍历完毕，仍然没有找到，则答案为 n + 1；

五、推荐专栏

🌳《画解数据结构》🌳
画解哈希表

六、习题练习

序号	题目链接	难度
1	缺失的第一个正数	★☆☆☆☆
2	剑指 Offer 03. 数组中重复的数字	★☆☆☆☆
3	按照频率将数组升序排序	★☆☆☆☆
4	数组中的第K个最大元素	★☆☆☆☆
5	数组中的第 k 大的数字	★☆☆☆☆

👇🏻 添加博主参加九日集训👇🏻

《算法零基础100讲》(第55讲) 哈希表入门

文章目录