当前位置：首页 > 编程日记 > 正文

哈希--直接定值法和除留取余法

编程日记 2024-05-11 22:00:00

1. 哈希是一种算法，哈希表是用哈希算法构造出来的一种数据结构

2. 哈希算方法的几种方法

直接定值法

这里有一个例题，就是我们想判断某一字符串中，某一个字符出现的个数，我们可以使用哈希的思想，就是可以遍历一遍字符串，然后开辟一个拥有26数据的整型数组，然后初始化全部为0，然后统计利用一种映射的思想，遍历字符串的时候，就把相应的位置++，每次我们查找某一个字符的时候，一下子就可以定值到那个字符的位置

还有一个例子就是，比如让我们存储1-10这个区间的不重复的数据，这个时候我么也是开辟一个拥有十个元素的整型数组，然后每个数据对应给位置，这样我们在查找的时候，就可以直接查找到这个数据是否存在。

第三个例子是，这里有一些 数据，比如是1001,1006,1009,1007这个时候我们知道数据的范围，我们也是可以开辟一个存储空间来存放这个数据，只不过这个时候我们不需要开辟1000多个大小的数组，我么只需要开辟十个即可，上面的每个数据都减去1000，然后在存放在这个位置，然后我们读取的时候也是按照这个规则读取

分析：上面的几种都是特殊的简单的情况，太具有局限性，还有就是如果我们的数据跨度很大的话，要开辟很大的存储空间，这显然是不合适的，但是一种解题的思路

除留取余法

这里有一部分数据然后我们不能开辟所有的大小的空间，这个时候我呢就出现了一个除留取余法，我们的可以把数据都取余数组的长度，然后放置在相应的位置上面去。

致命缺点：哈希冲突，即是我们的数据可能映射的位置是同一个位置。

法一：闭散列法--开放地址法

（1）第一种方式是线性探测

其他的发生冲突的数据直接往后面走，直到有一个位置上面的数据为空，这个时候把数据放置上去。

比如我么的数据，有89,18,49，58,9，我们开辟的整型数组的空间空间时十个，然后我们放置89，89%10 = 9，然后把89放置在了第九个位置上面去，接着是放置18，18被放置在了8这个位置上面。然后拿到49的时候，我们的数据9这个位置已经后数据，这个时候，我们依次往后走，知道扎到了0号位置是空的，于是49被放置在了0这个位置上面去了。同样 的方法放置其他的数据。

数据放置好了之后，就是查找数据了，这个是时候，如果找9，首先定位到9这个位置上面上，然后没有找到，然后就是依次往后面找，知道找到9，或者就是找到一个空位置停止，这个时候 是没有找到相关的数据。

但是这种方式留下了一个问题就是，如果我们冲突的数据都是集中在了9这个位置了，那每次查找的时候是不是很麻烦，这个时候我我们采用的方法及时二次探测。

（2）第二种方式是二次探测

二次探测的方式值这样的，89进来的时候还是直接放置数据，但是当49进来的时候，不是直接往后面放置了，而是往后移动1的平方个位置，如果是空的就是直接放置，如果不是空的，就是相对于起始位置移动2的 平方个，依次类推下去，直到有一个位置为空。

第一个问题：我们既然已经知道了一次探测的冲突比较大，所以我们这里直接采用的是二次探测

第二个问题：我们的考虑使用数组，但是因为后面的数据可能会增加的很大，所以我们还会考虑增容的操作，这个时候我们不妨直接使用vector。

第三个问题：我们一开始的时候，初始化的时候，初始值应该是多少呢，大家可能和自然的想到了是0，但是有一个问题就是，但是如果我要找的数据就是0的，那不是GG了，所以我们在设计类的成员变量的时候的时候，vector里面的内容 可以放置的是一个结构体，结构体的一部分是数据，一部分是标识位，标识我们的这个位置上面有没有数据

第四个问题：我们既然有增加数据，就一定有删除数据，那个如果是上面的例子，我现在删除了一个数据是49，然后我接下来可能是要找9，这个时候首先定位到下标为9的这个位置，然后往后面二次探测1的平方，这个时候找到了49这个 位置，发现是空，就不往下找了，显然这是不符合 我们的要求的，于是我们想设计结构体的时候，这个标识位有三个值，一个标识有数据，一个标识没有数据，一个标识删除数据，于是我们想到了枚举类型。

第五个问题：我们需要考虑的什么时候增容呢，一开始的想法是当vector满了之后再增容 ，可是这种增容的话，当我们的vector满的 时候是不是数据的冲突就可能大呢，于是我们想的是当已经 放置的数据个数的大小时vector的容量大小的0.7的时候开始增容。

