实验三 单向哈希函数与MAC
单向哈希函数与MAC
一、实验描述
本实验的学习目的是让学生熟悉单向哈希函数以及消息认证码（MAC），在完成本课实验后，学生应当对密码学概念有更深入的理解并且能通过使用命令为一段指定的信息生成哈希值以及消息认证码，理解哈希函数的特性。
二、实验环境
本实验中，我们将使用openssl命令行工具及其库。实验环境中已自带命令行工具vim，已安装openssl开发库。
系统用户名: test，密码123456
三、实验内容
实验1:生成消息摘要和MAC
在本实验中，我们将认识各种单向哈希算法。你可以使用openssl dgst 命令为一个文件生成哈希值。输入man openssl和man dgst查看手册。
dgsttype选项，是指定单向哈希算法，比如 -md5, -sha1, -sha256 等；
$ openssl dgst dgsttype filename
1、查阅文档，或用man openssl和man dgst查看手册，了解dgstype可用的哈希算法；
2、在dgsttype部分指定单向哈希算法，生成哈希值；
3、替换dgsttype部分，至少使用3种算法，生成哈希值；
【思考】：
1.对于指定的哈希算法，改变消息长度，对比生成的哈希值；
2.对于指定的消息，改变哈希算法，对比生成的哈希值。
实验2:Keyed Hash和HMAC
本节实验中，我们要为文件生成keyed hash（比如MAC）。使用-hmac选项，选项后所带参数就是key。
$ openssl dgst -md5 -hmac "abcdefg" filename
1、请分别使用 HMAC-MD5, HMAC-SHA256 和 HMAC-SHA1 生成keyed hash，并配以不同长度的key。
2、MAC具有签名的功能，为什么签名时不用MAC却使用RSA密钥？
【思考】：
1.是否总是需要在HMAC中使用一个固定长度的key？如果是，key的长度是多
少？如果不是，为什么？
实验3：单向哈希函数的随机性
为了理解单向函数的特性，我们需要做一些关于 MD5 和 SHA256的练习
1.创建一个任意长度的文本文件test1.txt；
2.使用指定的哈希算法为该文件生成哈希值H1；
3.翻转文件test1.txt的任意一位（比特位），可以使用vim进行编辑，另
存为test2.txt；
4.为修改后的文件test2.txt生成哈希值H2。
【思考】：
1.观察H1与H2是否相似，请描述你的观察，并解释原因？
2.改变哈希算法，重复本节实验内容，再次观察结果，对比分析两次哈希值的
差异？
四、作业
按要求完成实验内容并回答每节实验给出的问题。
实验4函数文件
实验四 函数文件 1.定义一个函数文件，求给定复数的指数、对数、正弦和余弦，并在命令文件中调用该函数文件。 函数文件： function [e,ln,s,c]=plural(x) e=exp(x); ln=log(x); s=sin(x); c=cos(x); End 命令文件： x=input('请输入一个复数：'); [e,ln,s,c]=plural(x); e ln s c 运行结果： 请输入一个复数：3+4i e = -13.1288 -15.2008i ln = 1.6094 + 0.9273i s = 3.8537 -27.0168i c = -27.0349 - 3.8512i 2.一物理系统可用下列方程组来表示: ? ?????????????=??????????????????????????----g g m m N N a a m m m m 2121212111001cos 000sin 00cos 0sin 0sin cos θθ θθ θθ 从键盘输入m 1、m 2和θ的值，求N a a 121、、和N 2的值。其中g 取9.8，输入 θ时以角度为单位。 函数文件： function [a1,a2,N1,N2]=physis(m1,m2,t) g=9.8; A=[m1*cos(t*pi/180),-m1,-sin(t*pi/180),0;... m1*sin(t*pi/180),0,cos(t*pi/180),0;... 0,m2,-sin(t*pi/180),0;... 0,0,-cos(t*pi/180),1]; B=[0;m1*g;0;m2*g];
实验五 M文件和MATLAB程序设计
实验五 M文件和MATLAB程序设计 一、实验目的 matlab作为一种高级计算机语言，不仅可以命令行方式完成操作，也具有数据结构、控制流、输入输出等能力，本次实验通过熟悉和掌握m文件的建立与使用方法，以及函数与控制程序流程语句的使用，使学生具备一定的编程和程序调试能力。 1．掌握M文件的使用方法。 2．掌握if语句和switch语句的使用 3. 掌握循环语句的使用 4. 通过练习理解MATLAB编程方法。 二、实验原理 1．m文件 用matlab语言编写的程序，称为m文件。M文件根据调用方式的不同分为两类，命令文件（Script file）和函数文件（Function file）。区别? 2．程序控制结构 1）顺序结构 2）选择结构 （1）if语句a) 单分支if语句b) 双分支if语句c) 多分支if语句 （2）switch 语句 （3）try语句 3）循环结构 （1）for 语句 （2）while语句 （3）break语句、continue语句、return使用,区别? 3．函数文件 function 输出形参表＝函数名（输入形参表） 注释说明部分 函数体语句 三、实验要求 1．首先上机练习PPT中各种流程控制语句的有关实例。 2．然后上机练习下面的实验习题。 四、实验习题 1．数论中一个有趣的题目：任意一个正整数，若为偶数，则用2除之，若为奇数，则与3相乘再加上1。重复此过程，最终得到的结果为1。如： 2→1 3→10→5→16→8→4→2→1
6→3→10→5→16→8→4→2→1 运行下面的程序，按程序提示输入n=1,2,3,5,7等数来验证这一结论。 %classic "3n+1" problem from number theory. while 1 n=input('Enter n,negative quits:'); if n<=0 break end a=n; while n>1 if rem(n,2)==0 n=n/2; else n=3*n+1; end a=[a,n]; end a end Enter n,negative quits:3 a = 3 10 5 16 8 4 2 1 2． 编程求满足∑=>m i i 1100002的最小m 值。 a=0; i=1; while (a<10000) a=a+pow2(i); i=i+1; end m=i-1; m 13 3． 编写一个函数，计算下面函数的值，给出x 的值，调用该函数后，返回y 的值。 function [y]=myfun1(x) ?? ???>+-≤<≤=3,630, 0,sin )(x x x x x x x y 选择一些数据测试你编写的函数。 function y=myfun1(x) if x<=0 y=sin(x);
哈希表实验报告完整版
实验报告 姓名：学号： 1．实验题目 针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。 基本要求：假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。 2．需求分析 本演示程序用VC编写，完成哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。 输出形式：地址，关键字，收索长度，H（key），拼音 3.概要设计 typedef struct NAME typedef struct hterm void InitNameList() void CreateHashList() void FindList() void Display() int main() 4．详细设计 #include
#define HASH_LEN 50 #define M 47 #define NAME_NO 8 typedef struct NAME { char *py; //名字的拼音 int k; //拼音所对应的整数}NAME; NAME NameList[HASH_LEN]; typedef struct hterm //哈希表{ char *py; //名字的拼音 int k; //拼音所对应的整数int si; //查找长度 }HASH; HASH HashList[HASH_LEN]; void InitNameList() { NameList[0].py="houxinming"; NameList[1].py="abc"; NameList[2].py="defdgf"; NameList[3].py="zhangrji"; NameList[4].py="jiaxin"; NameList[5].py="xiaokai"; NameList[6].py="liupeng"; NameList[7].py="shenyonghai";
什么是哈希函数
什么是哈希函数 哈希（Hash）函数在中文中有很多译名，有些人根据Hash的英文原意译为“散列函数”或“杂凑函数”，有些人干脆把它音译为“哈希函数”，还有些人根据Hash函数的功能译为“压缩函数”、“消息摘要函数”、“指纹函数”、“单向散列函数”等等。 1、Hash算法是把任意长度的输入数据经过算法压缩，输出一个尺寸小了很多的固定长度的数据，即哈希值。哈希值也称为输入数据的数字指纹（Digital Fingerprint）或消息摘要（Message Digest）等。Hash函数具备以下的性质： 2、给定输入数据，很容易计算出它的哈希值； 3、反过来，给定哈希值，倒推出输入数据则很难，计算上不可行。这就是哈希函数的单向性，在技术上称为抗原像攻击性； 4、给定哈希值，想要找出能够产生同样的哈希值的两个不同的输入数据，（这种情况称为碰撞，Collision），这很难，计算上不可行，在技术上称为抗碰撞攻击性； 5、哈希值不表达任何关于输入数据的信息。 哈希函数在实际中有多种应用，在信息安全领域中更受到重视。从哈希函数的特性，我们不难想象，我们可以在某些场合下，让哈希值来“代表”信息本身。例如，检验哈希值是否发生改变，借以判断信息本身是否发生了改变。` 怎样构建数字签名 好了，有了Hash函数，我们可以来构建真正实用的数字签名了。 发信者在发信前使用哈希算法求出待发信息的数字摘要，然后用私钥对这个数字摘要，而不是待发信息本身，进行加密而形成一段信息，这段信息称为数字签名。发信时将这个数字签名信息附在待发信息后面，一起发送过去。收信者收到信息后，一方面用发信者的公钥对数字签名解密，得到一个摘要H；另一方面把收到的信息本身用哈希算法求出另一个摘要H’，再把H和H’相比较，看看两者是否相同。根据哈希函数的特性，我们可以让简短的摘要来“代表”信息本身，如果两个摘要H和H’完全符合，证明信息是完整的；如果不符合，就说明信息被人篡改了。 数字签名也可以用在非通信，即离线的场合，同样具有以上功能和特性。 由于摘要一般只有128位或160位比特，比信息本身要短许多倍，USB Key或IC卡中的微处理器对摘要进行加密就变得很容易，数字签名的过程一般在一秒钟内即可完成。
数据结构实验 散列表实验报告
课程实验报告 课程名称：数据结构 实验项目名称：散列表 专业班级： 姓名：XXX 学号： 完成时间：2015 年06 月13 日
背景 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。在理想情况下，查找、插入、删除操作的时间均为O(1)，是一种高效的动态集合结构。 例1：计算机程序设计语言的编译程序需要维护一个符号表，其中元素的关键值为任意字符串，与语言中的标识符对应。该符号表常采用散列表。 例2：为了节约空间，常常需要把文本文件采用压缩编码方式存储。LZW是对文本文件进行压缩和解压缩的方法之一，该方法采用了散列。 问题描述 我们希望在浩瀚的图书中，去发现一本书是否存在。我们不知道书的编号，只知道它的书名。（其实这已经不错了...）。通过书名，来查询它是否存在。 为了简化问题，我们假设每本书的书名都是一组小写字母组成，长度不超过100字符。 基本要求 （1）根据输入建立图书名称表，采用散列表实现该表，散列函数选用BKDE 字符串哈希。 （2）数据的输入输出格式： 输入分为两部分 第一部分，第一行是行数n，n <= 5000。余下n行，每行一个字符串。表示已存 在的图书记录。 第二部分，第一行是行数m，m <= 1000。余下m行，每行一个字符串。表示要查 询的图书记录。 输出： 输出为m行，如果被查的记录存在，则输出"YES",如果不存在则输出"NO"。 测试数据 输入： 4 a ans and hellocpp
MATLAB实验五 函数文件
MATLAB实验报告 学院：光电学院 班级：073-1 姓名：刘颖 学号：200713503117
实验五 函数文件 1.定义一个函数文件，求给定复数的指数、对数、正弦和余弦，并在命令文件中调用该函数文件。 程序设计： function [e ln s c]=num(x) e=exp(x) ln=log(x) s=sin(x) c=cos(x) end 运行结果： >> num(5i) e = 0.2837 - 0.9589i ln = 1.6094 + 1.5708i s = 0 +74.2032i c = 74.2099 ans = 0.2837 - 0.9589i 2.一物理系统可用下列方程组来表示: ??? ? ??? ???????= ?????? ??? ??? ???????????? ??----g g m m N N a a m m m m 2121212 111001cos 0 0sin 00cos 0 sin 0sin cos θ θθ θθθ 从键盘输入 m 1 、 m 2 和θ的值，求 N a a 121、、和 N 2 的值。其中g 取9.8，输入θ时以角度为单位。 程序设计： 函数文件in.m: function [a1,a2,N1,N2]=in(m1,m2,t) g=9.8; A=[m1*cos(t) -m1 -sin(t) 0;m1*sin(t) 0 cos(t) 0;0 m2 -sin(t) 0;0 0 -cos(t) 1]; C=[0;m1*g;0;m2*g]; B=inv(A)*C; a1=B(1); a2=B(2); N1=B(3); N2=B(4); end 调用in.m 的命令文件： >> m1=1;m2=2;t=30*pi/180; >> [a1,a2,N1,N2]=in(m1,m2,t) 运行结果： a1 = 6.5333 a2 = 1.8860 N1 = 7.5440 N2 = 26.1333 4.设 f(x)= 01 .01 1 .01 ) 3() 2(4 2 +++--x x ， 编写一个MATLAB 函数文件fx.m ，使得调用f(x)时，x 可用矩阵代入，得出的f(x)为同阶矩阵。 程序设计： 函数文件fx.m: function A=fx(x) A=1./((x-2).^2+0.1)+1./(((x-3).^4)+0.01) end 调用fx.m 的命令文件： >> A=fx([1 2;2 3;4 3]) 运行结果: A = 0.9716 10.9901 10.9901 100.9091 1.2340 100.9091 5.已知y= ) 20()30() 40(f f f + （1）当f(n)=n+10ln(n 2+5)时，求y 的值。
数据结构课程设计--哈希表实验报告
福建工程学院 课程设计 课程：算法与数据结构 题目：哈希表 专业：网络工程 班级：xxxxxx班 座号：xxxxxxxxxxxx 姓名：xxxxxxx 2011年12 月31 日 实验题目：哈希表 一、要解决的问题 针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。以学生姓名为关键字设计哈希表，并完成相应的建表和查表程序。 基本要求：姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。 运行的环境：Microsoft Visual C++ 6.0 二、算法基本思想描述 设计一个哈希表（哈希表内的元素为自定义的结构体）用来存放待填入的30个人名，人名为中国姓名的汉语拼音形式，用除留余数法构造哈希函数，用线性探查法解决哈希冲突。建立哈希表并且将其显示出来。通过要查找的关键字用哈希函数计算出相应的地址来查找人名。通过循环语句调用数组中保存的数据来显示哈希表。 三、设计 1、数据结构的设计和说明 （1）结构体的定义 typedef struct //记录 { NA name; NA xuehao; NA tel; }Record;
{ Record *elem[HASHSIZE]; //数据元素存储基址 int count; //当前数据元素个数 int size; //当前容量 }HashTable; 哈希表元素的定义，包含数据元素存储基址、数据元素个数、当前容量。 2、关键算法的设计 （1）姓名的折叠处理 long fold(NA s) //人名的折叠处理 { char *p; long sum=0; NA ss; strcpy(ss,s); //复制字符串，不改变原字符串的大小写 strupr(ss); //将字符串ss转换为大写形式 p=ss; while(*p!='\0') sum+=*p++; printf("\nsum====================%d",sum); return sum; } （2）建立哈希表 1、用除留余数法构建哈希函数 2、用线性探测再散列法处理冲突 int Hash1(NA str) //哈希函数 { long n; int m; n=fold(str); //先将用户名进行折叠处理 m=n%HASHSIZE; //折叠处理后的数，用除留余数法构造哈希函数 return m; //并返回模值 }Status collision(int p,int c) //冲突处理函数，采用二次探测再散列法解决冲突{ int i,q; i=c/2+1; while(i
最小完美哈希函数(深入搜索引擎)
最小完美哈希函数 哈希函数h是一个能够将n个键值x j的集合映射到一个整数集合的函数h(x i)，其值域范围是0≤h(x j)≤m-l，允许重复。哈希是一个具有查找表功能并且提供平均情况下快速访问的标准方法。例如，当数 据包含n个整数键值。某常用哈希函数采用h(x)=x mod m，其中m 是一个较小的值，且满足m>n/a。a是装载因子，表示记录数和可用地址数的比例关系。m一般选择一个素数，因此如果要求提供一个对1000个整数键值进行哈希的函数，一个程序员可能会建议写出如下函数形式：，h(x)=x mod 1399。并且提供一个装载因子为。a=0.7的表，该表声明能够存放1399个地址。 a越小，两个不同键值在相同哈希值相互冲突的可能性就越小，然而冲突总是不可避免。第1次考虑这个问题时，事实可能让人吃惊，最好的例子莫过于著名的生日悖论(birthday paradox)。假定一年有365天，那么要组合多少个人，才能使得出现生日相同的人这一概率超过0.5呢？换句话说，给定一个365个哈希槽(hashslot)。随机选择多少个键值才能够使得出现冲突的概率超过0.5?当首次面对这样一个问题时，一般的反应肯定是认为需要很多人才行。事实上，答案是只需区区23人。找到一个能够满足现实大小要求且无冲突的哈希函数的几率小到几乎可以忽略25。例如，一个1000个键值和1399个随机选择的槽，完全没有冲突的概率为 2.35×10-217（概率的计算诱导公式将在下一节中给出，以公式4.1代入m=1399和n=1000得到），如何才能最好地处理这些不可避免冲突？这一话题将在本节中以大段篇幅展开，这里我们正是要找到其中万里挑一的能够避免所有冲突的哈 希函数。 25可以试图在一群人中做这样一个有趣的实验，笔者曾在讲述哈希表的课上和同学们做 过多次这样的实验。有一项很重要的事情往往被我们忽略，即参加者必须事先在纸上写下他们的生日（或者其他任意日子）。然后才能开始核对的工作，这样才能消除神奇的负反馈。在我们的实验中，除非这样做了，否则也许必须找到366个同学才能遇到第1次碰撞，也许这乜存在心理学悖论吧。
实验五.函数文件的编写
闽江学院电子系 实验报告 学生姓名：班级：学号：3142731 课程：函数文件的编写 一、(填实验几，例：试验一)：实验五 二、实验地点：实验楼A210 实验目的： 1.掌握函数文件的定义方法，函数头的写法； 2.掌握调用函数文件的方法，了解函数文件的嵌套调用； 3.熟悉MATLAB函数文件的特点。 三、实验内容： 1、定义一个函数文件lifang.m，用于计算一个立方体的表面积和体积。在命令窗口中调用它。函数文件： 命令窗口：
2、当n分别取100、1000、10000时，求下列各式的值： （1） 2 2232 1111 1236 n π ??++++= ? ?? （2） ()() ()() 22 224466 133******** n n n n π ?? ? ??? ???????? = ? ????? ? ????-+ ???????? ?? 要求用函数文件的定义和调用来实现。（1）函数文件的定义： 函数文件的调用： 命令窗口：
（2）函数文件的定义： 函数文件的调用： 命令窗口： 3、利用函数文件，实现极坐标(,)ρθ与直角坐标(,)x y 之间的转换，并通过函数调用加以验证。 直角坐标转化为极坐标函数定义： 极坐标转化为直角坐标函数定义：
函数文件的调用： 命令窗口： 4、利用预定义变量nargin和nargout，实现以下功能的函数：若输入只有一个参数，输出以 该参数为半径的球的体积；若输入有两个参数，输出分别以该参数为底面半径和高的圆柱体积；若输入有三个参数，输出分别以该参数为三条边的长方体的体积；若输入参数多
哈希表实验报告
数据结构实验报告四——哈希表查找名字(字符串） 实验题目:哈希表查找名字（字符串) 实验目标: 输入一组名字(至少50个）,将其保存并利用哈希表查找。输出哈希查找冲突次数,哈希表负载因子、查找命中率。 数据结构： 哈希表与数组（二维）。二维数组用于静态顺序存储名字(字符串),哈希表采用开放定址法,用于存储名字(字符串)对应得关键字并实现对名字（字符串)得查找。 需要得操作有: １、关键字求取(主函数中两次出现，未单独编为函数） 关键字key=abｓ(字符串首位AＳＣII码值-第二位ASCIＩ码值＋第([]+1)位ASCＩI码值-最后一位ASCII码值－倒数第二位ASCII码值)*字符串长度（abｓ为求整数绝对值得函数)。 ２、处理关键字得哈希函数(Hash) 利用平方取中法求关键值key在哈希表中得位置。公式ａdd=(key＊key）%1０00/LENGTH（a ｄd为key在哈希表中得地址)。 int Hａsｈ（ｉｎｔkey) { ?rｅturn((key*key)/1０００%LENＧＴH); } 3、处理哈希表中冲突得函数(Coｌlｉｓiｏn) 利用线性探测再散列处理冲突,利用全局变量counｔ统计冲突次数。 ｉnt Collｉsioｎ（inｔkｅy,int Haｓhtaｂle［］) { ｉｎtｉ; for(i=1;i<=ＬENGTH;ｉ++） { ??iｆ（Ｈashtabｌe[(Hａsｈ（kｅy)+ｉ)％LEＮGＴＨ]==-1） ?returｎ(（Hａsｈ(keｙ）＋i)％LENＧTＨ); ??count+＋; } } 4、哈希表初始化（InitＨaｓh) ｖoid InitHash(int Hａshtaｂlｅ[]) { ｉｎｔi; for(i=0;ｉ＜ＬＥNGTH；i++) ??Hashtable[i]=-1; } 5、向哈希表中插入关键字(InsｅrｔＨaｓh) void InｓertＨash(int kｅy,int Hａshｔablｅ［]) { ｉｎt add;
哈 希 常 见 算 法 及 原 理
数据结构与算法-基础算法篇-哈希算法 1. 哈希算法 如何防止数据库中的用户信息被脱库？ 你会如何存储用户密码这么重要的数据吗？仅仅 MD5 加密一下存储就够了吗？ 在实际开发中，我们应该如何用哈希算法解决问题？ 1. 什么是哈希算法？ 将任意长度的二进制值串映射成固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。 2. 如何设计一个优秀的哈希算法？ 单向哈希： 从哈希值不能反向推导出哈希值（所以哈希算法也叫单向哈希算法）。 篡改无效： 对输入敏感，哪怕原始数据只修改一个Bit，最后得到的哈希值也大不相同。 散列冲突： 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小。 执行效率： 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速计算哈
希值。 2. 哈希算法的常见应用有哪些？ 7个常见应用：安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储。 1. 安全加密 常用于加密的哈希算法： MD5：MD5 Message-Digest Algorithm，MD5消息摘要算法 SHA：Secure Hash Algorithm，安全散列算法 DES：Data Encryption Standard，数据加密标准 AES：Advanced Encryption Standard，高级加密标准 对用于加密的哈希算法，有两点格外重要，第一点是很难根据哈希值反向推导出原始数据，第二点是散列冲突的概率要小。 在实际开发中要权衡破解难度和计算时间来决定究竟使用哪种加密算法。 2. 唯一标识 通过哈希算法计算出数据的唯一标识，从而用于高效检索数据。 3. 数据校验 利用哈希算法对输入数据敏感的特点，可以对数据取哈希值，从而高效校验数据是否被篡改过。 4. 散列函数 1.如何防止数据库中的用户信息被脱库？你会如何存储用户密码这么重要的数据吗？
数据结构课程设计--哈希表实验报告
福建工程学院课程设计 课程：算法与数据结构 题目：哈希表 专业：网络工程 班级：xxxxxx班 座号：xxxxxxxxxxxx 姓名：xxxxxxx 2011年12 月31 日
实验题目：哈希表 一、要解决的问题 针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。以学生姓名为关键字设计哈希表，并完成相应的建表和查表程序。 基本要求：姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。 运行的环境：Microsoft Visual C++ 6.0 二、算法基本思想描述 设计一个哈希表（哈希表内的元素为自定义的结构体）用来存放待填入的30个人名，人名为中国姓名的汉语拼音形式，用除留余数法构造哈希函数，用线性探查法解决哈希冲突。建立哈希表并且将其显示出来。通过要查找的关键字用哈希函数计算出相应的地址来查找人名。通过循环语句调用数组中保存的数据来显示哈希表。 三、设计 1、数据结构的设计和说明 （1）结构体的定义 typedef struct //记录 { NA name; NA xuehao; NA tel; }Record; 录入信息结构体的定义，包含姓名，学号，电话号码。 typedef struct //哈希表 { Record *elem[HASHSIZE]; //数据元素存储基址 int count; //当前数据元素个数 int size; //当前容量 }HashTable; 哈希表元素的定义，包含数据元素存储基址、数据元素个数、当前容量。 2、关键算法的设计 （1）姓名的折叠处理
哈 希 常 见 算 法 及 原 理
计算与数据结构篇 - 哈希算法 (Hash) 计算与数据结构篇 - 哈希算法 (Hash) 哈希算法的定义和原理非常简单，基本上一句话就可以概括了。将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。 构成哈希算法的条件： 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同； 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小； 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。 哈希算法的应用(上篇) 安全加密 说到哈希算法的应用，最先想到的应该就是安全加密。最常用于加密的哈希算法是 MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法）和 SHA（Secure Hash Algorithm，安全散列算法）。 除了这两个之外，当然还有很多其他加密算法，比如 DES（Data Encryption Standard，数据加密标准）、AES（Advanced Encryption Standard，高级加密标准）。
前面我讲到的哈希算法四点要求，对用于加密的哈希算法来说，有两点格外重要。第一点是很难根据哈希值反向推导出原始数据，第二点是散列冲突的概率要很小。 不过，即便哈希算法存在散列冲突的情况，但是因为哈希值的范围很大，冲突的概率极低，所以相对来说还是很难破解的。像 MD5，有 2^128 个不同的哈希值，这个数据已经是一个天文数字了，所以散列冲突的概率要小于 1-2^128。 如果我们拿到一个 MD5 哈希值，希望通过毫无规律的穷举的方法，找到跟这个 MD5 值相同的另一个数据，那耗费的时间应该是个天文数字。所以，即便哈希算法存在冲突，但是在有限的时间和资-源下，哈希算法还是被很难破解的。 对于加密知识点的补充，md5这个算法固然安全可靠，但网络上也有针对MD5中出现的彩虹表，最常见的思路是在密码后面添加一组盐码(salt), 比如可以使用md5(1234567.'2019@STARK-%$#-idje-789'),2019@STARK-%$#-idje-789 作为盐码起到了一定的保护和安全的作用。 唯一标识(uuid) 我们可以给每一个图片取一个唯一标识，或者说信息摘要。比如，我们可以从图片的二进制码串开头取 100 个字节，从中间取 100 个字节，从最后再取 100 个字节，然后将这 300 个字节放到一块，通过哈希算法（比如 MD5），得到一个哈希字符串，用它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库中，这样就可以减少很多工作量。
实验五 函数文件的编写
闽 江 学 院 电 子 系 实 验 报 告 学生姓名： 班级： 学 号： 课程：MATLAB 程序设计教程 一、实验题目：函数文件的编写 二、实验地点：A210 三、实验目的： 1、掌握函数文件的定义方法，函数头的写法； 2、掌握调用函数文件的方法，了解函数文件的嵌套调用； 3、熟悉MATLAB 函数文件的特点。 四、实验内容： 1、定义一个函数文件lifang.m ，用于计算一个立方体的表面积和体积。在命令窗口中调用它。 2、当n 分别取100、1000、10000时，求下列各式的值： （1）2223211111236n π??++++= ??? （2）()()( )()2222446613355721212n n n n π??????????????= ? ????? ? ????-+?????????? 要求用函数文件的定义和调用来实现。 3、利用函数文件，实现极坐标(,)ρθ与直角坐标(,)x y 之间的转换，并通过函数调用加以验证。 4、利用预定义变量nargin 和nargout ，实现以下功能的函数：若输入只有一个参数，输出以该参数为半径的球的体积；若输入有两个参数，输出分别以该参数为底面半径和高的圆柱体积；若输入有三个参数，输出分别以该参数为三 条边的长方体的体积；若输入参数多于三个，则报错。 5、 先用函数的递归调用定义一个函数文件求1n m i i =∑，然后调用该函数文件求10050102111 1k k k k k k ===++∑∑∑。
五、实验环境（使用的软硬件）：Matlab6.5 六、实验步骤及操作： 1.计算立方体体积 函数文件lifang.m 2求函数值 （1）
数据结构实验四哈希表及其查找
云南大学数学与统计学实验教学中心实验报告 课程名称： 数据结构与算法学期： 2011-2012学年第二学期 成绩： 指导教师：xxx学生姓名：xxx学生学号：xxxxx 实验名称：哈希表及其查找实验要求：必做实验学时：4（+2）学时 实验编号：4（及5）实验日期：第6-8周完成日期：2012.5.10 学院：数学与统计学院专业：信息与计算科学年级：2010级 一、实验目的 通过实验掌握散列存储的基本概念，进行哈希问题的处理，同时附带进行字符串的处理的练习。 二、实验内容 为某单位的人名（n=30人）设计一个哈希表，使得平均查找长度<2，要求完成相应的哈希建表和查表。。 三、实验环境 Windows XP 程序设计语言C 四、实验过程 1．实验要求： 1、设人名长度<10个字符，用二维字符数组存储哈希表：char hash[ ][10]; 2、要求哈希函数用除留余数法，并用人名的10个字符代码和作为分子； 用（补偿性）线性探测再散列处理冲突。 3、依题意有：平均查找长度=（1+1/(1-α)）/2< 2，∴取α=0.6， 由此哈希表长m=n/α=30/0.6=50; 所以有char hashlist [ 50][10]； 令：除留余数法中的P取47； （补偿性）线性探测再散列的地址：j=(j+Q)% m中的Q取17。 4、对程序结构的要求： ①要求为哈希建表和哈希查表分别编写和设计相应的函数： createhash( ... ... ); hashsearch(... ...)； ②再设计一个哈希函数表的输出函数printhash( )，对构造的哈希表进行输出，注 意输出格式要在屏幕好看，先输出序号（1~30），再输出该序号 的人名或null，每行输出10项，共输出5行。 ③还应有一个初始化char hashlist [ 50][10]的函数Inithashlist( )， 初始时将50个人名全赋值为null. 5、在主函数中： 调用Inithashlist( )初始化哈希表；
哈希的基本概念
6、8 哈希表及其查找★3◎4 哈希译自“haｓh"一词,也称为散列或杂凑。?哈希表查找得基本思想就是:根据当前待查找数据得特征,以记录关键字为自变量,设计一个哈希函数,依该函数按关键码计算元素得存储位置,并按此存放;查找时,由同一个函数对给定值ｋｅy计算地址,将ｋｅy与地址单元中元素关键码进行比较,确定查找就是否成功。哈希方法中使用得转换函数称为哈希函数(杂凑函数),按这个思想构造得表称为哈希表(杂凑表)。?对于n个数据元素得集合,总能找到关键码与存放地址一一对应得函数、若最大关键为m,可以分配m个数据元素存放单元,选取函数f(ke ｙ)=ｋey即可,但这样会造成存储空间得很大浪费,甚至不可能分配这么大得存储空间、通常关键码得集合比哈希地址集合大得多,因而经过哈希函数变换后,可能将不同得关键码映射到同一个哈希地址上,这种现象称为冲突(Cｏlｌｉsio ｎ)。映射到同一哈希地址上得关键码称为同义词。可以说,冲突不可能避免,只能尽可能减少。所以,哈希方法需要解决以下两个问题:?(1)构造好得哈希函数?①所选函数尽可能简单,以便提高转换速度。?②所选函数对关键码计算出得地址,应在哈希地址集中大致均匀分布,以减少空间浪费。 (2)制定解决冲突得方案 1.常用得哈希函数 (1)直接定址法 即取关键码得某个线性函数值为哈希地址,这类函数就是一一对应函数,不会产生冲突,但要求地址集合与关键码集合大小相同,因此,对于较大得关键码集合不适用。如关键码集合为｛100,300,500,7０0,8０0,900｝,选取哈希函数为Hａ
sh(key)=ｋey／100,则存放如表6-3所示。 表6—3 直接定址法构造哈希表 (２)除留余数法 即取关键码除以p得余数作为哈希地址。使用除留余数法,选取合适得p很重要,若哈希表表长为m,则要求p≤m,且接近ｍ或等于ｍ。p一般选取质数,也可以就是不包含小于20质因子得合数、?(3)数字分析法 设关键码集合中,每个关键码均由ｍ位组成,每位上可能有r种不同得符号、?数字分析法根据ｒ种不同得符号及在各位上得分布情况,选取某几位,组合成哈希地址。所选得位应就是各种符号在该位上出现得频率大致相同。 (4)平方取中法?对关键码平方后,按哈希表大小,取中间得若干位作为哈希地址。?(5)折叠法(Ｆoｌｄinｇ)?此方法将关键码自左到右分成位数相等得几部分,最后一部分位数可以短些,然后将这几部分叠加求与,并按哈希表表长,取后几位作为哈希地址。这种方法称为折叠法。?有两种叠加方法:?①移位法-—将各部分得最后一位对齐相加。 ②间界叠加法—-从一端向另一端沿各部分分界来回折叠后,最后一位对齐相加。?如对关键码为key=25３46358705,设哈希表长为３位数,则可对关键码每3位一部分来分割。关键码分割为如下4组: 253 ４６3 5８７05 分别用上述方法计算哈希地址如图6—12所示、对于位数很多得关键码,且每一位上符号分布较均匀时,可采用此方法求得哈希地址。
实验五--M文件和MATLAB程序设计
实验五--M文件和MATLAB程序设计
实验五 M文件和MATLAB程序设计 一、实验目的 matlab作为一种高级计算机语言，不仅可以命令行方式完成操作，也具有数据结构、控制流、输入输出等能力，本次实验通过熟悉和掌握m 文件的建立与使用方法，以及函数与控制程序流程语句的使用，使学生具备一定的编程和程序调试能力。 1．掌握M文件的使用方法。 2．掌握if语句和switch语句的使用 3. 掌握循环语句的使用 4. 通过练习理解MATLAB编程方法。 二、实验原理 1．m文件 用matlab语言编写的程序，称为m文件。M文件根据调用方式的不同分为两类，命令文件（Script file）和函数文件（Function file）。区别? 2．程序控制结构 1）顺序结构 2）选择结构 （1）if语句a) 单分支if语句b) 双分
支if语句c) 多分支if语句 （2）switch 语句 （3）try语句 3）循环结构 （1）for 语句 （2）while语句 （3）break语句、continue语句、return使用,区别? 3．函数文件 function 输出形参表＝函数名（输入形参表） 注释说明部分 函数体语句 三、实验要求 1．首先上机练习PPT中各种流程控制语句的有关实例。 2．然后上机练习下面的实验习题。 四、实验习题 1．数论中一个有趣的题目：任意一个正整数，若为偶数，则用2除之，若为奇数，则与3相乘再加上1。重复此过程，最终得到的结果为1。如：
3→10→5→16→8→4→2→1 6→3→10→5→16→8→4→2→1 运行下面的程序，按程序提示输入n=1,2,3,5,7等数来验证这一结论。 %classic "3n+1" problem from number theory. while 1 n=input('Enter n,negative quits:'); if n<=0 break end a=n; while n>1 if rem(n,2)==0 n=n/2; else n=3*n+1; end a=[a,n]; end a
数据结构哈希表的实验报告
课程实习报告 一、需求分析： 1.本程序来自于图书馆靠书名来检索想要查找的书问题。 2.本程序要求： （1）根据输入建立图书名称表，采用创建散列表实现。 （2）建散列表后，如果想要查找的数据在散列表中输出yes否则输出no。 二、哈希表简介 结构中存在关键字和K相等的记录，则必定存储在f(K）的位置上。由此，不需比较便可直接取得所查记录。这个对应关系f称为散列函数(Hash function），按这个思想建立的表为散列表。
* 对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2），这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。 * 综上所述，根据散列函数H(key）和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”，作为这条记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。这个现象也叫散列桶，在散列桶中，只能通过顺序的方式来查找，一般只需要查找三次就可以找到。科学家计算过，当负载因子(load factor)不超过75%，查找效率最高。* 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。 程序设计流程 程序思想 (一)哈希函数unsigned int hash_BKDE(char *str)生成映射 地址，成为散列表的编号。 (二)哈希表HashTable::HashTable()通过数组储存元素 (三)插入函数void HashTable::insert(char*c)插入字符串， 先计算要插入字符串生成的映射地址，然后在相应的地址插入，如果没有空位查找空位插入。
哈 希 常 见 算 法 及 原 理 ( 2 0 2 0 )
哈希算法乱谈（摘自知乎） 最近【现场实战追-女孩教-学】初步了解了Hash算法的相关知识，一些人的见解让我能够迅速的了解相对不熟悉的知识，故想摘录下来，【QQ】供以后温故而知新。 HASH【⒈】算法是密码学的基础，比较常用的有MD5和SHA，最重要的两【О】条性质，就是不可逆和无冲突。 所谓不【１】可逆，就是当你知道x的HASH值，无法求出x； 所谓无【б】冲突，就是当你知道x，无法求出一个y，使x与y的HA【９】SH值相同。 这两条性【⒌】质在数学上都是不成立的。因为一个函数必然可逆，且【２】由于HASH函数的值域有限，理论上会有无穷多个不同的原始值【６】，它们的hash值都相同。MD5和SHA做到的，是求逆和求冲突在计算上不可能，也就是正向计算很容易，而反向计算即使穷尽人类所有的计算资-源都做不到。 顺便说一下，王小云教授曾经成功制造出MD5的碰撞，即md5(a) = md5(b)。这样的碰撞只能随机生成，并不能根据一个已知的a求出b（即并没有破坏MD5的无冲突特性）。但这已经让他声名大噪了。 HASH算法的另外一个很广泛的用途，就是很多程序员都会使用的在数据库中保存用户密码的算法，通常不会直接保存用户密码（这样DBA就能看到用户密码啦，好危险啊），而是保存密码的HASH值，验
证的时候，用相同的HASH函数计算用户输入的密码得到计算HASH值然后比对数据库中存储的HASH值是否一致，从而完成验证。由于用户的密码的一样的可能性是很高的，防止DBA猜测用户密码，我们还会用一种俗称“撒盐”的过程，就是计算密码的HASH值之前，把密码和另外一个会比较发散的数据拼接，通常我们会用用户创建时间的毫秒部分。这样计算的HASH值不大会都是一样的，会很发散。最后，作为一个老程序员，我会把用户的HASH值保存好，然后把我自己密码的HASH值保存到数据库里面，然后用我自己的密码和其他用户的用户名去登录，然后再改回来解决我看不到用户密码而又要“偷窥”用户的需要。最大的好处是，数据库泄露后，得到用户数据库的黑客看着一大堆HASH值会翻白眼。 哈希算法又称为摘要算法，它可以将任意数据通过一个函数转换成长度固定的数据串（通常用16进制的字符串表示），函数与数据串之间形成一一映射的关系。 举个粒子，我写了一篇小说，摘要是一个string:'关于甲状腺精灵的奇妙冒险'，并附上这篇文章的摘要是'2d73d4f15c0db7f5ecb321b6a65e5d6d'。如果有人篡改了我的文章，并发表为'关于JOJO的奇妙冒险'，我可以立即发现我的文章被篡改过，因为根据'关于JOJO的奇妙冒险'计算出的摘要不同于原始文章的摘要。 可见，摘要算法就是通过摘要函数f()对任意长度的数据data计算出固定长度的摘要digest，目的是为了发现原始数据是否被人篡
实验5 函数
实验5 函数 实验要求： 使用Visual C++ 6.0开发环境，完成以下习题。 1. 编程实现：分别编写一个求三个整数最大值的函数max，和一个求三个整数最小值的函数min，然后在主函数输入三个整数的值，分别调用max和min函数求最大最小值，并输出。源程序保存为5_1.c文件。 2. 编程实现：编写一个函数，由实参（数组传参）传来一个字符串（字符数组），统计此字符串中字母、数字（0~9）、空格和其它字符的个数，要求在主函数中输入字符串以及输出上述结果。字符串的大小（里面所包含的字符个数）可以是固定的，亦可以是根据输入情况变化。源程序保存为5_2.c文件。 3. 选做题：在一体育比赛中，有10个评委为参赛选手打分（分数在1～10之间），分数使用数组保存，求选手的最后得分，选手最后得分规则：去掉一个最高分和一个最低分后其余分数的平均值。编写一个函数；（例如：函数名为：calculator）计算选手的最后得分。在主函数中定义分数数组，并输入分数，调用自己函数计算最后得分，输出最后得分，结果保留2位小数。 源程序保存为5_3.c 实验提交要求： 1.每位同学的文件必须严格按照题目的要求对文件进行命名，否则按不提交作 业处理。 2.每位同学的作业放在一个文件夹中提交，只需提交源文件(后缀名是.c的文 件)，文件夹按以下格式命名： “班内序号_姓名_实验5” 例如：01_黄明_实验5 3.实验完成后，提交到指定服务器。服务器地址： ftp://fcy:fcy@10.5.1.5 请提交到服务器的“作业→高级语言程序设计(C)→实验5”文件夹中以各自
班级名称命名的文件夹内。 （请认清楚班级名称提交，切勿提交到其他班的文件夹中。）