蓝桥杯每日一刷(第六天)——暂会哈希
哈希 每日 蓝桥 一刷 第六天
2023-06-13 09:15:52 时间
文章目录
前言
距离蓝桥杯还剩短短俩个月的时间,最后的号角已经吹响,没有撤退可言!
最后的时间如果要彻底的搞懂比赛所需的算法,很难,但是最后的成绩可能也不是很好,所以我们用真题+解析的形式来做最后的冲刺!
话不多说,开启我们的第六天!
今天我们来学一下哈希表
哈希
哈希表
哈希表又称为散列表,哈希表是一种数据结构,它提供了快速的插入操作和查找操作,无论哈希表总中有多少条数据,插入和查找的时间复杂度都是为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;
}
};
设计哈希集合
相关文章
- 在Win10下 用 Powershell 或 CMD 完成文件的 MD2 MD4 MD5 SHA1 SHA256 SHA384 SHA512 等哈希校验[通俗易懂]
- 字符串之字符串哈希
- hash哈希游戏源码系统开发搭建(成熟技术)
- BAT算法面试题--环形链表(哈希表法)
- 哈希树简介
- 【C++】哈希的应用 -- 位图
- Go语言哈希函数
- C++ STL无序容器自定义哈希函数和比较规则(超级详细)
- Oracle中哈希索引的应用(oracle哈希索引)
- 如何利用Linux破解哈希密码:入门指南(linuxhash破解)
- 微擎玩转Redis哈希掌握分布式缓存之道(微擎redis哈希)
- MySQL中的哈希算法简介与应用(mysql中hash)
- 使用哈希与redis实现复杂应用的进阶教程(哈希redis教程)
- Mootools1.2教程定时器和哈希简介
- C#中哈希表(Hashtable)的介绍及简单用法
- c#哈希算法的实现方法及思路