哈希表--day1--基本理论介绍

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

哈希表

Hash table是根据关键码的值来直接进行访问的数据结构。

其实直白来讲其实数组就是一张哈希表,不过其索引是十分简单的,我们通过0来访问num[0],就是通过索引进行访问,得到对应的数据。

而对于个人理解,哈希表一般都是用来快速判断一个元素是否出现集合里。而涉及到Hash table 就需要了解Hash function。

哈希函数

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

哈希函数实际上就是通过hashCode把名字转化为数值,一般hashcode是通过特定编码方式,可以将其他数据格式转化为不同的数值,然后根据哈希表对应的数组大小,将这个数值%定义的数组的大小,得到的数值就是学生名字映射为哈希表上的索引数字,从而访问数组当中的各个元素。

但是这样子避免不了会出现不同的名字对应相同的映射的索引数字,比如小张和小李都经过哈希函数运算得到1,对应访问的都是数组下的num[1]这一个元素,那该如何去确定到底是该访问小张对应的数据还是小李对应的数据,这就出现了一个矛盾,这就是对应的哈希矛盾或者哈希碰撞。

哈希碰撞

一般来说哈希碰撞有俩种方法进行解决:拉链法或者线性探测法

拉链法

拉链法实际上就是在对应数据域的地方,将其变成链表元素,然后将对应索引数值相同的数据都保存到这个虚拟头节点之后。然后再次进行别的编码函数判断,求得对应的是元素的索引值。

举个例子:校长和小李对应都是索引值为1,那么我们将num[1]定义为头节点,后面串上小张和小李对应的数据,用单链表对应串起来,然后再访问的时候,再根据小张还是小李,再次进行判断,即可。

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

线性探测法

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

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

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

常见的三种哈希函数

当我们想使用哈希法来解决问题的时候,我们一般会选择如下三种数据结构。

数组
set (集合)
map(映射)

数组

这里数组就没啥可说的了,占个坑。。。。

set

在C++中,set提供以下三种数据结构,其底层实现以及优劣如下表所示:

集合 底层实现 是否有序 数值是否可以重复 能否修改数值 查询效率 增删效率
std::set 红黑树 有序 O(log n) O(log n)
std::multiset 红黑树 有序 O(logn) O(logn)
std::unordered_set 哈希表 无序 O(1) O(1)

std::unordered_set底层实现为哈希表,std::set 和std::multiset 的底层实现是红黑树,红黑树是一种平衡二叉搜索树,所以key值是有序的,但key不可以修改,改动key值会导致整棵树的错乱,所以只能删除和增加。

map

映射 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率
std::map 红黑树 key有序 key不可重复 key不可修改 O(logn) O(logn)
std::multimap 红黑树 key有序 key可重复 key不可修改 O(log n) O(log n)
std::unordered_map 哈希表 key无序 key不可重复 key不可修改 O(1) O(1)

std::unordered_map 底层实现为哈希表,std::map 和std::multimap 的底层实现是红黑树。同理,std::map 和std::multimap 的key也是有序的。

当我们要使用集合来解决哈希问题的时候,优先使用unordered_set,因为它的查询和增删效率是最优的,如果需要集合是有序的,那么就用set,如果要求不仅有序还要有重复数据的话,那么就用multiset。

那么再来看一下map ,在map 是一个key-value 的数据结构,map中,对key是有限制,对value没有限制的,因为key的存储方式使用红黑树实现的。

虽然std::set、std::multiset 的底层实现是红黑树,不是哈希表,std::set、std::multiset 使用红黑树来索引和存储,不过给我们的使用方式,还是哈希法的使用方式,即key和value。所以使用这些数据结构来解决映射问题的方法,我们依然称之为哈希法。 map也是一样的道理。

这里在说一下,一些C++的经典书籍上 例如STL源码剖析,说到了hash_set hash_map,这个与unordered_set,unordered_map又有什么关系呢?

实际上功能都是一样一样的,但是unordered_set在C++11的时候被引入标准库了,而hash_set并没有,所以建议还是使用unordered_set比较好,这就好比一个是官方认证的,hash_set,hash_map 是C++11标准之前民间高手自发造的轮子。

总结

总结一下,当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法。

但是哈希法也是牺牲了空间换取了时间,因为我们要使用额外的数组,set或者是map来存放数据,才能实现快速的查找。文章来源地址https://www.toymoban.com/news/detail-493449.html

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

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

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

