SHA256
哈希是一种能将不同的输入映射为独一无二的定长字符串的算法,如果对于不同的输入,映射为同一字符串,则称之为哈希碰撞(collision)
.
对于哈希碰撞,我们可以记住这样一个公式
50%概率发生哈希碰撞的计算次数
N为哈希值的二进制位数,对于 SHA256 来说,它会生成32字节,64长度的16进制字符串,256位(每个字符取值范围为[0-9a-z])
对于生日来说可以计算出它50%概率发生碰撞所需要的计算次数为23.9
同时也要记住另一个公式
哈希碰撞概率公式
n为计算次数,d为取值空间,该公式推导过程中用到了泰勒公式
迪杰斯特拉算法
我们假设G
中的每个顶点V
都被赋予了一个标记L(V)
,它要么是一个数,要么是∞
。假设P
是G
的顶点的集合,P
包含S
,满足:
1)如果
V属于P
,则L(V)是从S到V的最短通路的长度,并且存在这样的从S到V的最短通路:通路上的顶点都在P中2)如果
V不属于P
,则L(V)是从S到V的满足下面限制的最短通路的长度:V是通路中唯一一个不属于P的顶点。
先找出不在P
中且带有最小标记的顶点U
,标记为L(U)
, 可以证明从S
到U
的最短通路中除U
外不包含不属于P
的元素。
因为若存在除U
外其他顶点,先假如果最短通路U前最后一个点为Q
且不属于P
,则最短通路为SP1P2...PnQU(P1,P2..Pn属于P,Q不属于P)
,则由性质2)最短通路长度为L(Q)+PATH(Q,U)>L(U)
从而大于SP1P2..PnU的通路长度L(U),不是最短通路,所以从S到U的最短通路中除U外不包含不属于P的元素,从而从S到U的最短通路长度由L(U)给出.
以上证明了最短路终点的前一个顶点一定属于P