DAY6之哈希基础

这篇具有很好参考价值的文章主要介绍了DAY6之哈希基础。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

什么是哈希表

首先什么是 哈希表,哈希表(英文名字为Hash table,国内也有一些算法书籍翻译为散列表,大家看到这两个名称知道都是指hash table就可以了)。

哈希表是根据关键码的值而直接进行访问的数据结构。

这么这官方的解释可能有点懵,其实直白来讲其实数组就是一张哈希表。

哈希表中关键码就是数组的索引下标,然后通过下标直接访问数组中的元素,如下图所示:

DAY6之哈希基础,哈希算法,散列表,算法

那么哈希表能解决什么问题呢,一般哈希表都是用来快速判断一个元素是否出现集合里。

例如要查询一个名字是否在这所学校里。

要枚举的话时间复杂度是O(n),但如果使用哈希表的话, 只需要O(1)就可以做到。

我们只需要初始化把这所学校里学生的名字都存在哈希表里,在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

将学生姓名映射到哈希表上就涉及到了hash function ,也就是哈希函数。

哈希函数

哈希函数,把学生的姓名直接映射为哈希表上的索引,然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。

哈希函数如下图所示,通过hashCode把名字转化为数值,一般hashcode是通过特定编码方式,可以将其他数据格式转化为不同的数值,这样就把学生名字映射为哈希表上的索引数字了。

DAY6之哈希基础,哈希算法,散列表,算法

如果hashCode得到的数值大于 哈希表的大小了,也就是大于tableSize了,怎么办呢?

此时为了保证映射出来的索引数值都落在哈希表上,我们会在再次对数值做一个取模的操作,这样我们就保证了学生姓名一定可以映射到哈希表上了。

此时问题又来了,哈希表我们刚刚说过,就是一个数组。

如果学生的数量大于哈希表的大小怎么办,此时就算哈希函数计算的再均匀,也避免不了会有几位学生的名字同时映射到哈希表 同一个索引下标的位置。

接下来哈希碰撞登场

哈希碰撞

如图所示,小李和小王都映射到了索引下标 1 的位置,这一现象叫做哈希碰撞。

DAY6之哈希基础,哈希算法,散列表,算法

一般哈希碰撞有两种解决方法, 拉链法和线性探测法。

拉链法

刚刚小李和小王在索引1的位置发生了冲突,发生冲突的元素都被存储在链表中。 这样我们就可以通过索引找到小李和小王了

DAY6之哈希基础,哈希算法,散列表,算法

(数据规模是dataSize, 哈希表的大小为tableSize)

其实拉链法就是要选择适当的哈希表的大小,这样既不会因为数组空值而浪费大量内存,也不会因为链表太长而在查找上浪费太多时间。

线性探测法

使用线性探测法,一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。

例如冲突的位置,放了小李,那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ,要不然哈希表上就没有空置的位置来存放 冲突的数据了。如图所示:

DAY6之哈希基础,哈希算法,散列表,算法

其实关于哈希碰撞还有非常多的细节,感兴趣的同学可以再好好研究一下,这里我就不再赘述了。

数组(略)

set(集合)

是一个内部自动有序且不含重复元素的容器。

一.set用法:

1.定义方法

头文件:#include

定义: settypename> name;

         其中,typename 可以是任何基本类型或者容器,name 是集合的名字。

  set s;  //普通的定义(不允许元素重复)

   multiset s;  //(允许集合中元素重复)

   unordered_set s; //集合中元素不排序次序。

2.访问方法

先定义一个迭代器:set::iterator it; 然后使用“*it”来访问set中的元素。

C++11也可以通过auto遍历。

 for ( auto it =s.begin(); it!=s.end() ; ++it)

     cout << *it <<" ";

或 

for ( auto x : s )

       cout << x <<" ";

二.set常用函数

a是一个set

a.insert(5); //在a集合里插入一个元素5

a.size();//获取集合的长度(即有几个数)

a.clear(); //清空集合a中的所有元素

a.empty(); //判断集合a是否为空

a.begin(); //集合a的第一个位置

a.end(); //集合a的最后一个元素的下一个位置,就没有的意思

a.rbegin(); //逆序迭代器,集合a的最后一个元素

a.erase(x) 从 a 中删除所有等于 x 的元素。

a.find(x)//在集合a中查找等于x的元素,并返回指向该指针的迭代器。若不存在,则返回a.end()。时间复杂度O(logn).

a.count(x)//发挥集合中等于x的元素个数,时间复杂度O(k+logn),其中k为元素x的个数。通常在multise时所有,也可以作为set里判断是否存在某元素。

map(映射)

一.map简介

map是STL的一个关联容器,提供一对一的hash

map有两个值

一个可以成为关键字(key),每个挂件自只能在map中出现一次

第二个可以成为该关键字的值(value)

二.map的功能

自动建立key-value的对应。key和value可以使任意你需要的类型,包括自定义类型(结构体)

三.使用map

头文件#include

mapp;

四.插入元素

// 定义一个map对象
map<int, string> mapStudent;
 
// 第一种 用insert函數插入pair
mapStudent.insert(pair<int, string>(000, "student_zero"));
 
// 第二种 用insert函数插入value_type数据
mapStudent.insert(map<int, string>::value_type(001, "student_one"));
 
// 第三种 用"array"方式插入
mapStudent[123] = "student_first";
mapStudent[456] = "student_second";

用insert函数插入数据,在数据的 插入上涉及到集合的唯一性这个概念,即当map中有这个关键字时,insert操作是不能在插入数据的,但是用数组方式就不同了,它可以覆盖以前该关键字对 应的值

五.查找元素

当所查找的关键key出现时,它返回数据所在对象的位置,如果沒有,返回iter与end函数的值相同。