相关文章

  • itheima苍穹外卖项目学习笔记--Day1:项目介绍与开发环境搭建

    (1). 前端环境搭建 前端工程基于 nginx 运行 启动nginx:双击 nginx.exe 即可启动 nginx 服务,访问端口号为 80 (2). 后端环境搭建 后端工程基于 maven 进行项目构建,并且进行分模块开发 (3). 前后端联调 修改数据库中明文密码,改为MD5加密后的密文 修改Java代码,前端提交的密码进行

    2024年02月15日
    浏览(36)
  • 浅学Linux之旅 day1 学习路线及计算机入门知识介绍

    我不要做静等被掀起的轻波,我要生起翠绿的斑驳 偶尔过季的遭遭人事化长风拂过 思绪撕碎点燃了火                         ——24.1.14 ①计算机入门知识介绍 ②Linux系统概述 ③Linux系统的安装和体验 ④Linux的网络配置和连接工具 ⑤Linux的目录结构 ⑥Linux的常用命令

    2024年01月19日
    浏览(42)
  • 【Boost搜索引擎项目】Day1 项目介绍+去标签和数据清洗框架搭建

    🌈欢迎来到C++项目专栏 🙋🏾‍♀️作者介绍:前PLA队员 目前是一名普通本科大三的软件工程专业学生 🌏IP坐标:湖北武汉 🍉 目前技术栈:C/C++、Linux系统编程、计算机网络、数据结构、Mysql、Python 🍇 博客介绍:通过分享学习过程,加深知识点的掌握,也希望通过平台能

    2024年03月23日
    浏览(42)
  • 代码随想录day6|哈希表理论基础、有效的字母异位词、两个数组的交集、快乐数、两数之和

    当需要判断一个元素是否在一个集合中,哈希表的时间复杂度只有O(1)。 哈希表有一个映射的操作,当映射的元素在同一个索引下标的位置,就会引发 哈希碰撞 。 哈希碰撞的两种解决方法:拉链法 线性探测法   同时,哈希表还有常见的三种数据结构:分别是数组、集合s

    2024年02月06日
    浏览(46)
  • ● day5:哈希表理论基础 242.有效的字母异位词 349. 两个数组的交集 202. 快乐数 1. 两数之和

    ● 哈希表理论基础 ● 242.有效的字母异位词 ● 349. 两个数组的交集 ● 202. 快乐数 ● 1. 两数之和 哈希表理论基础 建议:大家要了解哈希表的内部实现原理,哈希函数,哈希碰撞,以及常见哈希表的区别,数组,set 和map。 什么时候想到用哈希法, 当我们遇到了要快速判断一

    2024年02月05日
    浏览(52)
  • 计算机网络课程 day1 基本概念-交换机-路由器 计算机网络的参考模型

    目录 学习计算机网络课程的目标和意义:  计算机网络的基本概念 常用网络设备: network device 交换机:组建局域网使用的,将很多电脑连接起来,组成一个局域网络,可以一起打游戏/上网 路由器:实现跨网段通信使用,把网络里的数据从一个地方转发到另一个地方。可以

    2024年02月13日
    浏览(53)
  • 【代码随想录】Day6 哈希表理论基础 242.有效的字母异位词 ,349. 两个数组的交集 202. 快乐数 1. 两数之和

    【代码随想录】Day6 哈希表理论基础 242.有效的字母异位词 ,349. 两个数组的交集 202. 快乐数 1. 两数之和 新的一部分-哈希表,哈希表之前做题相对比较熟练希望能快速复习 Source: 题目 Note:以前刷的时候使用python字典,这次换做C++ 注意数组就是简单的哈希表,但是数组的大小

    2024年02月20日
    浏览(45)
  • 13、Flink 的table api与sql的基本概念、通用api介绍及入门示例

    一、Flink 专栏 Flink 专栏系统介绍某一知识点,并辅以具体的示例进行说明。 1、Flink 部署系列 本部分介绍Flink的部署、配置相关基础内容。 2、Flink基础系列 本部分介绍Flink 的基础部分,比如术语、架构、编程模型、编程指南、基本的datastream api用法、四大基石等内容。 3、

    2024年02月04日
    浏览(39)
  • QT day1

     

    2024年02月12日
    浏览(35)
  • Qt : day1

     2.思维导图      

    2024年02月16日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包