蓝桥杯每日一刷|蓝桥杯每日一刷（第六天）——暂会哈希蓝桥杯|散列表|哈希算法

文章目录

前言
哈希
- 哈希表
- 哈希函数
- 哈希冲突
例题
- [剑指 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& 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; } };

设计哈希集合