第六个问题：我们的数据在放入的时候，可能在二次探测的时候，可能会出现一只循环在写某些位置，这个 问题下一讲在解决。

代码：hashtable.h

#include<iostream>
using namespace std;
#include<vector>//作为一个标记位
enum State   
{EMPTY,EXIT,DEL
};//哈希节点
template<class K,class V>
struct HashNode
{pair<K, V> _kv;State _state;HashNode():_state(EMPTY){}
};template<class K,class V>
ostream& operator<<(ostream &out, HashNode<K,V> node)
{out << " "<< " " << node._state;return out;
}template<class K,class V>
class HashTable
{//friend ostream& operator<<(ostream &out, HashNode<K, V> node);
public:HashTable():_n(0){_table.resize(10);  //预留的数租空间大小是}//插入函数bool Insert(const pair<K,V> node){Capacity();int m = HanshFunc(node);  //HanshFunc，找到我需要插入的一个下标size_t index = m;size_t i = 0;while (_table[index]._state == EXIT){index = m;i++;index = m + i*i;while (index >= _table.capacity()){index = index - _table.capacity();}}_table[index]._kv = node;_table[index]._state = EXIT;_n++;return true;}int Search(const pair<K, V> node){size_t m = HanshFunc(node);size_t index = m;size_t i = 0;while (_table[index]._kv.first != node.first){if (_table[index]._state == EMPTY){return -1;}index = m;i++;index = m + i*i;while (index >= _table.capacity()){index = index - _table.capacity();}}return index;}private:void Capacity(){//if (_n / _table.capacity() >= 0.7)   //这类需要改进的一个地方 就是，我们不能使用0.7，因为除以了之后，不是一个小数//{//	printf("增容\n");//}if (_n * 10 / _table.capacity() >= 7){printf("增容\n");}}int HanshFunc(const pair<K, V> node){size_t index = node.first % _table.capacity();return index;}private:vector<HashNode<K,V>> _table;  //这个是数组size_t _n;  //当前放置的数据的个数是多少
};

HashTable.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"hashtable.h"int main()
{HashTable<int, int> a;pair<int, int> p(5,6);pair<int, int> p1(15,7);pair<int, int> p2(25, 6);pair<int, int> p3(85, 6);pair<int, int> p4(75, 6);pair<int, int> p5(95, 6);pair<int, int> p6(2, 6);pair<int, int> p7(4, 6);a.Insert(p);a.Insert(p1);a.Insert(p2);a.Insert(p3);a.Insert(p4);a.Insert(p5);a.Insert(p6);a.Insert(p7);cout << a.Search(p);return 0;
}

https://www.dkcj.cn/info/5997.html

两条波浪线符号_四年级数学上册第二单元“线的认识”作业单（附带答案）

“线的认识”作业单一、线段、射线和直线。1.“线段、射线和直线”之间的联系与区别。名称形状长度端点关系2.表示方法：分别画出一条线段、射线和直线，并用字母进行表示。3.概念： (1) (2) (3) 二、相交与垂直1.概念：(1) (2)表示方…

编程日记2024/05/11 21:30:00

CTime类小结1

参考：http://www.cnblogs.com/chuncn/archive/2009/03/12/1409261.html CTime类1．构造和初始化CTime类对象CTime类有下列构造函数：CTime（ ）;CTime（ const CTime& timeSrc ）;CTime&#xff0…

编程日记2024/05/11 21:00:00

oracle数据库动态与静态注册

oracle数据库动态与静态注册动态注册:1.服务名来自于参数文件中的service_names或者是db_name与db_domain的组合;2.实例名来自与参数文件中的instance_name;3.动态注册不需要listener.ora监听文件支持;4.实例状态为READY或BLOCKED;静态注册:1.服务名来自于监听文件中的GLOBAL_…

编程日记2024/05/11 20:30:00

如何实现流畅观影体验？视频类应用内存和CPU大调查

如果把手机内存和CPU想象成固定面积的田地，单个应用对内存和CPU的占用则可比喻为个人的一亩三分地儿。当应用内存和CPU占用过高时，便过多占用了整个田地资源，挤压了邻家应用的面积，那么手机能够同时运行的应用的数量就会相应减少。…

编程日记2024/05/11 20:00:00

dmol3给定关键字不在字典中_python中的数据结构与算法（2）：字典与集合

1. 字典是什么字典是便于信息检索的一种数据结构，鉴于信息检索在程序中无处不在，字典的使用场景也非常广泛，包括许多 python 内部机制的实现，也依赖字典结构，比如命名空间的管理等。检索一般是根据关键字查找与它关联的…

编程日记2024/05/11 19:30:00

HTTP项目1.0 -- HTTP协议基础知识

一. HTTP之URL篇首先来看一下，我们一般在上网的时候，地址栏中经常会显示的信息，这里就举一些简单的例子https://www.baidu.comhttps://113.2.7.58.25/a/b/c.html从上面的简单的例子我们把url分成了以后的几个部分，请看下图第一个协…

编程日记2024/05/11 19:00:00

SQL Server 远程无法连接

1. 查看默认1433端口是否已经开启。转载于:https://www.cnblogs.com/jiajinyi/archive/2013/05/21/3091091.html

编程日记2024/05/11 18:30:00

WCF客户端不能用在Using语句块中，因为它可能会抛出不可预知的异常。即使你捕获了异常，仍有可能一直保持连接。...

WCF客户端不能用在Using语句块中，因为它可能会抛出不可预知的异常。即使你捕获了异常，仍有可能一直保持连接。让我们来看看形成这一问题的历史原因，并提出几个补救措施。在.NET中，资源管理的基础就是IDisposable和Using语句块。除…

编程日记2024/05/11 18:00:00

关于 MongoDB 与 SQL Server 通过本身自带工具实现数据快速迁移及注意事项的探究...

背景介绍随着业务的发展、需求的变化，促使我们追求使用不同类型的数据库，充分发挥其各自特性。如果决定采用新类型的数据库，就需要将既有的数据迁移到新的数据库中。在这类需求中，将SQL Server中的数据导入到MongoDB 中显得尤为突…

编程日记2024/05/11 17:30:00

语音计算矩形面积_LeetCode85-最大矩形

今天在制作书签的时候突然想到了一个问题如果要送给未来的女朋友一个书签上面该写些什么话哈哈哈哈哈哈哈哈哈The Spring is coming!想了一会儿，觉得这句话最合适To xxx:天使的笑，灿烂的心！！！哎，还是先找个…

编程日记2024/05/11 17:00:00

模板的分离编译

模板不支持分离编译我们来分析一下模板为什么不支持分离编译呢，所谓的分离编译就是我们在编写程序的时候可能会出现如下的一种情况就是，（我下面就是举具体的例子了）代码//*****************template.h***********// #include<i…

编程日记2024/05/11 16:30:00

什么是壳 - 脱壳篇01

什么是壳 - 脱壳篇01 让编程改变世界 Change the world by program 壳在自然界中，植物用壳来保护种子，动物用壳来保护身体，我们人类没有壳，但我们有衣服，房子也起到了壳的作用。不仅保护，而且美观。同…

编程日记2024/05/11 16:00:00

push、pop指令

push、pop指令转载于:https://www.cnblogs.com/LoveFishC/archive/2012/07/25/3846605.html

编程日记2024/05/11 15:30:00

个人前端学习路线图与github优秀前端开发者的路线图推荐

1、个人目前学习的路线图 2、github优秀前端开发者的路线图推荐打开github首页，在搜索框输入developer-roadmap，搜索github前端路线图选择kamranahmedse/developer-roadmap拥有56.5k的星，足以证明这个路线受到广大前端开发者的喜爱与推荐选…

编程日记2024/05/11 15:00:00

智能指针1.0

一.使用普通的动态内存开辟存在的问题我们在使用动态内存开辟一个空间的时候，需要释放掉这个空间，不然就容易出现内存泄漏。比如下面的程序情况一： #include<iostream> using namespace std; int errorTest() { intflag 0; …

编程日记2024/05/11 14:30:00

gen_event中的handler和supervised handler

呃，在gen_event中有两个添加handler的方法 gen_event:add_handler/3 gen_event:add_sup_handler/3 一开始总是有些迷惑两者的区别，今天查看了gen_event源码，总算弄清两者的区别。 add_handler添加的只是把gen_event作为容器，仅仅在…

编程日记2024/05/11 14:00:00

动态刷新_屋盖“起飞”刷新国内记录，中建八局杭州萧山国际机场项目最新动态来袭...

近日，中建八局承建的杭州萧山国际机场三期项目完成了一件“壮举”T4航站楼首段钢屋盖网架顺利提升至设计标高一举刷新了国内机场航站屋盖单次提升的记录正式进入主楼屋面及幕墙施工的新篇章两段视频速看首段钢屋架提升刷新记录覆盖测量全过程监控杭州萧山国际机场…

编程日记2024/05/11 13:30:00

逻辑 STANDBY ORA-00368日志应用失败处理一例

故障现象：逻辑STANDBY数据库注册日志成功，但应用日志出现错误，提示“ORA-00368: checksum error in redo log block”，显然是文件受到了破坏。Tue Jul 24 08:25:59 2012LOGMINER: WARNING: error 368 encountered, failed to read…

编程日记2024/05/11 13:00:00

Linux 下实现虚拟光驱功能，查看iso文件内容

1,创建挂载点（也可以不创建，直接用现有的目录）openSUSE:~ # mkdir /mnt/iso2，挂载ISO文件至创建的挂载点openSUSE:~ # mount -t iso9660 -o loop /home/ubuntu-14.04.5-server-amd64.iso /mnt/isomount参数解释：-t&…

编程日记2024/05/11 12:30:00

首先声明，我是一个菜鸟。一下文章中出现技术误导情况盖不负责来自Apache Thrift官网：Thrift Types Thrift Types The Thrift type system is intended to allow programmers to use native types as much as possible, no matter what programming lang…

编程日记2024/05/11 12:00:00

简易git操作 -- 让你的格子绿起来

创建github账号浏览器输入网址，申请一个github账号，github申请网址，看到下面的图片内容，点击图中红色框里面的内容，用邮箱账号申请一个github账号，一定记住账号和密码填写注册信息点击之后跳转到下面…

编程日记2024/05/11 11:30:00

c语言自定义char*函数返回值是乱码_[每日C语言」printf()函数的修饰符和返回值...

在上一个小demo《printf()函数(1)》中主要说了一下printf()函数的转换说明符，这些转移说明符是可以被修饰的。我们可以在%d和定义的转义字符之间通过插入修饰符对基本的转换说明加以修改。printf()修饰符digit(s) 字符宽度的最小值结果：不够的前面补空格…

编程日记2024/05/11 11:00:00

win2003辅助域服务器相关几个错误日志的解决办法

1.域助域上做了DNS后,提示:浏览器无法更新服务状态位,数据有错误,错误代码是8007关闭computer browser基本就行了,有人说还要关server,它负责共享之类的,如果关了,就不能共享了,我个人没有关!2.之前,公司主域上有DNS,不过没有允许复制区域,也没有在辅助域上做DNS,所以在辅助域上…

编程日记2024/05/11 10:30:00

redis.conf配置文件参数说明

参数说明 redis.conf 配置项说明如下：1. Redis默认不是以守护进程的方式运行，可以通过该配置项修改，使用yes启用守护进程daemonize no2. 当Redis以守护进程方式运行时，Redis默认会把pid写入/var/run/redis.pid文件，可以…

编程日记2024/05/11 10:00:00

用C#来开发CAD插件，含源代

CAD插件看起来很神秘，其实一个合格码农经过几天就能快速掌握。没什么秘密，开发CAD插件和winform一样简单，多学几个类库用法就是，在CAD里展现界面和winform略有不同。学习CAD插件开发的动机是为了薪水，由于公司是做显示…

编程日记2024/05/11 09:30:00

动态内存管理和智能指针 2.0 -- shared_ptr

shared_ptr出现原因通过第一章的学习，我们知道不管是auto_ptr合适scoped_ptr都是存在缺陷的，于是我们必须想出一个方法既能很好的管理我们的内存，而且在使用的时候，可以多个指针指向一个内存，这个时候就出现了shared…

编程日记2024/05/11 09:00:00

汇总同一时间段的数据_数据集干货：一文读懂Mapsidejoin

我们知道数据分析的第一步是准备数据，所以在前面的课程里，我们介绍了元数据。今天这篇文章，主要介绍大数据量组合数据集在永洪中的应用实例：Mapsidejoin。什么是Mapsidejoin？按照字面意思，Mapsidejoin就是M…

编程日记2024/05/11 08:30:00

【强烈推荐】国土档案管理信息系统产品使用说明书系列目录【附下载地址】...

<<国土档案管理信息系统>>产品使用说明书系列目录【附下载地址】——通过知识共享树立个人品牌。《国土档案管理信息系统》在线视频讲解一、记大型商业软件<<国土档案管理信息系统>>之系统简介记大型商业软件 > 之系统简介 ——通过知识共享树立个人…

编程日记2024/05/11 08:00:00

zip函数的使用

s [[1, 10], [1.2, 11], [2, 5], [5, 15]] data zip(*s) x_list data[0] y_list data[1] x_min min(x_list) x_max max(x_list) y_min min(y_list) y_max max(y_list) box [x_min, x_max, y_min, y_max] print(box) # [1, 5, 5, 15] 转载于:https://www.cnblogs.com/…

编程日记2024/05/11 07:30:00

计算机网络基础 1.0 -- 概述

概念理解报文：在网络中发送的数据块成为报文在发送报文之前，通常会把数组分组，每个组都有个包头和数据组成，包头中包含了诸如目标地址和源地址等重要信息，这样才保证了数据能够有目的的在网络中的传输主机是用户用来…

编程日记2024/05/11 07:00:00