精华内容
下载资源
问答
  • 使用Windows自带命令校验文件哈希

    千次阅读 2020-05-03 17:34:13
    Certutil是一个windows预装的CLI程序,主要作用是转储和显示证书颁发机构(CA),...这里记录如何使用这个程序校验文件,网上很多资源的下载很多都会提供文件的md5,SHA256等等之类的哈希值,便于下载者校验文件是否...

    Certutil

    Certutil是一个windows预装的CLI程序,主要作用是转储和显示证书颁发机构(CA),配置信息,证书服务, CA 组件的备份和还原以及验证证书、密钥对和证书链,它作为证书服务的一部分安装。可用于校验文件MD5、SHA1、SHA256,下载恶意文件和免杀。

    这里记录如何使用这个程序校验文件,网上很多资源的下载很多都会提供文件的md5SHA256等等之类的哈希值,便于下载者校验文件是否存在被修改,破坏等改变文件内容的操作

    例如我们下载了当前最新版的kali操作系统I的SO镜像,这里官方提供了SHA256的校验码
    在这里插入图片描述
    在这里插入图片描述
    使用Certutil得到kali-linux-2020.1b-installer-amd64.iso文件的SHA256密文

    certutil -hashfile [文件绝对路径] [md5/sha256/sha1]
    

    在这里插入图片描述
    在这里插入图片描述
    校验结果相同,证明下载的文件是正常的

    Certutil的帮助文档

    帮助文档命令:certutil -?

    PS C:\Users\Administrator\Downloads> certutil -?
    
    动词:
      -dump             -- 转储配置信息或文件
      -dumpPFX          -- 转储 PFX 结构
      -asn              -- 分析 ASN.1 文件
    
      -decodehex        -- 解码十六进制编码的文件
      -decode           -- 解码 Base64 编码的文件
      -encode           -- 将文件编码为 Base64
    
      -deny             -- 拒绝挂起的申请
      -resubmit         -- 重新提交挂起的申请
      -setattributes    -- 为挂起申请设置属性
      -setextension     -- 为挂起申请设置扩展
      -revoke           -- 吊销证书
      -isvalid          -- 显示当前证书部署
    
      -getconfig        -- 获取默认配置字符串
      -ping             -- Ping Active Directory 证书服务申请接口
      -pingadmin        -- Ping Active Directory 证书服务管理接口
      -CAInfo           -- 显示 CA 信息
      -ca.cert          -- 检索 CA 的证书
      -ca.chain         -- 检索 CA 的证书链
      -GetCRL           -- 获取 CRL
      -CRL              -- 发布新的 CRL [或仅增量 CRL]
      -shutdown         -- 关闭 Active Directory 证书服务
    
      -installCert      -- 安装证书颁发机构证书
      -renewCert        -- 续订证书颁发机构证书
    
      -schema           -- 转储证书架构
      -view             -- 转储证书视图
      -db               -- 转储原始数据库
      -deleterow        -- 删除服务器数据库行
    
      -backup           -- 备份 Active Directory 证书服务
      -backupDB         -- 备份 Active Directory 证书服务数据库
      -backupKey        -- 备份 Active Directory 证书服务证书和私钥
      -restore          -- 还原 Active Directory 证书服务
      -restoreDB        -- 还原 Active Directory 证书服务数据库
      -restoreKey       -- 还原 Active Directory 证书服务证书和私钥
      -importPFX        -- 导入证书和私钥
      -dynamicfilelist  -- 显示动态文件列表
      -databaselocations -- 显示数据库位置
      -hashfile         -- 通过文件生成并显示加密哈希
    
      -store            -- 转储证书存储
      -enumstore        -- 枚举证书存储
      -addstore         -- 将证书添加到存储
      -delstore         -- 从存储删除证书
      -verifystore      -- 验证存储中的证书
      -repairstore      -- 修复密钥关联,或者更新证书属性或密钥安全描述符
      -viewstore        -- 转储证书存储
      -viewdelstore     -- 从存储删除证书
      -UI               -- 调用 CryptUI
      -attest           -- 验证密钥证明请求
    
      -dsPublish        -- 将证书或 CRL 发布到 Active Directory
    
      -ADTemplate       -- 显示 AD 模板
      -Template         -- 显示注册策略模板
      -TemplateCAs      -- 显示模板的 CA
      -CATemplates      -- 显示 CA 的模板
      -SetCASites       -- 管理 CA 的站点名称
      -enrollmentServerURL -- 显示、添加或删除与 CA 关联的注册服务器 URL
      -ADCA             -- 显示 AD CA
      -CA               -- 显示注册策略 CA
      -Policy           -- 显示注册策略
      -PolicyCache      -- 显示或删除注册策略缓存项目
      -CredStore        -- 显示、添加或删除凭据存储项目
      -InstallDefaultTemplates -- 安装默认的证书模板
      -URLCache         -- 显示或删除 URL 缓存项目
      -pulse            -- 以脉冲方式执行自动注册事件或 NGC 任务
      -MachineInfo      -- 显示 Active Directory 计算机对象信息
      -DCInfo           -- 显示域控制器信息
      -EntInfo          -- 显示企业信息
      -TCAInfo          -- 显示 CA 信息
      -SCInfo           -- 显示智能卡信息
    
      -SCRoots          -- 管理智能卡根证书
    
      -DeleteHelloContainer -- 删除 Hello 登录容器。
         ** 在使用此选项后, 用户需要注销才能完成。**
      -verifykeys       -- 验证公/私钥集
      -verify           -- 验证证书,CRL 或链
      -verifyCTL        -- 验证 AuthRoot 或不允许的证书 CTL
      -syncWithWU       -- 与 Windows 更新同步
      -generateSSTFromWU -- 通过 Windows 更新生成 SST
      -generatePinRulesCTL -- 生成捆绑规则 CTL
      -downloadOcsp     -- 下载 OCSP 响应并写入目录
      -generateHpkpHeader -- 使用指定文件或目录中的证书生成 HPKP 头
      -flushCache       -- 刷新选定进程(例如 lsass.exe)中的指定缓存
      -addEccCurve      -- 添加 ECC 曲线
      -deleteEccCurve   -- 删除 ECC 曲线
      -displayEccCurve  -- 显示 ECC 曲线
      -sign             -- 重新签名 CRL 或证书
    
      -vroot            -- 创建/删除 Web 虚拟根和文件共享
      -vocsproot        -- 创建/删除 OCSP Web Proxy 的 Web 虚拟根
      -addEnrollmentServer -- 添加注册服务器应用程序
      -deleteEnrollmentServer -- 删除注册服务器应用程序
      -addPolicyServer  -- 添加策略服务器应用程序
      -deletePolicyServer -- 删除策略服务器应用程序
      -oid              -- 显示 ObjectId 或设置显示名称
      -error            -- 显示错误代码消息文本
      -getreg           -- 显示注册表值
      -setreg           -- 设置注册表值
      -delreg           -- 删除注册表值
    
      -ImportKMS        -- 为密钥存档导入用户密钥和证书到服务器数据库
      -ImportCert       -- 将证书文件导入数据库
      -GetKey           -- 检索存档的私钥恢复 Blob,生成恢复脚本 或恢复存档的密钥
      -RecoverKey       -- 恢复存档的私钥
      -MergePFX         -- 合并 PFX 文件
      -ConvertEPF       -- 将 PFX 文件转换为 EPF 文件
    
      -add-chain        -- (-AddChain) 添加证书链
      -add-pre-chain    -- (-AddPrechain) 添加预植证书链
      -get-sth          -- (-GetSTH) 获取签名树头
      -get-sth-consistency -- (-GetSTHConsistency) 获取签名树头更改
      -get-proof-by-hash -- (-GetProofByHash) 获取哈希证明
      -get-entries      -- (-GetEntries) 获取项
      -get-roots        -- (-GetRoots) 获取根
      -get-entry-and-proof -- (-GetEntryAndProof) 获取项和证明
      -VerifyCT         -- 验证证书 SCT
      -?                -- 显示该用法消息
    
    
    CertUtil -?              -- 显示动词列表(命名列表)
    CertUtil -dump -?        -- 显示 "dump" 动词的帮助文本
    CertUtil -v -?           -- 显示所有动词的所有帮助文本
    
    CertUtil: -? 命令成功完成。
    PS C:\Users\Administrator\Downloads>
    

    Get-FileHash

    Get-FileHash命令可用于通过使用指定的哈希算法来计算文件的哈希值,可以接受的哈希算法有:SHA1,SHA256,SHA384,SHA512,MD5

    PS C:\Users\Administrator\Desktop\Test\php> get-filehash -?
    
    NAME
        Get-FileHash
    
    SYNTAX
        Get-FileHash [-Path] <string[]> [[-Algorithm] {SHA1 | SHA256 | SHA384 | SHA512 | MD5}] [<CommonParameters>]
    
        Get-FileHash [-LiteralPath] <string[]> [[-Algorithm] {SHA1 | SHA256 | SHA384 | SHA512 | MD5}] [<CommonParameters>]
    
        Get-FileHash [-InputStream] <Stream> [[-Algorithm] {SHA1 | SHA256 | SHA384 | SHA512 | MD5}] [<CommonParameters>]
    
    
    ALIASES
        None
    
    
    REMARKS
        Get-Help cannot find the Help files for this cmdlet on this computer. It is displaying only partial help.
            -- To download and install Help files for the module that includes this cmdlet, use Update-Help.
            -- To view the Help topic for this cmdlet online, type: "Get-Help Get-FileHash -Online" or
               go to https://go.microsoft.com/fwlink/?LinkId=517145.
    
    
    PS C:\Users\Administrator\Desktop\Test\php> 
    

    在这里插入图片描述

    展开全文
  • 通过建立不完整文件的校验块构成的哈希表,快速检查完整文件的数据块的匹配情况,并返回校验快的编号。 基本结构: 以二维数组为容器,以滚动校验哈希索引,以md4校验码值为值。 另外增加一个二维数组来记录...

    作用:

    通过建立不完整文件的校验块构成的哈希表,快速检查完整文件的数据块的匹配情况,并返回校验快的编号。

    基本结构:

    以二维数组为容器,以滚动校验为哈希索引,以md4校验码值为值。
    另外增加一个二维数组来记录校验块的编号(用于重组)。

    注意点:

    哈希索引冲突时,跟在当前索引的数组队列中。
    查找时在索引下一次查找数组队列,直到不为null
    相同校验码不重复加入哈希表。

    源码:

    public class ServerCreateHash implements ServerCheckSumHashCreater {
    
    	/**
    	 * 记录校验块编号
    	 */
    	public int[][] sumIndex;
    	private String[][] mySums_table;
    
    	/**
    	 * 建立哈希表
    	 * 
    	 * @param filechecksum
    	 * @return
    	 * @throws IOException
    	 */
    	public String[][] buildHashTable(String filechecksum) throws IOException {
    
    		BufferedInputStream fileInputStream = new BufferedInputStream(
    				new FileInputStream(filechecksum));
    		return buildHashTable(fileInputStream);
    	}
    
    	/*
    	 * (non-Javadoc)
    	 * 
    	 * @see com.familyshare.pre.test.checkSumHashCreater#buildHashTable(java.io.
    	 * BufferedInputStream)
    	 */
    	@Override
    	public String[][] buildHashTable(InputStream in) throws IOException {
    		mySums_table = new String[TABLESIZE][HITNUM];
    		sumIndex = new int[TABLESIZE][HITNUM];
    		byte[] buffer1 = new byte[8];
    		byte[] buffer2 = new byte[16];
    		BufferedInputStream inStreamCheckSumFile = new BufferedInputStream(in);
    		int ordernum = 0;
    		byte end1[] = new byte[8];
    		byte end2[] = new byte[16];
    		Arrays.fill(end1, (byte) -1);
    		Arrays.fill(end2, (byte) -1);
    		inStreamCheckSumFile.read(buffer1);
    		inStreamCheckSumFile.read(buffer2);
    		//此处待优化
    		while (!Arrays.equals(buffer1, end1) && !Arrays.equals(buffer2, end2)) {
    			int index = (int) (DataConvertUtils.bytes2long(buffer1) % TABLESIZE);
    			int index2 = 0;
    			String md4 = Md4Checking.toHexString(buffer2);
    			boolean sameflag = false;
    			while (mySums_table[index][index2] != null && !sameflag) {
    				if (mySums_table[index][index2] != md4) {
    					index2++;
    				} else {
    					sameflag = true;
    				}
    			}
    			if (!sameflag) {
    				mySums_table[index][index2] = md4;
    				sumIndex[index][index2] = ordernum++;
    			}
    			inStreamCheckSumFile.read(buffer1);
    			inStreamCheckSumFile.read(buffer2);
    		}
    		// inStreamCheckSumFile.close();
    		return mySums_table;
    	}
    
    	/*
    	 * (non-Javadoc)
    	 * 
    	 * @see com.familyshare.pre.test.checkSumHashCreater#checkMatch(byte[], int)
    	 */
    	@Override
    	public int checkMatch(byte buffer[], int num) {
    		long sum1 = SumChecking.checkSum_Adler32(buffer, num);
    		// boolean find = false;
                    //此处需要优化,因为md4不一定用得到,应该放后面
    		String sum2 = Md4Checking.toHexString(Md4Checking.mdfour(buffer));
    		int index = (int) (sum1 % TABLESIZE);
    		int i = 0;
    
    		while (mySums_table[index][i] != null) {
    			if (mySums_table[index][i].equals(sum2)) {
    				// find = true;
    				return sumIndex[index][i] + 1;//返回匹配的校验块编号
    			}
    			i++;
    		}
    		return -1;
    		// return find;
    	}
    
    	public static void main(String args[]) throws IOException {
    		ServerCreateHash testCreateHash = new ServerCreateHash();
    		testCreateHash.buildHashTable(ServerCheckSumCreater.FILECHECKSUM);
    		byte[] buffer = new byte[] { 3 };
    		System.out.println(testCreateHash.checkMatch(buffer, 1));
    	}
    }
    


    展开全文
  • 文章目录哈希算法哈希函数的定义可靠哈希函数需满足的要求哈希函数的主要作用哈希实际例子Merkle Tree默克尔树完整性校验的方法哈希列表 Hash ListMerkle Tree 哈希树总结 哈希算法 哈希函数的定义   哈希函数:给...

    章节系列目录:点击跳转

    哈希算法

    哈希函数的定义

      哈希函数:给一个任意大小的数据生成出一个固定长度的数据,作为它的映射。
      你可以把哈希函数想象成“搅拌机”,一堆数据丢进去出来一段长度固定的16进制的数值就叫哈希值

    可靠哈希函数需满足的要求

    一个可靠的哈希算法要满足如下三点

    1.安全,给定数据 M 容易算出哈希值 X ,而给定 X 不能算出 M ,或者说哈希算法应该是一个单向算法。
    2.独一无二,两个不同的数据,要拥有不相同的哈希。
    3.长度固定,给定一种哈希算法,不管输入是多大的数据,输出长度都是固定的。

      如果哈希的长度是固定的,也就是取值范围是有限的,而输入数据的取值范围是无限的,所以总会找到两个不同的输入拥有相同的哈希。所以哈希函数的安全性是相对的。如果出现了两个不同输入有相同输出的情况,就叫碰撞(collision) 。不同的哈希算法,哈希位数越多,基本意味着安全级别越高,或者说它的”抗碰撞性“越好。

    消息A = 消息B 则 Hash(A) = Hash(B)
    逆否命题也成立:Hash(A) ≠ Hash(B) 则消息A ≠ 消息B
    而消息A ≠ 消息B 并不能推出 Hash(A) ≠ Hash(B)
    逆否命题:Hash(A) = Hash(B) 并不能推出 消息A = 消息B

    比如在网上都搜得到的汉字的哈希值有的就是一样的。
    “柳柴"与"柴柕” hashCode=851553
    “志捘"与"崇몈” hashCode=786017

    注意:后续章节我们使用哈希算法验证两者一致性时,就当它是几乎没有碰撞或者几率很小的情况,请大家不要钻这个牛角尖。

    哈希函数的主要作用

    为了保证哈希的独一无二性,如果数据在存储或者传输过程中有任何改动或者损坏,哪怕只有1bit,它的哈希值就一定会变。

    哈希函数的最常见的一个应用就是进行完整性校验( Integrity Check ),也就是检验数据无损坏。

    平时所看到的 Digest 摘要,有时候叫 Checksum 校验值,有时候叫 Fingerprint 指纹,其实都是哈希的另一种说法。

    哈希实际例子

    网站注册登录
      当我们提交用户名密码的时候,用户名被会直接保存到网站的数据库中,但是密码却不是直接保存的,而是先把密码转换成哈希,保存到数据库中的其实是哈希。即使是公司后台管理人员也拿不到用户的密码。这样万一公司数据库泄露了,用户的密码依然是安全的。而当用户自己登录网站的时候,输入密码提交到服务器,服务器上进行相同的哈希运算,只要算出来的哈希值是一样的,就认为你输入的密码是正确的。

    Merkle Tree默克尔树

      Merkle Tree也叫哈希树,Merkle Tree 就是用来做完整性校验的,所谓的完整性校验,就是检查一下数据有没有损坏或者被恶意篡改。Merkle Tree 的最大的应用场合就是在点对点网络上,Git 版本控制系统,IPFS 协议以及比特币以太坊等等项目

    完整性校验的方法

      要实现完整性校验,最简单的方法就是对要校验的整个的数据文件做个哈希运算,把得到的哈希值公布在网上,这样我们把数据下载到手之后,再次运算一下哈希值,如果运算结果相等,就表示我们下载过程中文件没有任何的损坏。如下图

      这种简单的采用哈希的方式做数据运算,比较适合数据本身不做分割且是放在一台服务器上的情况。如果去某个公司网站上去下载他们的一个软件,就会看到公司网站上公布了这个下载包的哈希值,有了这个哈希值,我们就可以放心的去下载这个软件,下载完做一下完整性校验,就知道这个软件没有损坏。甚至可以放心从其他的不可信网站上去下载这个软件包,因为有了校验机制,也一样可以保证这个包是跟官方的包一模一样的。

    哈希列表 Hash List

      在点对点网络上,数据往往都是拆分成很多小碎片去下载的,而且其中很多平台可以认为是不稳定或者是不可信的,很有可能因为网络问题导致下载中断,难不成要从头开始重新下载?这时需要有更加巧妙的做法。最简单的方式就是哈希列表(Hash List

      实际点对点网络在传输数据的时候,其实都是把比较大的一个文件切成一个个小的数据块。如果有一个小块数据在传输过程中损坏了, 那我只要重新下载这一个数据块就行了, 不用重新下载整个文件。当然这就要求对每个数据块计算哈希值,所有这些小数据块的哈希值都是兄弟关系,这样大家就组成了一个哈希列表。BT 下载的时候,在下载真正的数据之前,会先下载一个哈希列表的,这个就是所谓的种子文件。有了各个小块数据的 hash 之后,文件就可以从任意的机器上下载了,不用管那些机器是否是安全可信的。

    这时有一个问题就出现了,那么多的哈希,我们怎么保证它们本身都是正确地呢?

      我们需要一个根哈希,把每个小块的哈希值拼到一起,然后对整个这个长长的字符串再做一次哈希运算,最终的结果就是哈希列表的根哈希。于是,如果我们能够保证从一个绝对可信的网站,或者从我们的朋友手里拿到一个正确的根哈希,就可以用它来校验哈希列表中的每一个哈希都是正确的,进而可以保证下载的每一个数据块的正确性了。

      Hash List 也就是哈希列表形式,就非常适合在点对点网络上存储的大型数据了。

    Merkle Tree 哈希树

      Merkle Tree 本身也算是一个哈希列表,只不过是在这个基础上又引入了树形结构,从而获得了更高的灵活性。
      我们把数据分成小的数据块,然后对每个小的数据块进行哈希。但是往上走并不是直接去运算根哈希,而是把相邻的两个哈希合并成一个字符串,再对这个字符串的哈希,得到一个子哈希,如果最底层的哈希总数是单数,那到最后必然出现一个单身哈希,这种情况就直接对它进行哈希运算,所以也能得到它的子哈希。于是往上推,依然是一样的方式,可以得到数目更少的新一级哈希,到了树根的这个位置,这一代就剩下一个根哈希了,我们把它叫做 Merkle Root 。根哈希有时候也叫主哈希 Master Hash ,也有人叫它顶哈希 Top Hash

      相对于 Hash List,Merkle Tree 的明显的一个好处是可以单独拿出一个分支来(作为一个小树)对部分数据进行校验,这给很多使用场合就带来了哈希列表所不能比拟的灵活和高性能。


    Merkle Tree 是涉及到了数据结构中的3个概念:哈希、哈希列表、树。

    总结

      单个哈希不能担当大文件在分布式点对点网络上的校验工作,于是我们有了哈希列表的概念。 Merkle Tree 可以认为是哈希列表的一个变体,让哈希列表变得更加灵活高效,因为每次校验都可以单纯拿出树的一个分支来操作。




    文章资料参考自nervos网站


    关注、留言,我们一起学习。

    ----------------------Talk is cheap, show me the code-----------------------
    展开全文
  • 哈希简介

    2018-08-16 23:19:50
    在密码学中,hash算法的作用主要是用于消息摘要和签名,换句话说,它主要用于对整个消息的完整性进行校验。 1. 数据结构 使用Hash的数据结构叫做散列表,主要是为了提高查询的效率。也有直接译作哈希表,也叫Hash...

    Hash主要应用于数据结构中和密码学中。

    用于数据结构时,主要是为了提高查询的效率,这就对速度比较重视,对抗碰撞不太看中,只要保证hash均匀分布就可以。

    在密码学中,hash算法的作用主要是用于消息摘要和签名,换句话说,它主要用于对整个消息的完整性进行校验。

    1. 数据结构

    使用Hash的数据结构叫做散列表,主要是为了提高查询的效率。也有直接译作哈希表,也叫Hash表,

    Hash表是一种特殊的数据结构,它同数组、链表以及二叉排序树等相比较有很明显的区别,它能够快速定位到想要查找的记录,而不是与表中存在的记录的关键字进行比较来进行查找。这个源于Hash表设计的特殊性,它采用了函数映射的思想将记录的存储位置与记录的关键字关联起来,从而能够很快速地进行查找。

    2.密码学

    在密码学中,hash算法的作用主要是用于消息摘要和签名,换句话说,它主要用于对整个消息的完整性进行校验。

    举个用于消息摘要例子,银行的数据库中是不能保存用户密码的原文的,只能保存密码的hash值。在这种应用场景里,对于抗碰撞和抗篡改能力要求极高,对速度的要求在其次。一个设计良好的hash算法,其抗碰撞能力是很高的。

    需要注意的是,hash算法在密码学中,主要用于信息的摘要和完整性校验,而不是加密。

    概括来说,哈希(Hash)是将目标文本转换成具有相同长度的、不可逆的杂凑字符串(或叫做消息摘要),而加密(Encrypt)是将目标文本转换成具有不同长度的、可逆的密文。

     

          散列表(Hash table,也叫哈希表),是根据关键码值而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

    使用哈希查找有两个步骤:

    1. 使用哈希函数将被查找的键转换为数组的索引。在理想的情况下,不同的键会被转换为不同的索引值,但是在有些情况下我们需要处理多个键被哈希到同一个索引值的情况。所以哈希查找的第二个步骤就是处理冲突
    2. 处理哈希碰撞冲突。比如拉链法、开发地址法等。

    哈希函数:对不同情况采用不同的哈希函数。

            ①直接寻址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b,其中a和b为常数(这种散列函数叫做自身函数)。若其中H(key)中已经有值了,就往下一个找,直到H(key)中没有值了,就放进去。

            ②数字分析法:就是找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址。

            ③除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要,一般取素数或m

            ④平方取中法:当无法确定关键字中哪几位分布较均匀时,可以先求出关键字的平方值,然后按需要取平方值的中间几位作为哈希地址。这是因为:平方后中间几位和关键字中每一位都相关,故不同关键字会以较高的概率产生不同的哈希地址。

          通过构造性能良好的哈希函数,可以减少冲突,但一般不可能完全避免冲突,因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突,两种情况下解决冲突的方法应该一致。下面以创建哈希表为例,说明解决冲突的方法。常用的解决冲突方法有以下四种:

    ①开放定址法

    这种方法也称再散列法,其基本思想是:当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。这种方法有一个通用的再散列函数形式:

    Hi=(H(key)+di)% m   i=1,2,…,n

    其中H(key)为哈希函数,m 为表长,di称为增量序列。增量序列的取值方式不同,相应的再散列方式也不同。主要有以下三种:

        1》线性探测再散列

           dii=1,2,3,…,m-1

    这种方法的特点是:冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。

         2》二次探测再散列

           di=12,-12,22,-22,…,k2,-k2    ( k<=m/2 )

    这种方法的特点是:冲突发生时,在表的左右进行跳跃式探测,比较灵活。

        3》伪随机探测再散列

           di=伪随机数序列。

    具体实现时,应建立一个伪随机数发生器,(如i=(i+p) % m),并给定一个随机数做起点。

     

    例如,已知哈希表长度m=11,哈希函数为:H(key)= key  %  11,则H(47)=3,H(26)=4,H(60)=5,假设下一个关键字为69,则H(69)=3,与47冲突。

    如果用线性探测再散列处理冲突,下一个哈希地址为H1=(3 + 1)% 11 = 4,仍然冲突,再找下一个哈希地址为H2=(3 + 2)% 11 = 5,还是冲突,继续找下一个哈希地址为H3=(3 + 3)% 11 = 6,此时不再冲突,将69填入5号单元。

    如果用二次探测再散列处理冲突,下一个哈希地址为H1=(3 + 12)% 11 = 4,仍然冲突,再找下一个哈希地址为H2=(3 - 12)% 11 = 2,此时不再冲突,将69填入2号单元。

    如果用伪随机探测再散列处理冲突,且伪随机数序列为:2,5,9,……..,则下一个哈希地址为H1=(3 + 2)% 11 = 5,仍然冲突,再找下一个哈希地址为H2=(3 + 5)% 11 = 8,此时不再冲突,将69填入8号单元。

    ②再哈希法

          这种方法是同时构造多个不同的哈希函数:

    Hi=RH1(key)  i=1,2,…,k

    当哈希地址Hi=RH1(key)发生冲突时,再计算Hi=RH2(key)……,直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间。

    ③链地址法

           这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

    ④建立公共溢出区

            这种方法的基本思想是:将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表。

     

    优缺点

    开放散列(open hashing)【拉链法(针对桶链结构)

    1)优点: ①对于记录总数频繁可变的情况,处理的比较好(也就是避免了动态调整的开销) ②由于记录存储在结点中,而结点是动态分配,不会造成内存的浪费,所以尤其适合那种记录本身尺寸(size)很大的情况,因为此时指针的开销可以忽略不计了 ③删除记录时,比较方便,直接通过指针操作即可

    2)缺点: ①存储的记录是随机分布在内存中的,这样在查询记录时,相比结构紧凑的数据类型(比如数组),哈希表的跳转访问会带来额外的时间开销 ②如果所有的 key-value 对是可以提前预知,并之后不会发生变化时(即不允许插入和删除),可以人为创建一个不会产生冲突的完美哈希函数(perfect hash function),此时封闭散列的性能将远高于开放散列 ③由于使用指针,记录不容易进行序列化(serialize)操作

    封闭散列(closed hashing)【开放定址法(针对桶数组结构)】

    1)优点: ①记录更容易进行序列化(serialize)操作 ②如果记录总数可以预知,可以创建完美哈希函数,此时处理数据的效率是非常高

    2)缺点: ①存储记录的数目不能超过桶数组的长度,如果超过就需要扩容,而扩容会导致某次操作的时间成本飙升,这在实时或者交互式应用中可能会是一个严重的缺陷 ②使用探测序列,有可能其计算的时间成本过高,导致哈希表的处理性能降低 ③由于记录是存放在桶数组中的,而桶数组必然存在空槽,所以当记录本身尺寸(size)很大并且记录总数规模很大时,空槽占用的空间会导致明显的内存浪费 ④删除记录时,比较麻烦。比如需要删除记录a,记录b是在a之后插入桶数组的,但是和记录a有冲突,是通过探测序列再次跳转找到的地址,所以如果直接删除a,a的位置变为空槽,而空槽是查询记录失败的终止条件,这样会导致记录b在a的位置重新插入数据前不可见,所以不能直接删除a,而是设置删除标记。这就需要额外的空间和操作。

    查找性能:

           散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到,另一些关键码在散列函数得到的地址上产生了冲突,需要按处理冲突的方法进行查找。

           查找过程中,关键码的比较次数,取决于产生冲突的多少,产生的冲突少,查找效率就高,产生的冲突多,查找效率就低。因此,影响产生冲突多少的因素,也就是影响查找效率的因素。影响产生冲突多少有以下三个因素:

                           1. 哈希函数是否均匀;

                           2. 处理冲突的方法;

                           3. 哈希表的装填因子。

            散列表的装填因子:α= 填入表中的元素个数 / 散列表的长度

          α是散列表装满程度的标志因子。由于表长是定值,α与“填入表中的元素个数”成正比,所以,α越大,填入表中的元素较多,产生冲突的可能性就越大;α越小,填入表中的元素较少,产生冲突的可能性就越小。

    展开全文
  • 文件Hash校验.exe

    2020-04-09 09:08:58
    HASH是一个用于查看任意文件的哈希值的工具。Hash能查看的文件信息包括MD5、SHA1与CRC32,用户通过这些信息能够轻松了解到文件经过了哪些修改,对于防木马、防病毒、防盗版等方面有着非常重要的作用,快到碗里来
  • hash算法的作用是什么?

    千次阅读 2012-11-21 09:04:01
    Hash,一般翻译做"散列",也有直接音译为"哈希"的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常...
  • hash值--散列函数

    2020-07-08 14:49:05
    hash值,也叫散列函数。...哈希值的作用哈希值,即HASH值,是通过对文件内容进行加密运算得到的一组二进制值,主要用途是用于文件校验或签名。正是因为这样的特点,它常常用来判断两个文件是否相同。
  • (二)其作用主要是快速归纳和校验区块数据的完整性,它会将区块链中的数据分组进行哈希运算,向上不断的递归运算产生新的哈希节点,最终只剩下一个Merkle根存入区块头中,每个哈希节点总是包含两个相邻的数据块或其...
  • Bitcoin代码之MerkleTree

    2018-08-13 22:50:49
    Merkle树是一种哈希二叉树,它是一种用作快速归纳和校验大规模数据完整性的数据结构 2.Merkle Tree在区块链作用 merkle数在bitcoin里有2个主要作用 2.1归纳一个区块里全部交易为一个32字节值hash值。 这里写图片...
  • bitcoin代码之MerkleTree

    千次阅读 2018-03-02 14:32:01
    Merkle树是一种哈希二叉树,它是一种用作快速归纳和校验大规模数据完整性的数据结构 2.Merkle Tree在区块链作用 merkle数在bitcoin里有2个主要作用 2.1归纳一个区块里全部交易为一个32字节值hash值。 ​ ...
  • 在git中 , hash的一个重要作用是进行文件下载的校验(但是哈希结果是不区分大小写的) 二、 机制原理 1.版本数据管理机制 快照流 , 如果没有修改文件 , 就不保留 . 而只保留一个连接指向某一版本 只关心文件的整体是否
  • 大家应该明白哈希算法的主要三个作用,分别为:数据完整性校验、数据保密、快速查找。遇到相应的问题,能够想到使用哈希算法进行求解。 2. 分治法的步骤与要点——大问题分解成小问题、解决小问题、合并小问题的解...
  • redis cluster(集群)

    2019-12-30 23:32:50
    参考链接 redis中文官网 ...Redis 集群有16384个哈希槽,每个key通过CRC16校验后对16384取模来决定放置哪个槽.集群的每个节点负责一部分hash槽,举个例子,比如当前集群有3个节点,那么: 节点 A 包含...
  • 利用不完整文件的校验快所构成的哈希表顺序查询完整文件的校验块,从而得出匹配情况,并返回不匹配数据块及其相应编号,当然还有一些控制信息。由于该过程比较复杂,所以最好设计一个数据报,便于客户端分析和重组...
  • 作用:  任意长度的字符串内容通过摘要算法都可以生成唯一序列摘要值,通过摘要算法,可以校验某个文档或者某组字符串是否被修改。 应用:  1.文件内容一致性校验  2.用户登录验证 常用方法  update()----...
  • HMAC算法

    千次阅读 2018-04-18 20:37:10
    HMAC算法 HMAC(Hash Message Authentication Code),中文名“散列消息鉴别码”,主要是利用哈希算法,以一个密钥和一个消息为输入,生成一个消息摘要作为输出。 HMAC算法作用 数据完整性校验; 身份认证; HMAC ...
  • Linux命令介绍之md5sum

    2018-06-20 14:54:59
    md5sum md5校验命令,可以生成哈希值并比较用法:生成MD5文件[root@mail tmp]# md5sum passwd > passwd_md5比较[root@mail tmp]# md5sum -c passwd_md5 passwd: OK 生产中可以用作指纹作用,重要文件生成指纹存放...
  • 1、利用哈希值作为病毒特征 2、选取病毒内部的特征字符串 3、选取病毒内部的特色代码 4、双重校验和 网络特征 1、具体的下载URL或者访问的URL 2、IP地址 3、网络域名 注册表信息提取 1、启动项 2、写死的某个开关值 ...
  • K:hash的应用场景

    2018-05-30 09:17:00
    在密码学中,hash算法的作用主要是用于消息摘要和签名,换句话说,它主要用于对整个消息的完整性进行校验。 1. 数据结构 使用Hash的数据结构叫做散列表,主要是为了提高查询的效率。也有直接译作哈希表,也叫...
  • ios 加密

    2018-06-11 13:14:03
    -- 对称AESDES3DES-- 非对称-...作用 将加密的结果转成字符串 (可编码 可解码)-- 散列 (哈希) 算法- 算法公开- 不可逆MD5 --&gt; 不同的数据加密后的结果是定长的, 32个字符- 散列碰撞 不同的数据得到相同的HASH...
  • AES算法

    2017-12-14 15:52:11
    AES算法是典型的对称加密算法,它和其他我们常见的MD5,SHA的哈希摘要算法有很大的区别,主要体现在AES是可逆的,它主要的作用是来保证私密的信息不被泄漏,而摘要算法是不可逆的,是对信息一致性和完整性进行校验,...
  • JavaScript王者归来

    2013-01-10 11:30:48
    4.2.5 变量的作用域 4.3 表达式和运算符 4.3.1 表达式 4.3.2 运算符概述 4.3.3 算术运算符 4.3.4 关系运算符 4.3.5 逻辑运算符 4.3.6 位运算符 4.3.7 赋值运算符 4.3.8 其他运算符 4.3.8.1 条件运算符 4.3.8.2 逗号...
  • MySQL 5.1参考手册

    2018-10-15 11:12:46
    2.1.4. 通过MD5校验和或GnuPG验证软件包的完整性 2.1.5. 安装布局 2.2. 使用二进制分发版的标准MySQL安装 2.3. 在Windows上安装MySQL 2.3.1. Windows系统要求 2.3.2. 选择安装软件包 2.3.3. 用自动安装器安装...
  • 另外在配置 AOP 切面之前,我们需要了解下 aspectj 相关注解的作用: @Aspect:声明该类为一个注解类; @Pointcut:定义一个切点,后面跟随一个表达式,表达式可以定义为切某个注解,也可以切某个 package 下...
  • 2.1.4. 通过MD5校验和或GnuPG验证软件包的完整性 2.1.5. 安装布局 2.2. 使用二进制分发版的标准MySQL安装 2.3. 在Windows上安装MySQL 2.3.1. Windows系统要求 2.3.2. 选择安装软件包 2.3.3. 用自动安装器安装MySQL ...
  • MYSQL中文手册

    2013-03-11 21:21:34
    2.1.4. 通过MD5校验和或GnuPG验证软件包的完整性 2.1.5. 安装布局 2.2. 使用二进制分发版的标准MySQL安装 2.3. 在Windows上安装MySQL 2.3.1. Windows系统要求 2.3.2. 选择安装软件包 2.3.3. 用自动安装器安装...
  • 2.1.4. 通过MD5校验和或GnuPG验证软件包的完整性 2.1.5. 安装布局 2.2. 使用二进制分发版的标准MySQL安装 2.3. 在Windows上安装MySQL 2.3.1. Windows系统要求 2.3.2. 选择安装软件包 2.3.3. 用自动安装器安装MySQL ...

空空如也

空空如也

1 2
收藏数 27
精华内容 10
关键字:

哈希校验作用