iter = mapStudent.find("123");
 
if(iter != mapStudent.end())
       cout<<"Find, the value is"<<iter->second<<endl;
else
   cout<<"Do not Find"<<endl;

六.删除与清空元素

//迭代器刪除
iter = mapStudent.find("123");
mapStudent.erase(iter);
//用关键字刪除
int n = mapStudent.erase("123"); //如果刪除了會返回1,否則返回0
//用迭代器范围刪除 : 把整个map清空
mapStudent.erase(mapStudent.begin(), mapStudent.end());
//等同于mapStudent.clear()

七.map的大小

int nsize=map.size();

八.map的基本操作函数

C++ maps是一种关联式容器,包含“关键字/值”对文章来源地址https://www.toymoban.com/news/detail-825952.html

 begin()         返回指向map头部的迭代器

 clear()        删除所有元素

 count()         返回指定元素出现的次数, (帮助评论区理解: 因为key值不会重复,所以只能是1 or 0)

 empty()         如果map为空则返回true

 end()           返回指向map末尾的迭代器

 equal_range()   返回特殊条目的迭代器对

 erase()         删除一个元素

 find()          查找一个元素

 get_allocator() 返回map的配置器

 insert()        插入元素

 key_comp()      返回比较元素key的函数

 lower_bound()   返回键值>=给定元素的第一个位置

 max_size()      返回可以容纳的最大元素个数

 rbegin()        返回一个指向map尾部的逆向迭代器

 rend()          返回一个指向map头部的逆向迭代器

 size()          返回map中元素的个数

 swap()           交换两个map

 upper_bound()    返回键值>给定元素的第一个位置

 value_comp()     返回比较元素value的函数

到了这里,关于DAY6之哈希基础的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【优选算法题练习】day6

    76. 最小覆盖子串 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。 注意:对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串

    2024年02月16日
    浏览(38)
  • Day6——Web安全基础

    网络安全学习笔记Day6 互联网因特网万维网 个人网站,门户网站 Web1.0用于用户通过浏览器获取信息,Web2.0用于用户的交互。 1.SQL注入 2.文件包含 3.命令执行 4.上传漏洞 5.WebShell 1.SQL注入 2.文件包含 3.命令执行 4.上传漏洞 5.WebShell 6.钓鱼攻击 7.URL跳转 8.框架漏洞 9.逻辑漏洞 10.

    2024年02月12日
    浏览(25)
  • 【算法训练(day6)】双指针模板

    通常情况下我们可能会遇到在某些可遍历的集合中寻找满足某种性质的字串或元素。这时候我们采取暴力的思路就会面临多重循环。我们可以利用题目中所给的集合并利用其性质将多重循环降成一重循环。光用语言描述可能不太好理解。接下来看几个双指针典型案例 请从字符

    2024年02月06日
    浏览(32)
  • 新星计划Day6【数据结构与算法】 链表Part2

    👩‍💻博客主页:京与旧铺的博客主页 ✨欢迎关注🖱点赞🎀收藏⭐留言✒ 🔮本文由京与旧铺原创,csdn首发! 😘系列专栏:java学习 💻首发时间:🎞2022年4月30日🎠 🎨你做三四月的事,八九月就会有答案,一起加油吧 🀄如果觉得博主的文章还不错的话,请三连支持一

    2023年04月08日
    浏览(56)
  • HELLO算法笔记之散列表(哈希)

    一、哈希表 建立键  key  与值  value  之间的映射,实现高效的元素查询。输入一个key,以O(1)获取对应的value 遍历: 知识点1、哈希函数: 将一个较大的输入空间映射到一个较小的输出空间。在哈希表中,输入空间是所有  key  ,输出空间是所有桶(数组索引)。换句话

    2024年02月10日
    浏览(36)
  • 数据结构算法设计——哈希表(散列表)

            哈希表 又叫 散列表 ,他们两个是同一个东西,本文全文采用“散列表”的叫法。散列表的本质其实就是一个 数组 ,他的作用就像使用数组时一样,输入下标可以得到对应元素,散列表可以实现 输入一个的时候得到这个的地址信息 。 下面是百科给出

    2024年02月03日
    浏览(59)
  • 【100天精通python】Day6:python基础_基本数据结构,常用序列类型和运算符

    目录 目录 1 常用的序列类型 1.1 字符串(String)  1.2 列表(List) 1.3 元组 (Tuple)

    2024年02月14日
    浏览(59)
  • 【数据结构与算法】04 哈希表 / 散列表 (哈希函数、哈希冲突、链地址法、开放地址法、SHA256)

    一种很好用,很高效,又一学就会的数据结构,你确定不看看? 莫慌,每个概念都很好理解。 哈希表( Hash Table ),也称为 散列表 ,是一种数据结构, 用于存储键值对(key-value pairs) 。 键值对是一种数据结构,用于将键(key)与对应的值(value)相关联。在键值对中,键

    2024年02月09日
    浏览(78)
  • 算法打卡|Day5 哈希表part01

    今日任务 ● 哈希表理论基础 ● 242.有效的字母异位词 ● 349. 两个数组的交集 ● 202. 快乐数 ● 1. 两数之和 目录 哈希表 part01 链表理论基础 Problem: 242. 有效的字母异位词 思路 解题方法 Code Problem: 349. 两个数组的交集 思路 解题方法 Code Problem: 202. 快乐数 思路 解题方法 Code P

    2024年02月08日
    浏览(79)
  • arm:day6

    实现UART通信: 1.键盘输入一个字符\\\'a\\\',串口工具显示\\\'b\\\'  2.键盘输入一个字符串\\\"nihao\\\",串口工具显示\\\"nihao\\\" uart.h uart4.c main.c

    2024年02月12日
    浏览(31)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包