哈希原理(笔记)

1. 哈希

        一般情况下很少将Hash这个词单独拿出来用，我们常用的其实是Hash function(又称 哈希函数、散列函数、散列算法)。Hash function通常是保密的。

哈希过程的理解：
        Hash function的计算过程可以理解为我们常说的加密或者说伪装。(本图来源:wiki)

例一(以数学中的函数运算为例)：

例二(以简单的密码学为例 – 最简单的密码学就是散列函数)：
" 明文->密钥(Hash function) ->密文(散列值 或称为哈希值)"
例三(以实际生活为例)：
        大学生可以享受海底捞六九折优惠。其他人要是也想用六九折，可以让大学生先帮忙付款，然后自己再把钱转给人家。这种情况下，请大学生帮忙付款这个伪装成大学生的过程也可以称为Hash function。

        综上所述，不同的场景下，伪装方式也不尽相同。因此对于我们初学者而言，怎么伪装的其实不太重要，重要的是我们需要知道有伪装这个操作。

数据结构Hash map(Hash Table)

(再次强调：数据结构是一种解决问题的思想。)
实际应用：哈希表强调数据之间的映射关系。如下所述，云盘秒传、文件完整性检验、手机通讯录等。
内存中的存储过程：
        内存地址都是16进制的，在这里我们假设1、2、3等数字是内存地址编号。

        尤其应该注意Hash function的设计，它是一个难点，Hash funtion设计好坏直接关乎哈希表查询速度的快慢。可以通过翻看源码，学习不同语言哈希表中Hash function的设计。

                                                (本图来源：wiki)

复杂度分析

                                                (本图来源：wiki)
        我们只需要经过计算拿到key对应value的地址，就可以进行查找、增加、删除操作，因此平均时间复杂度为O(1)。考虑到哈希碰撞(涉及到对链表的操作)，所以最坏的时间复杂度都是O(n)。
        多次出现哈希碰撞会严重影响哈希表的效率，由此证明当前Hash function的设计有问题。
        为了降低哈希碰撞出现的可能性，很多企业再设计Hash function时会夹杂时间戳，例如：网购的订单编号。
Hash 表的时间复杂度为什么是 O(1)(面试版)

散列值碰撞(哈希碰撞)

        不同的输入数据(key)经过相同的Hash function伪装之后得到了相同的输出（索引值或者哈希值）。相同的索引值：不同的键经过哈希函数计算后映射到了哈希表中的同一个位置，这可能会导致冲突，需要解决冲突的方法比如链表或者开放寻址法。相同的哈希值：不同的键计算得到相同的哈希值，但是在哈希表中可以通过额外的信息（比如链表节点或者其他方法）区分存储不同的键值对。
        哈希碰撞是在实现哈希映射时需要考虑和处理的问题之一
例一：

例二：
        手机通讯录：不同的备注(key)对应详情信息里的手机号相同。
一些高级语言中的解决方案：
这只是其中一种解决方案：弄一个链表

                                                (本图来源：wiki)

2. 单向散列函数

        上述加密方法Hash function(简称为f(1) )是保密的，因此我们只能通过验证方法(简称为f(2) )计算查询哈希碰撞确认某个哈希值的存在，但是无法通过 f(2)逆推出明文(因为 f(2)只是验证方法，而非解密方法)。例子：sha验证。
        单向散列函数是哈希值的一个实际应用，我们常见的加密算法(例如：md5。早期的md5被破解也是因为人们搞清楚了它的加密方法 f(1) )大多利用单向散列函数函数。
相关文章

补充①：文件完整性校验过程(sha验证)

原理：

操作步骤：
① 进入tomcat官网

② 右击所安装软件包后面对应的sha512文件，查看该文件的散列值

③ powershell中查看自己所下载安装包的散列值
Windows:
打开 PowerShell，然后使用以下命令：
SHA-256: Get-FileHash <文件路径> -Algorithm SHA256
SHA-512: Get-FileHash <文件路径> -Algorithm SHA512
MD5: Get-FileHash <文件路径> -Algorithm MD5
macOS 和 Linux:
SHA-256: shasum -a 256 <文件路径>
SHA-512: shasum -a 512 <文件路径>
MD5: md5 <文件路径>
本次查看：

④ 将自己终端生成的散列值和官网给出的散列值比对。如果两者一致，说明文件下载完整且未被篡改。

补充②：pgp签名

        PGP 签名（Pretty Good Privacy）是为了验证文件的来源和完整性。它通过公钥加密技术来确保文件确实是由特定的发布者生成，并且在传输过程中未被篡改。
        -----BEGIN PGP SIGNATURE----- 开头的内容是一个数字签名，通常用于验证文件是否被伪造或被篡改。这个签名是由文件的散列值通过发布者的私钥加密生成的。
        验证 PGP 签名通常需要使用发布者的公钥。你需要将这个签名和对应的公钥一起使用来验证文件的完整性。

与散列值的异同

        相同点：都与验证文件的完整性有关。
        不同点：散列值是通过散列函数（如 SHA-256）计算得到的固定长度字符串，它用于验证文件在传输过程中是否发生了变化。

3. 内容出处

直面数据结构