精华内容
下载资源
问答
  • 近期有网友在博客中留言,希望俺介绍散列值校验文件的知识。所以俺干脆写一篇“文件完整性校验”的扫盲教程。由于本文是扫盲性质,尽量不涉及太技术化的内容。 ★啥是“完整性校验”? 所谓的“完整性校验”,...

    [转自外星人某大牛博客]
    近期有网友在博客中留言,希望俺介绍散列值校验文件的知识。所以俺干脆写一篇“文件完整性校验”的扫盲教程。由于本文是扫盲性质,尽量不涉及太技术化的内容。

    ★啥是“完整性校验”?

    所谓的“完整性校验”,顾名思义,就是检查文件是否完整。那么,什么情况下会导致文件不完整捏?大概有如下几种情况。

    1. 感染病毒
      比方说你的系统中了病毒,病毒感染了某个软件安装包或者某个可执行程序。那么该文件的完整性就被破坏了。

    2. 植入木马/后门
      还有一种文件不完整的情况,是被别有用心的人植入木马或后门。比方说某些国内的软件下载站点,它们提供的 Windows 安装光盘镜像已经被安置了后门。

    3. 传输故障
      这种情况主要发生在网络下载时。因为网络传输是有可能发生误码的(传输错误),另外还有可能下载到快结束的时候断线(没下载全)。这些情况都会导致你下载的文件不完整。
      如今的上网环境相比当年的 Modem 拨号,已经有明显改善。所以这种情况应该不多见了。

    ★散列算法(哈希算法)扫盲

    ◇什么是“散列算法/哈希算法”?

    这里所说的“散列”是一种计算机算法,洋文叫做 Hash,有时候也根据音译称为哈希。
      散列算法可以把【任意尺寸】的数据(原始数据)转变为一个【固定尺寸】的“小”数据(叫“散列值”或“摘要”)。

    ◇摘要长度

    对于某个具体的散列算法,得到的散列值长度总是固定的。散列值的长度又称“摘要长度”。
      以下是常见散列算法的摘要长度
    散列算法 散列值比特数 散列值字节数
    CRC32 32 4
    MD5 128 16
    SHA1 160 20
    SHA256 256 32
    SHA512 512 64

    ◇散列算法的特色

    1. 不可逆性
      从刚才的描述看,散列似乎有点像压缩。其实捏,散列算法跟压缩算法是完全不同滴。压缩算法是可逆的(可以把压缩后的数据再还原),而【散列算法是不可逆的】。
      还有一些人把散列算法称为“加密算法”,这也是不对的。因为加密算法是可逆的(“加密”的【逆操作】就是“解密”),而散列算法是【不可逆】的。

    2. 确定性
      通过某种散列算法,分别对两个原始数据计算散列值。如果算出来的散列值不同,那么可以 100% 肯定这两段数据是不同的——这就是“确定性”。
      但反过来,如果这两段数据的散列值相同,则只能说,这两段数据【非常可能】相同。所谓的“非常可能”,就是说,还达不到百分百。具体原因,请看下一节“散列函数的可靠性”。

    ★关于散列算法的【可靠性】

    ◇何为“散列碰撞”?

    刚才说了,存在非常小的可能性,导致两段不同的原始数据,计算出相同的散列值。这种情况称之为“散列碰撞”或“散列冲突”。

    ◇碰撞的类型

    散列碰撞的类型,大体上有两种:

    1. 随机碰撞
      随机碰撞就像买彩票中大奖,完全是出于小概率的偶然因素——你碰巧遇见两个不同的数据(文件),具有相同的散列值。
      理论上讲,任何散列算法都存在随机碰撞的可能性,只是可能性有大有小。

    2. 人为碰撞
      人为碰撞就是说,有人(通常是恶意的攻击者)故意制造散列碰撞,以此来骗过“基于散列值的完整性校验”。

    ◇如何避免碰撞

    1. 对于随机碰撞
      要避免随机碰撞,很简单,只需要选择摘要长度足够长的散列算法。
      拿前面举的3个例子。
      CRC32 的摘要长度是“32bit”,也就说,最多可以表示“2的32次方”这么多种可能性(也就是几十亿,数量级相当于地球总人口)。表面上看貌似很大,其实还不够大。比如当前互联网上的页面总数就已经大大超过“几十亿”。如果对每个页面计算 CRC32 散列,会碰到很多重复(碰撞)。
      而 MD5 的摘要长度是“128bit”,也就是【2的128次方】。这个数字足够大了。通俗地说,从宇宙诞生到宇宙毁灭,你都未必有机会碰见 MD5 的【随机碰撞】。而 SHA1 的摘要长度是“160bit”,那就更不用说了。

    2. 对于人为碰撞
      想避免人为碰撞,要同时兼顾两个因素——散列算法的摘要长度、散列算法的优秀程度。“摘要长度”刚才已经解释了。光说一下“算法的优秀程度”。
      如果某个散列算法有缺陷(不够优秀),那么攻击者就可以比较容易地构造出两个【不同的】原始数据,但却拥有【相同的】散列值。如此一来,就可以骗过基于散列算法的完整性检查。
      典型的例子就是 MD5——该算法在过去10多年里曾经非常流行,但是前几年被发现存在严重缺陷。所以,MD5 虽然“随机碰撞”的概率非常非常低,但“人为碰撞”的概率可【不低】。如果你比较注重安全性,【不要】再使用 MD5 进行完整性校验。

    再补充一下:
      随着硬件计算能力的提升,即便是 SHA1 也开始变得【不】安全了(参见如下博文中的密码学相关章节)。今后 SHA1 会逐步被 SHA256 或 SHA512 替代。
    《近期安全动态和点评(2019年2季度)》

    ★散列值校验的方法——使用网站提供的软件散列值

    如今,大伙儿的安全意识越来越高了。相应的,很多知名的软件,除了在官网上提供下载,还会相应提供下载软件的散列值。当你下载好某个软件之后,先在自己电脑里计算一下散列值,然后跟官方网站提供的散列值对比一下。如果散列值一样,通常就说明没问题。

    举例:Firefox 浏览器的散列校验
      打开如下链接,就可以看到 Firefox 某个版本的 SHA1 列表(把网址中的 版本号 三个字替换为具体的【三段式】版本号,比如18.0.2)。这个列表很长,包括各种语言,各个平台。为了方便起见,你可以先算好 SHA1 散列值,然后到里面搜索该散列值
    https://ftp.mozilla.org/pub/mozilla.org/firefox/releases/版本号/SHA1SUMS

    某些菜鸟读者可能会问:如何在自己电脑上计算某个软件的散列值?
      这就需要看下一个章节。

    ★散列值校验的方法——使用客户端工具计算散列值

    前面说完了校验的流程,最后再说一下校验的工具。
      考虑到大部分读者是 Windows 用户,俺介绍一下微软官方的 FCIV(洋文全称是“File Checksum Integrity Verifier”)。这是一个小巧、绿色、免费的命令行工具,下载页面在“这里”。
      因为是命令行工具,你需要先运行 CMD,出现 Windows 的命令行界面(黑窗口)之后,在其中使用该工具。下面是 FCIV 功能简介。

    ◇计算单个文件

    比如你有一个微软的系统安装光盘镜像,位于 C:\download\Windows.iso 那么,用如下命令可以计算该文件的 SHA1 散列值
    fciv -sha1 C:\download\Windows.iso

    ◇批量计算某个目录

    FCIV 支持批量计算某个目录下的文件散列值。比方说,可以用如下命令可以计算 C:\download 目录下的每一个文件的 SHA1
    fciv -sha1 C:\download\

    ◇批量计算并存储,供前后对比

    比如 C:\download 目录下有很多文件。俺想知道过一段时间之后,这些文件是否被改过。那么,可以先用如下命令,把该目录中所有文件的 SHA1 散列都存储到某个 XML 格式的文件中(本例中,俺假设保存的文件是当前目录的 hash.xml,你也可以保存到其它文件名)
    fciv -sha1 C:\download\ -xml hash.xml

    过了一段时间后,你可以用如下命令,就可以看出哪些文件被修改过。
    fciv -sha1 C:\download\ -xml hash.xml -v

    ★啥是“数字签名”?

    所谓的“数字签名”,通俗来说,就是采用某种技术手段来证明某个信息确实是由某个机构(或某个人)发布的。因为其用途有点类似于传统的手写签字,所以称之为“数字签名”。
      数字签名的技术实现需要依赖于“非对称加密技术”和“数字证书体系”。关于“非对称加密技术”,考虑到篇幅,今天就不展开了;关于“数字证书”,3年前写过一篇扫盲(在“这里”),有兴趣的同学可以瞧一瞧,这里就不再啰嗦了。

    ★Windows 平台的“数字签名”

    数字签名有很多种,大伙儿比较常见的是 Windows 平台下的数字签名。如今大型 IT 公司(比如“微软、Google、苹果”等)或者是知名开源组织发布的 Windows 软件,安装文件通常都内置数字签名。所以俺着重介绍 Windows 平台的数字签名该如何校验。

    ◇利用资源管理器验证单个文件

    大概从 Windows 2000开始,Windows 就支持在某个文件尾部附加数字签名,并且 Windows 的资源管理器内置了对数字签名的校验功能。
      下面俺通过几个截图,简单介绍一下:如何在资源管理器中验证数字签名。

    比如,俺手头有一个 Firefox 的安装文件(带有数字签名)。当俺查看该文件的属性,会看到如下的界面。眼神好的同学,会注意到到上面有个“数字签名”的标签页。如果没有出现这个标签页,就说明该文件没有附带数字签名。
    不见图 请翻墙

    选择该标签页,出现如下界面。
      顺便说一下,某些数字签名中没有包含“邮件地址”,那么这一项会显示“不可用”;同样的,某些数字签名没有包含“时间戳”,也会显示“不可用”。不要紧张,这里显示的“不可用”跟数字签名的有效性没关系。
    不见图 请翻墙

    一般来说,签名列表中,有且仅有一个签名。选中它,点“详细信息”按钮。跳出如下界面:
      通常这个界面会显示一行字:该数字签名正常(图中红圈标出)。如果有这行字,就说明该文件从出厂到你手里,中途没有被篡改过(是原装滴、是纯洁滴)。
    不见图 请翻墙

    如果该文件被篡改过了(比如,感染了病毒、被注入木马),那么对话框会出现一个警告提示:该数字签名无效(图中红圈标出),界面如下。一旦出现数字签名无效,那这个文件就不要再使用了。
    不见图 请翻墙

    ◇利用命令行工具批量验证

    用上面的图形化界面进行验证,比较傻瓜化。但有一个缺点——如果你要验证的文件比较多,一个一个去点对话框,手会抽筋滴。所以,俺再介绍一下命令行的工具,适合进行批量验证。
      这个命令行工具就是微软官网提供的【SigCheck】,由大名鼎鼎的 SysInternals 出品(SysInternals 已经被微软收购)。跟前面提到的 FCIV 类似,它也是一个小巧、绿色、免费的命令行工具,下载页面在“这里”。

    使用如下命令,可以批量检查某个目录下(包括多层嵌套子目录)的所有可执行程序,并且把“无签名”或者“签名无效”的文件列出来。
    sigcheck -u -e -s 某个目录的路径名
      先提醒一下:
      检查数字签名的有效性本身就比较慢,如果目录下的文件很多,你要有足够的耐心等它运行完毕。

    稍微补充一下,这个 SigCheck 命令还顺便提供了散列值(命令格式如下),该功能可替代 FCIV 的头两个功能,可惜无法替代 FCIV 的第三个功能。
    sigcheck -h 某个【目录】的路径名
    sigcheck -h 某个【文件】的路径名

    ★PGP/GPG 的数字签名

    刚才聊了 Windows 平台滴。但是,切莫以为只有 Windows 平台才提供数字签名——其它的数字签名工具还有好几种。名气比较大的数字签名工具当属 PGP/GPG。这两个缩写就像绕口令,很容易搞混。PGP 是商业软件,而 GPG 是 GnuPG 的缩写,是 GNU 的开源项目。后者是前者的开源替代品,两者的功能基本兼容。
      这俩玩意儿的功能很强悍,校验数字签名对它俩只是小菜一碟。考虑到大伙儿平时较少碰到 GPG 的签名,俺今天就偷懒一下,暂不介绍。以后如果有空,再专门写一篇帖子介绍 PGP/GPG 的各种功能和使用场景。

    展开全文
  • 近期有网友在博客中留言,希望俺介绍散列值校验文件的知识。所以俺干脆写一篇”文件完整性校验”的扫盲教程。由于本文是扫盲性质,尽量不涉及太技术化的内容。 ★什么是”完整性校验”?  所谓的”完整性校验...

    转自:http://jmchxy.blog.163.com/blog/static/746082322013121113818518/ 
    近期有网友在博客中留言,希望俺介绍散列值校验文件的知识。所以俺干脆写一篇”文件完整性校验”的扫盲教程。由于本文是扫盲性质,尽量不涉及太技术化的内容。

    ★什么是”完整性校验”?

      所谓的”完整性校验”,顾名思义,就是检查文件是否完整。那么,什么情况下会导致文件不完整捏?大概有如下几种情况。

      1. 感染病毒 
      比方说你的系统中了病毒,病毒感染了某个软件安装包或者某个可执行程序。那么该文件的完整性就被破坏了。

      2. 植入木马/后门/人为篡改 
      还有一种文件不完整的情况,是被别有用心的人植入木马或后门。比方说某些国内的软件下载站点,它们提供的 Windows 安装光盘镜像已经被安置了后门。

      3. 传输故障 
      这种情况主要发生在网络下载时。因为网络传输是有可能发生误码的(传输错误),另外还有可能下载到快结束的时候断线(下载不完整)。这些情况就会导致你下载的文件不完整。 
      如今的上网环境相比当年的Modem拨号,已经有明显改善。所以这种情况应该不多见了。

    ★散列算法(哈希算法)扫盲

    ◇什么是”散列算法/哈希算法”?

      这里所说的”散列”是一种计算机算法,洋文叫做 Hash,有时候也根据音译称为哈希。 
      散列算法可以把任意尺寸的数据(原始数据)转变为一个固定尺寸的”小”数据(叫”散列值”或”摘要”)。

    ◇摘要长度

      对于某个具体的散列算法,得到的散列值长度总是固定的。散列值的长度又称”摘要长度”。 
      以下是常见散列算法的摘要长度 
    CRC32 32比特(4字节) 
    MD5 128比特(16字节) 
    SHA1 160比特(20字节)

    ◇散列算法的特色

      1. 不可逆性 
      从刚才的描述看,散列似乎有点像压缩。其实捏,散列算法跟压缩算法是完全不同滴。压缩算法是可逆的(可以把压缩后的数据再还原),而散列算法是不可逆的。 
      还有一些人把散列算法称为”加密算法”,这也是不对的。因为加密算法是可逆的(”加密”的逆操作就是”解密”),而散列算法是不可逆的。

      2. 确定性 
      通过某种散列算法,分别对两个原始数据计算散列值。如果算出来的散列值不同,那么可以 100% 肯定这两段数据是不同的——这就是”确定性”。 
      但反过来,如果这两段数据的散列值相同,则只能说,这两段数据非常可能相同。所谓的”非常可能”,就是说,还达不到百分百。具体原因,请看下一节”散列函数的可靠性”。

    ★关于散列算法的可靠性

    ◇什么是”散列碰撞”?

      刚才说了,存在非常小的可能性,导致两段不同的原始数据,计算出相同的散列值。这种情况称之为”散列碰撞”或”散列冲突”。

    ◇碰撞的类型

      散列碰撞的类型,大体上有两种:

      1. 随机碰撞 
      随机碰撞就像买彩票中大奖,完全是出于小概率的偶然因素——你碰巧遇见两个不同的数据(文件),具有相同的散列值。 
      理论上讲,任何散列算法都存在随机碰撞的可能性,只是可能性有大有小。

      2. 人为碰撞 
      人为碰撞就是说,有人(通常是恶意的攻击者)故意制造散列碰撞,以此来骗过”基于散列值的完整性校验”。

    ◇如何避免碰撞

      1. 对于随机碰撞 
      要避免随机碰撞,很简单,只需要选择摘要长度足够长的散列算法。 
      拿前面举的3个例子。 
      CRC32 的摘要长度是 32bit,也就说,最多可以表示 “2的32次方” 这么多种可能性(也就是几十亿,数量级相当于地球总人口)。表面上看貌似很大,其实还不够大。比如当前互联网上的页面总数就已经大大超过几十亿。如果对每个页面计算 CRC32 散列,会碰到很多重复(碰撞)。 
      而 MD5 的摘要长度是128bit,也就是 2的128次方。这个数字足够大了。通俗地说,从宇宙诞生到宇宙毁灭,你都未必有机会碰见 MD5 的随机碰撞。而 SHA1 的摘要长度是160bit,那就更不用说了。

      2. 对于人为碰撞 
      想避免人为碰撞,要同时兼顾两个因素——散列算法的摘要长度、散列算法的优秀程度。”摘要长度”刚才已经解释了。光说一下”算法的优秀程度”。 
      如果某个散列算法有缺陷(不够优秀),那么攻击者就可以比较容易地构造出两个不同的原始数据,但却拥有相同的散列值。如此一来,就可以骗过基于散列算法的完整性检查。 
      典型的例子就是 MD5,MD5算法在过去10多年里曾经非常流行,但是前几年被发现存在严重缺陷。所以,MD5 虽然随机碰撞的概率非常非常低,但人为碰撞的概率可不低。如果你比较注重安全性,尽量不要依赖 MD5 进行完整性校验。

    ★散列值校验的步骤

      如今,大伙儿的安全意识越来越高了。相应的,很多知名的软件,除了在官网上提供下载,还会相应提供下载软件的散列值。当你下载好某个软件之后,先在自己电脑里计算一下散列值,然后跟官方网站提供的散列值对比一下。如果散列值一样,通常就说明没问题。再啰嗦一下,尽量不要用 MD5,改用 SHA1。

      下面,介绍几个常用软件的散列值页面,便于大伙儿查询

      微软的产品 
      到”这个页面”:http://msdn.microsoft.com/zh-cn/subscriptions/downloads/default.aspx

    可以查微软发布的所有产品的散列值。微软的产品很多,先根据类型或名称筛选,找到某产品后,点”详细信息”,就可以看到 SHA1 散列值。

      Firefox 浏览器 
      打开如下链接,可以看到 Firefox 某个版本的 SHA1 列表(把链接中的 XXXX 替换为版本号,比如18.0.2)。这个列表很长,包括各种语言,各个平台。为了方便起见,你可以先算好 SHA1 散列值,然后到里面搜索该散列值 
    https://ftp.mozilla.org/pub/mozilla.org/firefox/releases/XXXX/SHA1SUMS

    ★散列值校验的工具——FCIV

      前面说完了校验的流程,最后再说一下校验的工具。 
      考虑到大部分读者是 Windows 用户,俺介绍一下微软官方的 FCIV(全称是 File ChecksumIntegrity Verifier)。这是一个小巧、绿色、免费的命令行工具,下载页面在”这里”:http://support.microsoft.com/kb/841290/。 
      因为是命令行工具,你需要先运行 CMD,出现 Windows 的命令行界面(黑窗口)之后,在其中使用该工具。下面是 FCIV 功能简介。

    ◇计算单个文件

      比如你有一个微软的系统安装光盘镜像,位于C:\download\Windows.iso 那么,用如下命令可以计算该文件的 SHA1 散列值 
    fciv -sha1 C:\download\Windows.iso

    ◇批量计算某个目录

      FCIV 支持批量计算某个目录下的文件散列值。比方说,可以用如下命令可以计算 C:\download 目录下的每一个文件的 SHA1 
    fciv -sha1 C:\download\

    ◇批量计算并存储,供前后对比

      比如 C:\download 目录下有很多文件。俺想知道过一段时间之后,这些文件是否被改过。那么,可以先用如下命令,把该目录中所有文件的 SHA1 散列都存储到某个 xml 文件中(本例中,保存到 C:\hash.xml,你也可以保存到其它文件名) 
    fciv -sha1 C:\download\ -xml C:\hash.xml

      过了一段时间后,你可以用如下命令,就可以看出哪些文件被修改过。 
    fciv -sha1 C:\download\ -xml C:\hash.xml -v

    ★什么是”数字签名”?

      所谓的”数字签名”,通俗来说,就是采用某种技术手段来证明某个信息确实是由某个机构(或某个人)发布的。因为其用途有点类似于传统的手写签字,所以称之为”数字签名”。 
      数字签名的技术实现需要依赖于”非对称加密技术”和”数字证书体系”。考虑到篇幅,这里就不再啰嗦了。

    ★Windows 平台的”数字签名”

      数字签名有很多种,大伙儿比较常见的是 Windows 平台下的数字签名。如今大型 IT 公司(比如:微软、Google、苹果、等)或者是知名开源组织发布的 Windows 软件,安装文件通常都内置数字签名。所以俺着重介绍 Windows 平台的数字签名该如何校验。

    ◇利用资源管理器验证单个文件

      大概从 Windows 2000开始,Windows 就支持在某个文件尾部附加数字签名,并且 Windows 的资源管理器内置了对数字签名的校验功能。 
      下面俺通过几个截图,简单介绍一下:如何在资源管理器中验证数字签名。

      比如,俺手头有一个 Firefox 的安装文件(带有数字签名)。当俺查看该文件的属性,会看到如下的界面。眼神好的同学,会注意到到上面有个”数字签名”的标签页。如果没有出现这个标签页,就说明该文件没有附带数字签名。

      选择该标签页,出现如下界面。 
      顺便说一下,某些数字签名中没有包含”邮件地址”,那么这一项会显示”不可用”;同样的,某些数字签名没有包含”时间戳”,也会显示”不可用”。不要紧张,这里显示的”不可用”跟数字签名的有效性没关系。

      一般来说,签名列表中,有且仅有一个签名。选中它,点”详细信息”按钮。跳出如下界面: 
      通常这个界面会显示一行字:”该数字签名正常”(图中红圈标出)。如果有这行字,就说明该文件从出厂到你手里,中途没有被篡改过(是原装滴、是纯洁滴)。

      如果该文件被篡改过了(比如,感染了病毒、被注入木马),那么对话框会出现一个警告提示”该数字签名无效”,界面如下。一旦出现数字签名无效,那这个文件就不要再使用了。

    ◇利用命令行工具批量验证

      用上面的图形化界面进行验证,比较傻瓜化。但有一个缺点——如果你要验证的文件比较多,一个一个去点对话框,手会抽筋滴。所以,俺再介绍一下命令行的工具,适合进行批量验证。 
      这个命令行工具就是微软官网提供的 SigCheck,由大名鼎鼎的 SysInternals 出品(SysInternals 已经被微软收购)。跟前面提到的 FCIV 类似,它也是一个小巧、绿色、免费的命令行工具,下载页面在”这里”:http://technet.microsoft.com/en-us/sysinternals/bb897441.aspx

      使用如下命令,可以批量检查某个目录下(包括多层嵌套子目录)的所有可执行程序,并且把”无签名”或者”签名无效”的文件列出来。

    sigcheck -u -e -s 某个目录的路径名 
    先提醒一下,检查数字签名的有效性本身就比较慢,如果目录下的文件很多,你要有足够的耐心等它运行完毕。

      稍微补充一下,这个 SigCheck 命令还顺便提供了散列值(命令格式如下),该功能可替代 FCIV 的头两个功能,可惜无法替代 FCIV 的第三个功能。 
    sigcheck -h 某个目录或文件的路径名

    ★PGP/GPG 的数字签名

      刚才聊了 Windows 平台滴。但是,切莫以为只有 Windows 平台才提供数字签名——其它的数字签名工具还有好几种。名气比较大的数字签名工具当属 PGP/GPG。这两个缩写就像绕口令,很容易搞混。PGP 是商业软件,而 GPG 是 GnuPG 的缩写,是 GNU 的开源项目。后者是前者的开源替代品,两者的功能基本兼容。 
      这俩玩意儿的功能很强悍,校验数字签名对它俩只是小菜一碟。考虑到大伙儿平时较少碰到 GPG 的签名,俺今天就偷懒一下,暂不介绍。以后如果有空,再专门写一篇帖子介绍 PGP/GPG 的各种功能和使用场景。

    __ Information from ESET NOD32 Antivirus, version of virus signaturedatabase 7356 (20120804) __

    The message was checked by ESET NOD32 Antivirus.

    http://www.eset.com

    展开全文
  • 服务器散列值与客户端计算 内容精选换一换根据后端云服务器组的ID查询后端云服务器组详情。GET /v2/{project_id}/elb/pools/{pool_id}无请求样例1 查询后端云服务器组的详情GET ...

    服务器散列值与客户端计算 内容精选

    换一换

    c8a5a5028d2cabfeeee0907ef5119e7e.png

    根据后端云服务器组的ID查询后端云服务器组详情。GET /v2/{project_id}/elb/pools/{pool_id}无请求样例1 查询后端云服务器组的详情GET https://{Endpoint}/v2/1867112d054b427e808cc6096d8193a1/elb/pools/5a9a3e9e-d1aa-448e

    云桌面支持通过瘦终端(TC)、软终端(中标麒麟、UOS、Windows 7和Windows 10操作系统)以及浏览器方式接入,多种登录方式可让您灵活存取文件以及使用应用,实现移动办公。其中软终端方式无需额外配置设备,可通过本地PC的安装的客户端接入桌面,方便快捷。您可以依据以下操作方式通过软终端登录桌面。通过软终端方式登录桌面(arm 版

    服务器散列值与客户端计算 相关内容

    TCP协议适用于注重可靠性,对数据准确性要求高,速度可以相对较慢的场景,如文件传输、发送或接收邮件、远程登录等。您可以添加一个TCP监听器转发来自TCP协议的请求。登录管理控制台。在管理控制台左上角单击图标,选择区域和项目。单击页面左上角的,选择“网络 > 弹性负载均衡”。在“负载均衡器”界面,单击需要添加监听器的负载均衡名称。切换到“监

    为云服务器添加tags。需在客户端通过以下HTTP header指定微版本号:X-OpenStack-Nova-API-Version: 2.26。PUT /v2.1/{project_id}/servers/{server_id}/tags参数说明请参见表1。参数说明参数是否必选描述project_id是项目ID。获取方法请参见获取项目

    服务器散列值与客户端计算 更多内容

    55a2638139d68369d49b3058cd5d88e8.png

    每台后端服务器的权重取值范围为[0, 100]。新的请求不会转发到权重为0的后端服务器上,此时健康检查状态没有参考意义。以下三种算法支持权重设置。在加权轮询算法中,每台后端服务器的权重取值范围为[0, 100]。新的请求不会转发到权重为0的后端。在非0的权重下,负载均衡器会将请求按权重值的大小分配给所有的后端服务器。当后端服务器的权重都设

    d57a9c4df2ad6d5977a2dea882116132.png

    查询裸金属服务器的所有标签。需在客户端通过以下HTTP header指定微版本号:X-OpenStack-Nova-API-Version: 2.26。GET /v2.1/{project_id}/servers/{server_id}/tags参数说明请参见表1。请求参数无无请求样例GET https://{ECS Endpoint}/

    399bb9e39ad395cd7fb119c5287fddf8.png

    云桌面支持通过瘦终端(TC)、软终端(中标麒麟、UOS、Windows 7和Windows 10操作系统)以及浏览器方式接入,多种登录方式可让您灵活存取文件以及使用应用,实现移动办公。其中软终端方式无需额外配置设备,可通过本地PC的安装的客户端接入桌面,方便快捷。您可以依据以下操作方式通过软终端登录桌面。通过软终端方式登录桌面(arm 版

    d151cefbfd54a36eb240c5cc85e1151a.png

    删除裸金属服务器的所有标签。需在客户端通过以下HTTP header指定微版本号:X-OpenStack-Nova-API-Version: 2.26。“__type_baremetal”标识是一台裸金属服务器,建议不要删除“__type_baremetal”标签,否则,裸金属服务器将仅在ECS控制台可见,而不在BMS控制台。“__typ

    631651361fa2e5698f6a9d681fb5668c.png

    SSH方式连接弹性云服务器,出现卡顿,需要较长时间才可以连接。服务端sshd服务开启UseDNS选项状态下,当客户端试图使用SSH连接服务器时,服务器端先根据客户端的IP地址进行DNS PTR反向查询出客户端的主机名,然后根据查询出的客户端主机名进行DNS正向A记录查询,验证与其原始IP地址是否一致,这是防止客户端欺骗的一种措施,但一般我

    b139ef593fb8558052cf7d856d8ac3a5.png

    当目的迁移任务执行失败时,提示“sms.3802 与目的服务器建立SSH连接失败”。linux文件级迁移时,源端会和目的端服务器建立一个SSH连接用于传输数据。如果无法成功建立SSH连接,则会提示该错误。建议您参考本章节操作步骤排查SSH无法连接的原因。检查目的端是否被关机检查目的端安全组22端口是否被关闭或指定了一个非源端IP检查源端网

    784b2dc537fb8677eac9c3453eafe288.png

    为裸金属服务器添加标签。需在客户端通过以下HTTP header指定微版本号:X-OpenStack-Nova-API-Version: 2.26。标签个数不超过50个。建议为裸金属服务器添加“__type_baremetal”标签,标识是一台裸金属服务器。否则,裸金属服务器将仅在ECS控制台可见,而不在BMS控制台。新增标签时,会覆盖原

    c8670e33c445c10cd2a0fcb5ca15332b.png

    用户在弹性云服务器里可以通过一键部署客户端的方法,使用GeoMesa Shell和HBase Shell访问集群。使用一键部署客户端工具,建议Linux弹性云服务器的操作系统类型为EulerOS,CentOS,Ubuntu和SUSE。具体操作请参见准备弹性云服务器章节。执行如下命令,获取客户端一键部署工具:登录表格存储服务管理控制台,在左

    118fcc6f8f8a59b8317188ff10d93c94.png

    华为云帮助中心,为用户提供产品简介、价格说明、购买指南、用户指南、API参考、最佳实践、常见问题、视频帮助等技术文档,帮助您快速上手使用华为云服务。

    784dc64e49dbbf1bc7916486d97eab2c.png

    本章节指导您使用MongoDB客户端和Robo 3T工具,通过公网连接GaussDB(for Mongo)集群实例。操作系统使用场景:弹性云服务器的操作系统以Linux为例,客户端本地使用的计算机系统以Windows为例。GaussDB(for Mongo)集群实例需要绑定弹性公网IP并设置安全组规则,请分别参见步骤二:绑定弹性公网IP和

    359866fbd3d89c6b4b0a93acc1fa4c87.png

    负载均衡的访问日志功能支持查看和分析对七层负载均衡HTTP和HTTPS进行请求的详细访问日志记录,包括请求时间、客户端IP地址、请求路径和服务器响应等。配置访问日志时需要您对接云日志服务,并且已经创建需要关联的云日志组和日志流。目前只有七层共享型负载均衡支持此功能,四层共享型负载均衡不支持。当前支持的区域:华北-北京四、华北-北京一、华东

    展开全文
  • HASH 散列介绍

    2020-12-05 22:21:58
    散列函数(英语:Hash function)又称散列算法、哈希函数,是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要,使得数据量变小,将数据的格式固定下来。该函数函数将数据打乱混合...

    Hash

    音译:哈希
    翻译:散列

    0. 计算机常见

    • 哈希函数(Hash function):将数据编码成固定的小尺寸;用于哈希表和密码学
    • 哈希表(Hash table):使用哈希函数的数据结构 {key, value}

    1. 哈希函数

    1.1 定义

    散列函数(英语:Hash function)又称散列算法哈希函数,是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要,使得数据量变小,将数据的格式固定下来。该函数函数将数据打乱混合,重新创建一个叫做散列值(hash values,hash codes,hash sums,或hashes)的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。好的散列函数在输入域中很少出现散列冲突。在散列表数据处理中,不抑制冲突来区别数据,会使得数据库记录更难找到。

    如今,散列算法也被用来加密存在数据库中的密码(password)字符串,由于散列算法所计算出来的散列值(Hash Value)具有不可逆(无法逆向演算回原本的数值)的性质,因此可有效的保护密码。

    1.2 散列函数的性质

    优秀的 Hash 函数性质

    • 确定性(单向散列函数):如果两个散列值是不相同的(根据同一函数),那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果,具有这种性质的散列函数称为单向散列函数

      输入数据的微小变化会得到完全不同的hash值,相同的数据会得到相同的值
      md5("这是一个测试文案");	==>	输出结果:2124968af757ed51e71e6abeac04f98d
      md5("这是二个测试文案");	==>	输出结果:bcc2a4bb4373076d494b2223aef9f702
      可以看到我们只改了一个文字,但是整个得到的hash值产生了非常大的变化。
      
    • 较小散列碰撞(collision):散列函数的输入和输出不是唯一对应关系的,如果两个散列值相同,两个输入值很可能是相同的,但也可能不同。这通常是两个不同长度的输入值,计算出相同的输出值。

      由于hash的原理是将输入空间的值映射成hash空间内,而hash值的空间远小于输入的空间。
      根据抽屉原理,一定会存在不同的输入被映射成相同输出的情况。
      那么作为一个好的hash算法,就需要这种冲突的概率尽可能小。
      
    • 不可逆性:从hash值不可以反向推导出原始的数据

      1. 这个从上面 MD5 的例子里可以明确看到,经过映射后的数据和原始数据没有对应关系
      2. 为什么有 MD5 类似解密?
      	- 数据库中对应取出
      
    • 高效性:哈希算法的执行效率要高效,长的文本也能快速地计算出哈希值

    1.3 散列函数的应用

    1.3.1 散列表

    散列表是散列函数的一个主要应用,使用散列表能够快速的按照关键字查找数据记录。(注意:关键字不是像在加密中所使用的那样是秘密的,但它们都是用来“解锁”或者访问数据的。)例如,在英语字典中的关键字是英文单词,和它们相关的记录包含这些单词的定义。在这种情况下,散列函数必须把按照字母顺序排列的字符串映射到为散列表的内部数组所创建的索引上。

    散列表散列函数的几乎不可能理想是把每个关键字映射到唯一的索引上,因为这样能够保证直接访问表中的每一个数据。一个好的散列函数(包括大多数加密散列函数)具有均匀的真正随机输出,因而平均只需要一两次探测(依赖于装填因子)就能找到目标。同样重要的是,随机散列函数不太会出现非常高的冲突率。但是,少量的可以估计的冲突在实际状况下是不可避免的。

    1.3.2 保护资料

    散列值可用于唯一地识别机密信息。这需要散列函数是抗碰撞(collision-resistant)的,意味着很难找到产生相同散列值的资料。散列函数分类为密码散列函数和可证明的安全散列函数。第二类中的函数最安全,但对于大多数实际目的而言也太慢。透过生成非常大的散列值来部分地实现抗碰撞。例如,SHA-2是最广泛使用的密码散列函数之一,它生成256比特值。

    1.3.3 确保传递真实的信息

    消息或数据的接受者确认消息是否被篡改的性质叫数据的真实性,也称为完整性。发信人通过将原消息和散列值一起发送,可以保证真实性。

    1.3.4 错误校正

    使用一个散列函数可以很直观的检测出数据在传输时发生的错误。在数据的发送方,对将要发送的数据应用散列函数,并将计算的结果同原始数据一同发送。在数据的接收方,同样的散列函数被再一次应用到接收到的数据上,如果两次散列函数计算出来的结果不一致,那么就说明数据在传输的过程中某些地方有错误了。这就叫做冗余校验

    校正错误时,至少会对可能出现的扰动大致假定一个分布模式。对于一个信息串的微扰可以被分为两类,大的(不可能的)错误和小的(可能的)错误。我们对于第二类错误重新定义如下,假如给定H(x)和x+s,那么只要 s 足够小,我们就能有效的计算出 x。那样的散列函数被称作错误校正编码。这些错误校正编码有两个重要的分类:循环冗余校验里德-所罗门码

    1.3.5 语音识别

    对于像从一个已知列表中匹配一个MP3文件这样的应用,一种可能的方案是使用传统的散列函数——例如MD5,但是这种方案会对时间平移、CD读取错误、不同的音频压缩算法或者音量调整的实现机制等情况非常敏感。使用一些类似于MD5的方法有利于迅速找到那些严格相同(从音频文件的二进制数据来看)的音频文件,但是要找到全部相同(从音频文件的内容来看)的音频文件就需要使用其他更高级的算法了。

    分析正在播放的音乐,并将它于存储在数据库中的已知的散列值进行比较。用户就能够收到被识别的音乐的曲名。

    1.4 目前常见的散列算法

    算法名称输出大小(bits)内部大小区块大小长度大小字符尺寸碰撞情形
    HAVAL256/224/192/160/12825610246432
    MD2128384128No8大多数
    MD41281285126432
    MD51281285126432
    PANAMA256873625632
    RIPEMD1281285126432
    RIPEMD-128/256128/256128/2565126432
    RIPEMD-160/320160/320160/3205126432
    SHA-01601605126432
    SHA-11601605126432有缺陷
    SHA-256/224256/2242565126432
    SHA-512/384512/384512102412864
    Tiger(2)-192/160/128192/160/1281925126464
    WHIRLPOOL5125125122568

    2. 哈希表

    2.1 定义

    散列表Hash table,也叫哈希表),是根据键(Key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数存放记录的数组称做散列表

    2.2 基本概念

    • 若关键字为 k {\displaystyle k} k,则其值存放在 f ( k ) {\displaystyle f(k)} f(k) 的存储位置上,称这个对应关系 f {\displaystyle f} f 为散列函数,按这个思想建立的表为散列表。不需比较便可直接取得所查记录。
    • 对不同的关键字可能得到同一散列地址,即 k 1 ≠ k 2 {\displaystyle k_{1}\neq k_{2}} k1=k2,而 f ( k 1 ) = f ( k 2 ) {\displaystyle f(k_{1})=f(k_{2})} f(k1)=f(k2) ,这种现象称为碰撞(英语:Collision)。具有相同函数值的关键字对该散列函数来说称做同义词。
    • 根据散列函数 f ( k ) {\displaystyle f(k)} f(k)处理冲突的方法 将一组关键字映射到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“映像”作为记录在表中的存储位置,这种表便称为散列表,这一映射过程称为散列造表或散列,所得的存储位置称散列地址。
    • 若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function),这就使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。

    2.3 构造散列函数

    散列函数能使对一个数据序列的访问过程更加迅速有效,通过散列函数,数据元素将被更快定位。

    2.3.1 直接定址法

    取关键字或关键字的某个线性函数值为散列地址。即 h a s h ( k ) = k {\displaystyle hash(k)=k} hash(k)=k h a s h ( k ) = a ⋅ k + b {\displaystyle hash(k)=a\cdot k+b} hash(k)=ak+b ,其中 a   b {\displaystyle a\,b} ab 为常数(这种散列函数叫做自身函数)

    1. hash(k) = k

    举例1:统计1-100岁的人口,其中 年龄 作为关键字,哈希函数取关键字本身。

    查找年龄25岁的人口有多少,则直接查表中第25项。

    地址A0A1……A98A99
    年龄12……99100
    人数980800……495107
    1. hash(k) = a * k + b

    举例2:统计解放以后出生人口,其中 年份 作为关键字,哈希函数取关键字自身加一个常数 H(key)=key+(-1949)。

    查找 2000 年出生的人数,则直接查 (2000-1949)=51 项即可。

    地址A0A1……A98A99
    年份19491950……20472048
    人数980800……495107

    提示:

    • 直接定址法获取得到的散列函数有点就是简单,均匀也不会产生冲突但问题是这需要事先知道关键字的分布情况。

    • 适合查找表较小且连续的情况,地址集合的大小 = = 关键字集合的大小,其中a和b为常数。由于这样的限制,在现实应用中,此方法虽然简单,但却并不常用。

    2.3.2 数字分析法

    假设关键字是以 r 为基的数,并且哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干数位组成哈希地址。数字分析法是取数据元素关键字中某些取值较均匀(数值不一样)的数字位作为哈希地址的方法。即当关键字的位数很多时,可以通过对关键字的各位进行分析,丢掉分布不均匀的位,作为哈希值。

    举例1:有 80 个记录,其关键字为8位十进制数,假设哈希表长,则可取两位十进制数组成哈希地址,为了尽量避免冲突,可先分析关键字。

    k0  = 84595839
    k1  = 84598344
    k2  = 84593928
    k3  = 84592162
     ···
    k76 = 84211211
    k77 = 84214657
    k78 = 84219732
    k79 = 84217476
    

    经分析,发现第一位都是8,第二位都是4,第三位只可能取5或2,第四位只可能取9或1,所以这四位不可取,那么对于第五、六、七、八位可看成是随机的,可取这四位作为哈希地址。

    举例2:手机号前三位是接入号,中间四位是 HLR 识别号,只有后四位才是真正的用户号,也就是说,如果手机号作为关键字,那么极有可能前 7 位是相同的,此时我们选择后四位作为散列地址就是不错的选择。

    提示:

    • 目的就是为了提供一个能够尽量合理地将关键字分配到散列表的各个位置的散列函数
    • 能预先估计出全体关键字的每一位上各种数字出现的频度,它只适合于所有关键字值已知的情况。通过分析分布情况把关键字取值区间转化为一个较小的关键字取值区间
    • 对于抽取出来的数字,还可以再进行反转,右环位移,左环位移等操作

    2.3.3 平方取中法

    关键字平方的中间位数作为散列地址

    举例:若设哈希表长为1000则可取关键字平方值的中间四位

    关键字关键字的平方哈希函数值
    1234015227565227
    2143045924495924
    4132170734240734
    3214103297963297
    #include <stdio.h>
    
    // 哈希函数将返回 key * key 的中间 4 位
    int Hash(int key) {
        // 计算 key 的平方
        key = key * key;
        printf("%08d\n", key);
        // 去掉低 2 位
        key = key / 100;
        // 取低 4 位,即平方中间 4 位
        key = key % 10000;
        return key;
    }
    
    int main(int argc, char* argv[]) {
        int key = 1234;
        int ret = Hash(key);
        printf("%04d\n", ret);
        return 0;
    }
    

    提示:

    • 平方取中法比较适合不知道关键字的分布,而位数又不是很大的情况

    2.3.4 折叠法

    将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址。

    两种叠加处理的方法:

    • 移位叠加:将分 割后的几部分低位对齐相加
    • 边界叠加:从一端沿分割界来回折叠,然后对齐相加

    举例:当哈希表长为1000时,关键字key=110108331119891,允许的地址空间为三位十进制数,则这两种叠加情况如图:

    	移位叠加							 边界叠加
    	891									891
    	119									911
    	331									331
    	108									801
      + 110								  + 110
    --------------                      -------------
     (1)559								 (3)044
    
    /***************************************************************************
     * @date    2020/12/05
     * @brief   从后面开始折叠,key 为关键字,len 为返回长度
     ***************************************************************************/
    #include <malloc.h>
    #include <math.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    char* reverse(char* str) {
        int   len  = strlen(str);
        char* temp = (char*)malloc(sizeof(char) * (len + 1));
        for (int i = 0; i < len; i++) {
            temp[i]           = str[len - 1 - i];
        }
        temp[len] = '\0';
        return temp;
    }
    
    // 移位折叠
    int fold(char* key, int len) {
        int    n   = (strlen(key) % len == 0) ? (strlen(key) / len) : (strlen(key) / len + 1);
        char** str = (char**)malloc(sizeof(char*) * n);
        for (int i = 0; i < n; i++) {
            *(str + i) = (char*)malloc(sizeof(char) * (len + 1));
            memset(*(str + i), '\0', sizeof(*(str + i)));
            if (i < n - 1 || strlen(key) % len == 0) {
                strncpy(*(str + i), key + strlen(key) - (i + 1) * len, len);
            } else {
                strncpy(*(str + i), key, strlen(key) % len);
            }
            printf("%d: %s\n", i, *(str + i));
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += atoi(*(str + i));
        }
        return (sum >= pow(10, len)) ? (sum % (int)pow(10, len)) : sum;
    }
    
    // 边界折叠
    int fold2(char* key, int len) {
        int    n   = (strlen(key) % len == 0) ? (strlen(key) / len) : (strlen(key) / len + 1);
        char** str = (char**)malloc(sizeof(char*) * n);
        for (int i = 0; i < n; i++) {
            *(str + i) = (char*)malloc(sizeof(char) * (len + 1));
            memset(*(str + i), '\0', sizeof(*(str + i)));
            if (i < n - 1 || strlen(key) % len == 0) {
                strncpy(*(str + i), key + strlen(key) - (i + 1) * len, len);
            } else {
                strncpy(*(str + i), key, strlen(key) % len);
            }
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                sum += atoi(*(str + i));
            } else {
                sum += atoi(reverse(*(str + i)));
            }
        }
        return (sum >= pow(10, len)) ? (sum % (int)pow(10, len)) : sum;
    }
    
    int main(int argc, char* argv[]) {
        char* key  = (char*)"110108331119891";
        int   len  = 3;
        int   ret  = fold(key, len);
        int   ret2 = fold2(key, len);
        printf("%d\n", ret);
        printf("%d\n", ret2);
        return 0;
    }
    

    提示:

    • 折叠法事先不需要知道关键字的分布,适合关键字位数较多的情况

    2.3.5 伪随机数法

    选择一个随机数,取关键字随机函数值为它的散列地址 f ( k ) = r a n d o m ( k e y ) f(k) = random(key) f(k)=random(key)

    #include <stdio.h>
    #include <stdlib.h>
    
    int my_random(int key) {
        return rand_r((unsigned int*)&key);
    }
    
    int main(int argc, char* argv[]) {
        int key = 10;
        int ret = my_random(key);
        printf("%d\n", ret);
        return 0;
    }
    

    提示:

    • 此法适于:当关键字的长度不等采用这个方法构造散列函数是比较合适
    • 实际造表时,采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态),以及哈希表 长度(哈希地址范围),总的原则是使产生冲突的可能性降到尽可能地小

    2.3.6 除留余数法

    取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址。即
    h a s h ( k ) = k     m o d    p p ≤ m { hash(k)=k\,{\bmod {\,}}p} \qquad { p\leq m} hash(k)=kmodppm

    例如,已知待散列元素为(18,75,60,43,54,90,46),表长 m=10,p=7,则有
        h(18)=18 % 7=4    h(75)=75 % 7=5    h(60)=60 % 7=4   
        h(43)=43 % 7=1    h(54)=54 % 7=5    h(90)=90 % 7=6   
        h(46)=46 % 7=4
    
    此时冲突较多。为减少冲突,可取较大的 m 值和 p 值,如 m=p=13,结果如下:
        h(18)=18 % 13=5    h(75)=75 % 13=10    h(60)=60 % 13=8    
        h(43)=43 % 13=4    h(54)=54 % 13=2     h(90)=90 % 13=12   
        h(46)=46 % 13=7
    
    #include <stdio.h>
    
    int my_mod(int key, int p) {
        return key % p;
    }
    
    int main(int argc, char* argv[]) {
        int key[] = {18, 75, 60, 43, 54, 90, 46};
        int m     = 13;
        int p     = m;
        for (int i = 0; i < sizeof(key) / sizeof(key[0]); i++) {
            int ret = my_mod(key[i], p);
            printf("%d ", ret);
        }
        return 0;
    }
    

    提示:

    • 此方法为最常用的构造散列函数方法
    • 若散列表表长为 m 通常 p 为小于或等于表长(最好接近 m )的最小质数或不包含小于 20 质因子的合数
    • 不仅可以对关键字直接取模,也可在折叠法、平方取中法等运算之后取模。对p的选择很重要,一般取素数或m,若p选择不好,容易产生冲突。

    2.3.7 减去法

    f ( k ) = k − b f(k) = k-b f(k)=kb

    举例:公司有一百个员工,而员工的编号介于1001到1100,减去法就是员工编号减去1000后即为数据的位置。编号1001员工的数据在数据中的第一笔。编号1002员工的数据在数据中的第二笔…依次类推。从而获得有关员工的所有信息,因为编号1000以前并没有数据,所有员工编号都从1001开始编号。

    2.3.8 基数转换法

    将十进制数X看作其他进制,比如十三进制,再按照十三进制数转换成十进制数,提取其中若干为作为X的哈希值。一般取大于原来基数的数作为转换的基数,并且两个基数应该是互素的。

    举例: H a s h ( 80127429 ) = ( 80127429 ) 13 = 8 ∗ 1 3 7 + 0 ∗ 1 3 6 + 1 ∗ 1 3 5 + 2 ∗ 1 3 4 + 7 ∗ 1 3 3 + 4 ∗ 1 3 2 + 2 ∗ 1 3 1 + 9 = ( 502432641 ) 10 Hash(80127429)=(80127429)_{13}=8*13^7+0*13^6+1*13^5+2*13^4+7*13^3+4*13^2+2*13^1+9=(502432641)_{10} Hash(80127429)=(80127429)13=8137+0136+1135+2134+7133+4132+2131+9=(502432641)10

    如果取中间六位作为哈希值,得Hash(80127429)= 024326

    提示:

    • 为了获得良好的哈希函数,可以将几种方法联合起来使用,比如先变基,再折叠或平方取中等等,只要散列均匀,就可以随意拼凑。

    2.3.9 字符串数值哈希法

    在很都情况下关键字是字符串,因此这样对字符串设计Hash函数是一个需要讨论的问题。

    这个函数称为 ELF Hash(Exextable and Linking Format ,ELF,可执行链接格式) 函数。它把一个字符串的绝对长度作为输入,并通过一种方式把字符的十进制值结合起来,对长字符串和短字符串都有效,这种方式产生的位置均匀分布。

    #include <stdio.h>
    
    unsigned int ELFHash(char* str) {
        unsigned int hash = 0;
        unsigned int high = 0;
        while (*str) {
            hash = (hash << 4) + (*str++); // hash左移4位,把当前字符ASCII存入hash低四位。
            high = hash & 0xf0000000L;
            if (high) {
                // 如果最高的四位不为0,则说明字符多余7个,现在正在存第7个字符,如果不处理,再加下一个字符时,第一个字符会被移出,因此要有如下处理。
                // 该处理,如果最高位为0,就会仅仅影响5-8位,否则会影响5-31位,因为C语言使用的算数移位
                // 因为1-4位刚刚存储了新加入到字符,所以不能>>28
                hash ^= (high >> 24);
                // 上面这行代码并不会对X有影响,本身X和hash的高4位相同,下面这行代码&~即对28-31(高4位)位清零。
                hash &= ~high;
            }
        }
        // 返回一个符号位为 0 的数,即丢弃最高位,以免函数外产生影响。(我们可以考虑,如果只有字符,符号位不可能为负)
        return (hash & 0x7FFFFFFF);
    }
    
    int main(int argc, char* argv[]) {
        char*        key = (char*)"abcdefg";
        unsigned int ret = ELFHash(key);
        printf("%d\n", ret);
        return 0;
    }
    

    2.4 处理冲突(HASH 碰撞)

    前面介绍:散列函数的输入和输出不是唯一对应关系的,如果两个散列值相同,两个输入值很可能是相同的,但也可能不同。这通常是两个不同长度的输入值,计算出相同的输出值。

    (1)聚集/堆积(Cluster)

    在函数地址的表中,散列函数的结果不均匀地占据表的单元,形成区块,造成线性探测产生一次聚集(primary clustering)和平方探测的二次聚集(secondary clustering),散列到区块中的任何关键字需要查找多次试选单元才能插入表中,解决冲突,造成时间浪费。对于开放定址法,聚集会造成性能的灾难性损失,是必须避免的。

    (2)负载因子(load factor)
    load factor = n k {\displaystyle{\text{load factor}}={\frac{n}{k}}} load factor=kn

    • n 是哈希表中占用的条目数。
    • k 是存储桶数

    随着负载因子的增大,哈希表变慢,甚至可能无法工作(取决于所使用的方法)。哈希表的预期恒定时间属性假定负载因子保持在某个界限以下。对于固定数量的存储桶,查找时间随条目数量而增加,因此无法实现所需的恒定时间。在某些实现中,解决方案是在达到负载因子限制时自动增大(通常为两倍)表的大小,从而强制重新散列所有条目。作为一个实际示例,Java 10中HashMap的默认加载因子为0.75。

    2.4.1 开放定址法

    open addressing:在另一种称为开放式寻址的策略中,所有条目记录都存储在存储桶数组本身中。当必须插入新条目时,将检查存储桶,从哈希到的插槽开始,并按某些探测顺序进行操作,直到找到未占用的插槽。搜索条目时,将按相同顺序扫描存储桶,直到找到目标记录或找到未使用的阵列插槽为止。

    “开放地址”是指以下事实:项目的位置(“地址”)不是由其哈希值确定的。(此方法也称为 封闭式哈希;请勿将其与“开放式哈希”或“封闭式寻址”混淆

    (1)通用函数

    这种方法有一个通用的再散列函数形式:
    H i = ( H ( k e y ) + d i ) % m i = 1 , 2 , ⋅ ⋅ ⋅ , m H_{i} = (H(key) + d_{i}) \% m \qquad i = 1, 2, ···, m Hi=(H(key)+di)%mi=1,2,,m
    其中 H ( k e y ) H(key) H(key)哈希函数 m m m表长 d i d_{i} di 称为增量序列。

    (2)分类

    增量序列的取值方式不同,相应的再散列方式也不同。

    1. 线性探测(Linear Probing)
      两次探测之间的间隔是固定的,通常设置为1。
    2. 平方探测(Quadratic Probing)
      二次探测:其中探针之间的间隔呈二次方增加(因此,索引由二次函数描述)。
    3. 双重哈希(伪随机探测)
      其中每个记录的探测间隔(是固定的?)由另一个哈希函数计算得出。

    这些方法之间线性探测具有最佳的缓存性能对聚类最敏感,而双重哈希的缓存性能较差,但实际上没有聚类。二次探测介于两个区域之间。与其他形式的探测相比,双散列还可能需要更多的计算。

    举例:

    关键字为 {89,18,49,58,69} 插入到一个散列表中的情况。并假定取关键字除以10的余数为散列函数法则(m = 10)。

    显示线性探测填装一个散列表的过程,此时线性探测的方法是取 d i = 1 d_{i} = 1 di=1

    散列地址0123456789结果
    空表
    插入89899未占用,89插入9
    插入1818898未占用,18插入8
    插入494918899被占用,49后移一位,0未占用,49插入0
    插入58495818898被占用,58后移,直到1未占用,58插入1
    插入6949586918899被占用,69后移,直到2未占用,69插入2

    表的大小选取至关重要,此处选取10作为大小,发生冲突的几率就比选择质数11作为大小的可能性大。越是质数,mod取余就越可能均匀分布在表的各处。

    显示平方探测填装一个散列表的过程,此时线性探测的方法是取 d i = ( x % 10 ) 2 d_{i} = (x\%10)^{2} di=(x%10)2

    散列地址0123456789结果
    空表
    插入89899未占用,89插入9
    插入1818898未占用,18插入8
    插入494918899被占用, 1 2 = 1 1^2=1 12=1,0未占用,49插入0
    插入58495818898被占用, 1 2 = 1 1^2=1 12=1 2 2 = 4 2^2=4 22=4,3未占用,58插入3
    插入6949586918899被占用, 1 2 = 1 1^2=1 12=1 2 2 = 4 2^2=4 22=4,4未占用,69插入4

    显示双重探测填装一个散列表的过程,此时线性探测的方法是取随机 d i = r a n d _ r ( i ) % 10 m = 10 d_{i} = rand\_r(i)\%10 \quad m =10 di=rand_r(i)%10m=10 。(未验证)

    散列地址0123456789结果
    空表
    插入89899未占用,89插入9
    插入1818898未占用,18插入8
    插入494918899被占用,49随机,0未占用,49插入0
    插入5849581889随机
    插入694958691889随机
    #include <stdio.h>
    #include <stdlib.h>
    
    void displayA(int* array, int size) {
        for (int i = 0; i < size; i++) {
            printf("%3d|", array[i]);
        }
        printf("\n");
    }
    
    /***************************************************************************
     * @date    2020/12/05
     * @brief   选择插入位置,d = 1
     * @param   Hash1   散列地址空间
     * @param   size    散列地址大小
     * @param   key     关键字
     * @return  插入位置
     ***************************************************************************/
    int open1(int* Hash1, int size, int key) {
        int temp  = key % size;
        int count = size;
        while (count--) {
            if (Hash1[temp] == 0) {
                return temp;
            } else {
                temp = (temp + 1) % size;
            }
        }
        printf("散列地址已满!");
        exit(-1);
    }
    
    int main(int argc, char* argv[]) {
        int key[]     = {89, 18, 49, 58, 69, 45, 55, 78, 93, 61, 28};
        int key_size  = sizeof(key) / sizeof(key[0]);
        int Hash1[10] = {0};
        printf("  0|  1|  2|  3|  4|  5|  6|  7|  8|  9|\n");
        printf("----------------------------------------\n");
        for (int i = 0; i < key_size; i++) {
            Hash1[open1(Hash1, 10, key[i])] = key[i];
            displayA(Hash1, 10);
        }
        return 0;
    }
    

    2.4.2 链地址法

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

    • 链接列表分开链接

    在这里插入图片描述

    • 列表头单元格分开链接

    一些链接实现将每个链的第一条记录存储在插槽阵列本身中。在大多数情况下,指针遍历的数量减少一。目的是提高哈希表访问的缓存效率。缺点是空桶与一个入口的桶占用相同的空间。为了节省空间,此类哈希表通常具有与存储的条目一样多的插槽,这意味着许多插槽具有两个或多个条目。

    在这里插入图片描述

    • 其他数据结构链接

    除了列表以外,还可以使用支持所需操作的任何其他数据结构。

    举例:已知一组关键字(32,40,36,53,16,46,71,27,42,24,49,64),哈希表长度为13,哈希函数为:H(key)= key % 13

    在这里插入图片描述

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct list_node {
        int               data;
        struct list_node* next;
    } LN;
    
    void display(LN* HashMap, int mod) {
        for (int i = 0; i < mod; i++) {
            printf("%2d: ", i);
            LN* p = (HashMap + i)->next;
            while (p) {
                printf("%d ", p->data);
                p = p->next;
            }
            printf("\n");
        }
    }
    
    /***************************************************************************
     * @date    2020/12/05
     * @brief   插入对应链表,然后顺序插入
     * @param   list    链表头
     * @param   key     关键字
     * @param   mod     Hash 表长度
     ***************************************************************************/
    void insert(LN* list, int key, int mod) {
        int value  = key % mod;
        LN* temp   = (list + value);
        LN* node   = (LN*)malloc(sizeof(LN));
        node->data = key;
        node->next = NULL;
        if (temp != NULL) {
            while (temp->next && temp->next->data < key) {
                temp = temp->next;
            }
        }
        // 头插法
        node->next = temp->next;
        temp->next = node;
    }
    
    /***************************************************************************
     * @date    2020/12/05
     * @brief   删除 Hash 值(查找同理)
     * @param   list    链表头
     * @param   key     关键字
     * @param   mod     Hash 表长度
     * @return  0/1     完成信息 0-成功
     ***************************************************************************/
    int erase(LN* list, int key, int mod) {
        int value = key % mod;
        LN* prev  = (list + value);
        LN* temp  = prev->next;
        if (temp != NULL) {
            while (temp && temp->data < key) {
                prev = temp;
                temp = temp->next;
            }
            if (temp->data == key) {
                prev->next = temp->next;
                free(temp);
                return 0;
            }
        }
        return -1;
    }
    
    int search(LN* list, int key, int mod) {
        int value = key % mod;
        LN* temp  = (list + value)->next;
        if (temp != NULL) {
            while (temp && temp->data < key) {
                temp = temp->next;
            }
            if (temp->data == key) {
                return 0;
            }
            if (temp == NULL) {
                return -1;
            }
        }
        return -1;
    }
    
    int main(int argc, char* argv[]) {
        int key[]   = {32, 40, 36, 53, 16, 46, 71, 27, 42, 24, 49, 64};
        int size    = sizeof(key) / sizeof(key[0]);
        int mod     = 13;
        LN* HashMap = (LN*)malloc(sizeof(LN) * mod);
        for (int i = 0; i < mod; i++) {
            (*(HashMap + i)).next = NULL;
        }
    
        // 插入
        for (int i = 0; i < size; i++) {
            insert(HashMap, key[i], mod);
        }
        display(HashMap, mod);
        // 查找
        (search(HashMap, 40, mod) == 0) ? printf("\ttrue\n") : printf("\tfalse\n");
        // 删除
        erase(HashMap, 40, mod);
        display(HashMap, mod);
        // 查找
        (search(HashMap, 40, mod) == 0) ? printf("\ttrue\n") : printf("\tfalse\n");
    
        return 0;
    }
    

    2.4.3 多重哈希法

    • 再哈希法

    h a s h = H 2 ( H 1 ( k e y ) ) hash = H2(H1(key)) hash=H2(H1(key))

    即在上次散列计算发生冲突时,利用该次冲突的散列函数地址产生新的散列函数地址,直到冲突不再发生。这种方法不易产生**“聚集”(Cluster)**,但增加了计算时间。(可以多重哈希算法计算,直到不冲突)。

    • 2-选择散列

    2-选择哈希对哈希表:采用两个不同的哈希函数 h 1 ( k e y ) h1(key) h1(key) h 2 ( k e y ) h2(key) h2(key) 。这两个哈希函数都用于计算两个表位置。将对象插入表中后,会将其放置在包含较少对象的表位置(如果存储桶大小相等,则默认为表 h 1 ( k e y ) h1(key) h1(key) 位置)。2-选择散列采用两种选择的幂的原理。

    2.4.4 建立公共溢出区

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

    3. 使用及分析

    3.1 应用

    (1)数据库索引

    哈希表也可用作基于磁盘的数据结构和数据库索引(例如dbm),尽管B树在这些应用程序中更为流行。在多节点数据库系统中,哈希表通常用于在节点之间分配行,从而减少了哈希联接的网络流量。

    (2)高速缓存

    哈希表可用于实现高速缓存,辅助数据表,这些数据表用于加快对主要存储在较慢媒体中的数据的访问。在此应用程序中,可以通过丢弃两个冲突条目之一来处理哈希冲突-通常擦除当前存储在表中的旧项目,然后用新项目覆盖它,因此表中的每个项目都具有唯一的哈希值。

    (3)密码学

    3.2 优缺点

    (1)优势

    • 哈希表相对于其他表数据结构的主要优点是速度。当条目数量很大时,此优势更加明显。当可以预先预测最大条目数时,哈希表特别有效,因此可以以最佳大小分配存储桶数组一次,而从不调整大小。
    • 如果一组键值对是固定的,并且提前知道(因此不允许插入和删除),则可以通过仔细选择哈希函数,存储区表大小和内部数据结构来降低平均查找成本。特别地,人们可能能够设计出一种无冲突甚至完美的哈希函数。在这种情况下,密钥不必存储在表中。

    (2)劣势

    • 尽管对哈希表的操作平均需要花费恒定的时间,但良好的哈希函数的成本可能比顺序列表或搜索树的查找算法的内循环高得多。因此,当条目数很少时,哈希表无效。如果没有太多可能要存储的键(也就是说,如果每个键可以用足够小的位数表示),则可以使用该键直接作为数组的索引,而不使用哈希表价值。请注意,在这种情况下不会发生冲突。
    • 如果哈希表使用动态调整大小,则插入或删除操作可能会偶尔花费与条目数量成比例的时间。在实时或交互式应用程序中,这可能是一个严重的缺点。
    • 通常,哈希表的引用局部性很差-也就是说,要访问的数据似乎在内存中随机分布。因为哈希表会导致访问模式跳来跳去,所以这会触发微处理器高速缓存未命中,从而导致长时间的延迟。如果表相对较小并且键很紧凑,则紧凑的数据结构(例如使用线性搜索搜索的数组)可能会更快。最佳性能点因系统而异。
    • 当发生许多冲突时,哈希表的效率变得非常低下。虽然极不可能偶然出现非常不均匀的哈希分布,但是具有哈希功能知识的恶意攻击者可能会向哈希提供信息,从而通过引起过多的冲突而导致最坏情况的行为,从而导致性能非常差。

    4. 总结

    4.1 复杂度

    平均最坏的情况下
    space O ( n ) O(n) O(n) O ( n ) O(n) O(n)
    search O ( 1 ) O(1) O(1) O ( n ) O(n) O(n)
    insert O ( 1 ) O(1) O(1) O ( n ) O(n) O(n)
    delete O ( 1 ) O(1) O(1) O ( n ) O(n) O(n)

    4.2 理解

    Hash算法也被称为散列算法,Hash算法虽然被称为算法,但实际上它更像是一种思想。Hash算法没有一个固定的公式,只要符合散列思想的算法都可以被称为是Hash算法。

    参考

    [1] 什么是 hash?

    [2] hash算法原理详解

    [3] 数据结构—— 构造散列函数的六种方法

    [4] 程序员必备:字符串哈希函数比较

    [5] 散列函数

    展开全文
  • 比如我们下载一个文件文件的下载过程中会经过很多网络服务器、路由器的中转,如何保证这个文件下载过程中没有丢包,被完整的下载下来了呢?我们不可能去检测这个文件的每个字节,也不能简单地利用文件名、文件大小...
  • 单向散列加密

    2019-10-02 01:17:44
    或者验证文件唯一性等。这时就要用到单向散列加密。  单向散列函数特点  1. 对任意长度的消息散列值是定长的。  2. 散列计算速度快,非常高效。  3. 明文不同,散列加密后的密文一定不同;明文相同,散列...
  • 计算机中所有东西都可以看作是文件,那么计算机系统是必须有文件管理功能的,这也是操作系统中最为重要的功能子系统,本文介绍文件管理的基础知识。
  • 散列

    2017-08-30 20:28:00
    数组的每个位置存储一条信息,并且与一个唯一的关键字有确定的映射关系f,f被称为散列函数。这样在已知关键字k和散列函数f时,就能 唯一确定存储的信息。理想情况下,存储信息的位置是无限的,关键字的个数也是无限...
  • JAVA如何把HashMap内容输出到文本文件

    千次阅读 2021-03-09 01:01:02
    IO按照处置数据的类型分歧分为字符和字节省,按照数据的标的目的分歧可以分为输入和输出。IO的分类可以参考下图,我们将在接下来利用这里面的类。2接下来我们建立一个TxtUtil东西类,来实现写入文本文件...
  • 这两种方法的不同之处在于:开散列法把发生冲突的关键码存储在散列表主表之外,而闭散列法把发生冲突的关键码存储在表中另一个槽内。 下面介绍业内比较流行的hash冲突解决策略: 线性探测(Linear probing) 双重哈希...
  • 【0】README0.1) 本文描述转自 core java volume 2, 旨在理解 java文件——对象和序列化 的相关知识; 【1】对象和序列化1.1)problem + solution 1.1.1)problem: 当你需要存储相同类型的数据时, 使用...
  • 操作系统实验四:文件系统

    千次阅读 2020-06-20 19:15:41
    2、模拟实现Linux文件系统的简单I/O操作:备份文件。 二、实验环境 Linux系统 三、实验内容 1、浏览Linux系统根目录下的子目录,熟悉每个目录的文件和功能; 2、设计程序模拟实现Linux文件系统的简单I/O操作:...
  • 文件的概念 概念:文件是具有符号名的,在...文件系统:是操作系统中负责存取和管理信息的模块,它用统一的方式管理用户和系统信息的存储、检索、更新、共享和保护,并为用户提供一整套方便有效的文件使用和操作方法
  • 这两种方法的不同之处在于:开散列法把发生冲突的关键码存储在散列表主表之外,而闭散列法把发生冲突的关键码存储在表中另一个槽内。 下面介绍业内比较流行的hash冲突解决策略: 线性探测(Linear probing) 双重哈希...
  • Hash,一般翻译做"散列",也有直接音译为"哈希"的,就是把任意长度的输入(又叫做预映射,pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常...
  • 对基本信息单位操作不多的文件较适于采用字符的无结构方式,例如,源程序文件、目标代码文件等。 记录式的有结构文件 记录式的有结构文件文件中的基本信息(记录)按不同方式排列构成不同的逻辑结构,方便...
  • 操作系统--文件系统

    千次阅读 2015-05-19 10:46:15
    物理文件可以是在存储设备上的存储区域,也可以使一个设备、管道、套接字,文件系统将用户对文件的操作转换成用户对设备的操作、用户间的通信操作和网络操作。 1逻辑文件文件系统中,用户所面对的文件是逻辑文件...
  • 当前的大数据处理系统无论是何种架构都面临一个共同的问题,即:“计算是原生的计算,而存储却不是原生的流存储” 。Pravega 团队重新思考了这一基本的数据处理和存储规则,为这一场景重新设计了一种新的存储类型...
  • B树适合在磁盘等直接存储设备上组织动态查找表,文件的组织方式便是B树或B+树。他在查询和动态操作方面效率很高。但是hash表的效率更高,可是hash表第一存在散列冲突问题,这个必须解决;第二hash表的一般利用率仅为...
  • 原因如下:(1)数据的持久化文件HFile中是按照KeyValue存储的,如果Rowkey过长比如100个字节,1000万列数据光Rowkey就要占用100 * 1000万=10亿个字节,将近1G数据,这会极大影响HFile的存储效率 (2)MemStore将...
  • Unix系统的用户密码就是MD5散列运算储存文件系统,当用户登录时,系统就要把用户输入的密码进行MD5散列运算,在和储存文件系统里MD5值进行比较,进而确定密码是否正确。这样的好处时文件系统没有直接明文存储...
  • 逆向算法--散列之MD5

    2018-09-16 11:24:01
    MD5是一种生成32位hex格式字串的单项散列函数,不可恢复,一般用于校验文件完整性防止被篡改,有时会被用于避免明文出现,也经常被用于软件保护方面 MD5以512位(32字节)分组处理输入消息,每一分组的处理过程中...
  • 散列函数

    2015-05-23 21:39:39
    在数据存储领域,主要是数据的索引和对容器的结构化支持,比如哈希表。 2.加密哈希 用于数据 /用户 核查和 验证。 一个 强大的 加密哈希 函数很难从结果再得到原始数据 。 加密 哈希函数 用于哈希 用户 ...
  • 操作系统之文件管理

    千次阅读 多人点赞 2020-09-22 03:05:15
    一、文件文件系统 1.1 文件是什么 文件是对磁盘的抽象 所谓文件是指一组带标识(标识即为文件名)的、在逻辑上有完整意义的信息项的序列。 信息项:构成文件内容的基本单位(单个字节,或多个字节),各信息项...
  • 哈希(散列,Hash)算法总结-java版

    千次阅读 2019-05-08 11:13:54
    哈希表是根据设定的哈希函数H(key)和处理冲突方法将一组关键字映射到一个有限的地址区间上,并以关键字在地址区间中的象作为记录在表中的存储位置,这种表称为哈希表或散列,所得存储位置称为哈希地址或散列地址...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 23,594
精华内容 9,437
关键字:

文件流是散列存储