文章目录

• 前言
• 哈希
  • 哈希表
  • 哈希函数
  • 哈希冲突
• 例题
  • [剑指 Offer 03. 数组中重复的数字](https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/)
  • 设计哈希集合

前言

距离蓝桥杯还剩短短俩个月的时间，最后的号角已经吹响，没有撤退可言!

最后的时间如果要彻底的搞懂比赛所需的算法，很难，但是最后的成绩可能也不是很好，所以我们用真题+解析的形式来做最后的冲刺！

话不多说，开启我们的第六天！

今天我们来学一下哈希表

哈希

哈希表

哈希表又称为散列表，哈希表是一种数据结构，它提供了快速的插入操作和查找操作，无论哈希表总中有多少条数据，插入和查找的时间复杂度都是为O(1)，因为哈希表的查找速度非常快，所以在很多程序中都有使用哈希表，例如拼音检查器。

哈希表也有自己的缺点，哈希表是基于数组的，我们知道数组创建后扩容成本比较高，所以当哈希表被填满时，性能下降的比较严重。

哈希表采用的是一种转换思想，其中一个中要的概念是如何将「键」或者「关键字」转换成数组下标？在哈希表中，这个过程有哈希函数来完成，但是并不是每个「键」或者「关键字」都需要通过哈希函数来将其转换成数组下标，有些「键」或者「关键字」可以直接作为数组的下标。

哈希函数

哈希函数的作用是帮我们把非int的「键」或者「关键字」转化成int，可以用来做数组的下标。

哈希冲突

哈希冲突是不可避免的，我们常用解决哈希冲突的方法有两种「开放地址法」和「链表法」

由于本文并不是深入哈希表，所以基本概念了解完，我们来看例题

例题

剑指 Offer 03. 数组中重复的数字

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int i = 0;
        while(i < nums.size()) {
            if(nums[i] == i) {
                i++;
                continue;
            }
            if(nums[nums[i]] == nums[i])
                return nums[i];
            swap(nums[i],nums[nums[i]]);
        }
        return -1;
    }
};

设计哈希集合