c++ 哈希表(hash表)
2024-08-24 11:32:38
一、定义
Hash表,也称散列表。一般应用于有大量“动态”的插入(删除)和查找操作的一类问题。(如果是“静态”的,通常可以先对数据排序,查找时就可以用“二分查找”)
虽然可以用“平衡树”之类方法,但实践中,用hash表更简单实用。
普通的查找方法建立在“比较”的基础上,查找的效率与比较次数密切相关。
hash的思想是能直接找到需要的元素,因此必须在元素的存储位置和它的关键字之间建立一确定的对应关系f,使每个关键字和存储结构中一个(几乎)唯一的存储位置相对应。(按我的理解就类似于高中数学中的映射)
注:虽然存储方式多样,但由于我是个OIer,就都用数组模拟了
e.g.本年级每个学生的记录中都有一个关键字:学号。学号是0000~9999之间的,每个学生学号唯一。因此就可以用函数f(key)=key 得到唯一的地址。因此可以直接(O(1))找到对应的位置(数组下标),插入、查找、删除操作都是O(1)。
(类似于计数排序法)
Hash函数:上面的记录中关键字key和存储位置(这里是数组下标)之间建立的对应关系函数f(key)。称这个对应关系f为哈希函数,按这个思想建立的表为哈希表(又称为杂凑法或散列表)。
冲突:通常的hash函数不是一一对应关系。普通情况下hash函数很可能会出现keyi≠keyj,f(keyi)=f(keyj) 的现象。也就是几个关键字可能对应同一个“地址”。
这就叫作冲突。
最新文章
- 主成分分析 (PCA) 与其高维度下python实现(简单人脸识别)
- 预装WIN8系统的电脑安装WIN7的方法
- 【unity shaders】:Unity中的Shader及其基本框架
- JVM初探 -JVM内存模型
- ECLIPSE下SVN的创建分支/合并/切换使用
- php有些系统会报错或提示 Cannot modify header information - headers already sent by
- tr命令的使用
- Android onActivityResult 设置requestCode 返回的code不对
- 管理Undo数据
- 6.编写一个Java应用程序,该应用程序包括2个类:Print类和主类E。Print 类里有一个方法output()功能是输出100 ~ 999之间的所有水仙花数(各位数字的 立方和等于这个三位数本身,如: 371 = 33 + 73 + 13。)在主类E的main方法中来 测试类Print。
- asp.net web api 2.2 基础框架(带例子)
- MySQL 栏位修改为区分大小写
- python基础 ---- 使用pyCharm 调试
- CF1009E [Intercity Travelling]
- Javascript php 异常捕获
- 从kepware定时取web api内容
- C#基础篇四数组
- Maven配置setting.xml值Mirror与Repository区别
- eclipse,myeclipse综合
- 漫谈NIO(3)之Netty实现
热门文章
- Hadoop案例(八)辅助排序和二次排序案例(GroupingComparator)
- tensorflow运行出现错误 : ImportError: Could not find 'cudart64_90.dll'.
- 【LOJ】#2129. 「NOI2015」程序自动分析
- 关于在vue里使用脚手架空行、空格会报错的问题
- java 数组冒泡排序、转置(降序)
- Python并发编程-SocketServer多线程版
- mySQL 的 2个分类
- android 捕获所有异常 未捕获的异常
- 「HAOI2015」按位或
- luoguP3830 [SHOI2012]随机树 期望概率 + 动态规划 + 结论