计算机程序的构造和解释 是这样的一本书：它将大量编程中的基本技巧，用一本正经的语言讲出来，帮助你在构建大型软件时使用这些技巧来控制代码中的复杂性。而这些技巧的共性之一就是，将复杂的事物，通过隐藏细节的方式进行组合和抽象。我认为如果一个合格的程序员只需要读三本书的话，这本书便位列其中。

写笔记是为了自己在读书的过程中能够更好地思考和理解，这份笔记的定位是排除书中的例子，将书中的结论和观点用自己的话重新描述一遍，以简体中文版为主，因为似乎翻译的质量不高，所以也会参考英文原版。本书的英文原版以 CC-BY-SA 发行，相信公开发布这份笔记没有版权方面的问题。其实这份笔记对没有读过本书的人没有什么意义，因为本书的重要价值在于书中的例子，而这份笔记不会涉及这些例子，所以请纯当我在自言自语。

1.2 过程与它们产生的计算

在程序设计中，能够对计算过程中各种动作的进行情况进行规划是十分重要的，只有看清楚各种不同种类的过程会产生怎样的计算过程，才能更好地反向构造出可靠的程序，使之能表现出所需的行为。

1.2.1 线性的递归和迭代

计算阶乘可能有多种方式，其中一种基于这样的认识「对于一个正整数 n, 它的阶乘就等于 n * (n - 1)!」。另一种方法则可以将阶乘描述为「维持一个用来表示乘积的 product, 然后从 1 开始递增计数器 counter, 并将 product 设置为 product * counter, 直到 counter 大于 n, product 就是 n 的阶乘」。

从结果来看，这两种计算方法并没有什么差异，但如果我们考虑这两种方式的「形状」，即计算过程中时间和空间等资源的消耗情况，就会发现他们有很大区别。

第一个计算过程，如果使用前文提到的代换模型进行展开，会呈现出一种先逐步展开，而后收缩的形状。在展开阶段，这一计算过程构造器了一个「推迟执行的操作」所形成的链条，具体就是乘法运算，收缩阶段表现为这些运算的实际执行。这种类型的计算过程被称为「递归计算过程」，在执行时，解释器必须维护好那些以后要执行的操作的轨迹，在计算 n! 时，推迟执行的乘法链条的长度随 n 呈线性增长，这样的计算过程被称为「线性递归过程」。

与之对应的，第二个计算过程里并没有任何增长或收缩。对于任何一个 n, 在计算过程中的每一步，解释器需要保存的状态只有变量 product, counter 和 n 的当前值。我们称这种过程为「迭代计算过程」。一般来说，迭代计算过程就是那种其状态可以用固定数目的「状态变量」描述的计算过程；而与此同时，又存在着一套固定的规则，描述了计算过程在从一个状态转换到下一个状态时，这些变量的更新方式；以及一个通常都会有的结束检测，它描述了这一计算过程应该终止的条件。在计算 n! 时，所需的计算步骤随 n 线性增长，这种过程被称为「线性迭代过程」。

我们还可以换一个角度来对比这两个过程。在迭代的例子中，在计算过程中的任何一点，有关计算状态的完整描述都被包含在了那三个状态变量中。如果我们令上述计算过程在某两个步骤中停下来，在重新恢复这个计算过程时，只需要为编译器提供这三个变量的值。

而对于递归的计算过程而言，存在着一些「隐藏」的信息，它们并未保存在变量中，而是由解释器维持着，以指明在所推迟的运算所形成的链条中，当前计算过程所处的状态。这个链条越长，需要保存的信息就越多。

在后文中我们将会讨论过程在计算机上的实现，那时将会看到，所有的迭代过程都可以「以硬件的方式」实现为一个机器，其中只需要固定数目的寄存器，无需任何辅助存储器。而要实现递归计算过程，就需要一种机器，其中使用到了一种被称为「堆栈」的辅助数据存储结构。

在对比「迭代过程」和「递归过程」时，我们必须当心，不要混淆了「递归计算过程」和「递归过程」的概念。当我们说一个过程是递归的时候，描述的是一个代码的语法形式上的事实，说明这个过程的定义中直接或简介地引用了该过程本身。

而当我们说某一计算过程具有某种例如线性递归的模式时，我们说的是这一计算过程所产生的计算方式，而不是代码书写上的形式。当我们说某个递归过程将产生一个迭代的计算过程时，可能会让人感到很奇怪；但这一过程可能确实是迭代的，因为它的状态可以通过固定数目的状态变量来完全刻画，解释器在执行这一计算过程时，只需要保持这三个变量的状态就够了。

区分计算过程和写出的代码可能令人看到困惑，其中的一个原因在于一部分常见的编程语言的实现中，在执行递归的过程时，所需要消耗的内存总是与过程调用的深度成正比，即使这个过程所描述的计算过程从原理上看上去是迭代的。作为这一设计的后果，要在这些语言中描述迭代过程，必须借助于特殊的「循环结构」，例如 for 和 while 等。

而在 Scheme 的实现中则没有这一缺陷，它总是能在常亮的内存消耗中执行迭代型的计算过程，即使这一计算过程是用一个递归过程描述的。具有这一特征的编程语言实现被称为「尾递归」的，有了支持尾递归的实现，我们就可以利用常规的过程调用机制来表述迭代，而不必借助专用的迭代结构。

1.2.2 树状递归

线性递归之外的另一种计算模式是「树状递归」，作为例子来考虑斐波那契数量的计算，除了前两位是 0 和 1 之外，其他的每个数都是前两个数之和。在 Lisp 中，我们可以简单地将 n 大于 1 的 fib(n) 表示为 fib(n - 1) + fib(n - 2).

当我们计算 fib(5) 的时候，我们需要计算 fib(4) 和 fib(3), 而为了计算 fib(4) 又需要计算 fib(2), 这一展开过程将会是树状的，在每一层会形成两个分支，直到其中一个是 fib(1) 或 fib(0).

这是一个典型的树状递归，但确实一种糟糕的计算斐波那契数列的方式，因为它进行了大量的冗余计算。该过程的计算步骤将会随着 n 呈指数增长，而空间需求则正比于 n, 因为在计算中的任何一点，只需要保存树中位于该节点之上的节点的轨迹。一般来说，树状递归中的计算步骤正比于树中的节点数，空间需求正比于树的最大深度。

如果用迭代方式重新实现 fib, 将会减少大量步骤，并减少一些空间需求，但并不是说树状递归是没有价值的。当在层次性的数据结构上进行操作时，树状递归是一种非常自然而威力强大的工具。而且它更加简单直接，如果将 fib 规划为迭代过程，则必须意识到，这一计算过程是通过三个状态变量来刻画的。

对待冗余计算的一种途径是通过重新安排，使计算过程能够自动构造出一个已经计算出的值的缓存，每次要求对某一参数调用过程时，先检查这个值是否在缓存中，如果存在就可以避免重复计算。

1.2.3 增长的阶

不同的计算过程在资源的消耗上存在着巨大的差别，衡量这种差别的一种方法就是用「增长阶」的记法。令 n 是有关问题规模的一个度量，例如如果是求一个数的平方根，n 就可以是所需的精度的位数。

而 R(n) 就是当问题规模为 n 时所需的资源的量。可能是所用到的寄存器的个数，也可能是需要执行的机器指令的个数，在每一时刻执行执行固定数目的操作的计算机里，所需的时间正比于需要执行的机器执行的条数。

如果存在常数 k1 和 k2, 使得 R(n) 总是在 k1 * f(n) 和 k2 * f(n) 之间，那我们就称 R(n) 具有 O(f(n)) 的增长阶。

举例来说，前文中计算阶乘的线性递归过程中，计算步骤的数目正比于 n, 也就是说具有 O(n) 的增长阶，其空间需求的增长阶也是 O(n). 而迭代版本的阶乘，步数具有 O(n) 的增长阶，而空间是 O(1), 即为一个常数。

增长阶是对计算过程的行为的一个粗略描述，如果一个三个计算过程分别需要 n^2, 1000 * n^2, 3 * n^2 * 10 * 10 + 17, 它们的增长阶都是 O(n^2).

增长阶为我们在问题规模改变时，预计一个计算过程的行为变化提供了有用的线索。对于一个增长阶为 O(n) 的计算过程，规模增大一倍将使它所用的资源也增加一倍。对于一个 O(n^2) 的计算过程，问题规模每增加一，都将导致所用资源按倍增长。而对于 O(log n) 的计算过程，问题规模每增加一倍，所需资源只增加一个常数。

1.2.4 求幂

考虑对一个给定的数计算幂乘，一个简单的做法是将其定义为一个递归过程 expt(x, n): x * expt(x, n - 1) 直到 n 为 0 时 expt(0) 为 1. 这个线性递归计算需要 O(n) 的计算步骤和 O(n) 的空间。

如果像阶乘一样将其转换为一个等价的迭代算法，则需要 O(n) 的计算步骤和 O(1) 的空间。

因为 x^a * x^b 等于 x ^ (a + b) 所以我们可以利用这个规则将 expt(x, n) 定义成当 n 是偶数时为 expt(x, (n / 2)) ^ 2, 奇数时为 x * expt(x, n - 1). 这个算法在时间上和空间上都有 O(log n) 的增长阶，在计算 x ^ 2n 时只比 x ^ n 多一次乘法。

随着 n 的变大，O(log n) 与 O(n^2) 之间的差距会越来越大。

1.2.5 最大公约数

1.2.6 实例：质数检测

费马检查与我们前面熟悉的算法都不一样，前面的算法都保证了结果一定正确，而费马检查得到的结果只有概率上的正确性。如果一个数不能够通过费马检查，我们可以确定它一定不是质数，但如果一个数通过了费马检查，我们只能认为它有很大的可能性是质数。如果执行这个检查的次数足够多，就可以将这一检查出错的概率减少到可以接受的程度。这类算法被称为「概率算法」。

计算机程序的构造和解释 是这样的一本书：它将大量编程中的基本技巧，用一本正经的语言讲出来，帮助你在构建大型软件时使用这些技巧来控制代码中的复杂性。而这些技巧的共性之一就是，将复杂的事物，通过隐藏细节的方式进行组合和抽象。我认为如果一个合格的程序员只需要读三本书的话，这本书便位列其中。

写笔记是为了自己在读书的过程中能够更好地思考和理解，这份笔记的定位是排除书中的例子，将书中的结论和观点用自己的话重新描述一遍，以简体中文版为主，因为似乎翻译的质量不高，所以也会参考英文原版。本书的英文原版以 CC-BY-SA 发行，相信公开发布这份笔记没有版权方面的问题。

其实这份笔记对没有读过本书的人没有什么意义，因为本书的重要价值在于书中的例子，而这份笔记不会涉及这些例子，所以请纯当我在自言自语。

计算机程序的构造和解释

一个计算机语言不仅仅是让计算机去执行操作的一种方式，更是一种表述有关方法学思想的新颖的形式化媒介。因此，程序必须写得能够供人们阅读，顺便供计算机执行。在这一层次，最基本的材料并不是特定的程序设计语言的语法，不是能够有效地计算某种功能的巧妙算法，也不是算法的数学分析或计算的本质基础，而是一些能够用于控制大型软件系统的智力复杂性的技术。

我们希望读者能够对程序设计的风格要素和审美观有一种很好的感觉；他们应该掌握控制大型系统中的复杂性的主要技术；他们应该能够去读 50 页长的代码，并知道在什么时候哪些东西不需要去读，不需要去理解；应该有把握地去修改一个程序，而保持原来的作者的精神和风格。

这些技能并不仅仅限于计算机程序设计，对于所有工程设计都是通用的。我们应当在适当的时候隐藏起一些细节，通过创建抽象去控制复杂性；通过建立起约定，以一种「混合与匹配」的方式组合起一些标准的，易于理解的片段，去控制复杂性；通过发明新的程序设计语言，每种语言强调设计中的一个特定方面并降低其他方面的重要性，来控制复杂性。

1 构造抽象过程

「计算过程」是存在于计算机中的一类抽象事物，这些过程会去操作一些被称为「数据」的抽象事物，人们创造出一种被称为「程序」的规则模式，来指导这类过程的进行。

设计良好的计算机系统就像设计良好的汽车或核反应堆一样，具有某种模块化的设计，其中的各个部分都可以独立地构造、替换、排除错误。

虽然 Lisp 并不是一种主流语言，但其具有一些特征使它成为研究程序的设计、构造，以及各种数据结构的一种最佳媒介。其中最重要的是：计算过程的 Lisp 描述本身又可以作为 Lisp 的数据来表示和操作；它的重要性在于，现存的许多威力强大的程序设计技术，都是在致力于填平「数据」和「过程」之间的传统划分。

1.1 程序设计的基本元素

任何一个强有力的语言都必须提供三种机制：

• 「基本的表达形式」表示最简单的个体
• 「组合的方法」将简单个体组合成复合对象
• 「抽象的方法」将复合对象作为一个整体单元来操作

1.1.1 表达式

1.1.2 命名和环境

在 Lisp 中，我们可以将值与符号关联，而后又能通过符号提取出这些值，这意味着解释器必须维护着某种储存能力，以保持有关的符号和值之间的映射，这种储存被称为「环境」。

1.1.3 组合式的求值

在 Lisp 中，对一个组合式的求值过程：先求值该组合式的各个子表达式；然后将最左子表达式的值所表示的过程，应用于其他子表达式所代表的参数。

我们可以用一棵树的形式来表示这一求值过程，其中每个组合式用一个带分支的节点表示，其分支对应于组合式中的运算符和运算对象，终端节点表示的是基本运算符和数值。

可以设想这些运算符和运算对象向上穿行，从终端节点开始，而后在越来越高的层次组合起来。

在性质上，这一求值过程是「递归」的，也就是说在这个计算过程中，包含着调用这个过程本身的步骤。我们应当将递归看做一种处理层次性结构的强有力的技术。

进一步的观察告诉我们，反复地应用第一个步骤，总可以将我们带到求值过程中的某一点，在这里遇到的不是组合式而是基本表达式，例如数值、内部运算符或者其他名字，处理这种基本情况的规则如下：

• 数的值就是它们所表示的数值
• 内部运算符的值就是能够完成相应操作的机器指令序列
• 其他名字的值就是在环境中关联于这个名字的那个对象

环境所扮演的角色就是用于确定表达式中各个符号的意义，如果没有关于环境的任何信息，例如 (+ x 1) 这样的表达式的值是毫无意义的，因为需要有环境来为符号 x 提供意义，甚至需要环境来为符号 + 提供意义。环境是一种具有普遍性的概念，它为求值过程的进行提供了一种上下文。

define 是目前我们看到的唯一的一种特殊形式，每个特殊形式都有其自己的求职规则。各种拥有不同的求值规则的表达式组成了程序设计语言的语法形式。Lisp 的语法非常简单，也就是说，可以被描述成一个通用规则和一组针对不多的特殊形式的专门规则。

1.1.4 复合过程

「过程定义」可以为复合操作关联一个名字，而后就可以将这样的操作作为一个单元来使用了。

过程定义的一般形式是：(define (<name> <formal parameters>) <body>)

其中 name 是一个符号，这个符号将在环境中和这个过程关联起来；formal parameters 即形式参数是一些名字，在过程体中用于表示应用过程时与它们位置对应的各个实际参数。body 是一组表达式，在应用这个过程中，body 中的形式参数将被与之对应的实际参数取代，对这样被替换后的表达式进行求值，产出这个过程应用的结果。

我们还可以用过程作为基本构件去定义其他过程，复合过程的使用方式与基本过程完全一样，事实上如果人们只看到过程的名字，根本就无法分辨出来它是像一个基本过程一样被定义在解释器中，还是一个复合过程。

1.1.5 过程应用的代换模型

对复合过程进行应用的过程被称为「代换模型」，在应用一个过程时，先将过程体中的形式参数替换为实际参数，然后像对组合式求值那样，对替换后的过程体进行求值。当然，这里描述的过程知识一个简单的庆幸，在真正的解释器中并不是这么做的。

对组合式的求值可以有两种方式：先将组合式完全展开再进行求值的模型被称为「正则序求值」，与之对应的，先求值参数再应用过程的模型被称为「应用序求值」。对于前面提到的可以通过替换来应用的过程，正则序和应用序求值的结果将会是一样的。

Lisp 采用应用序求值，部分原因在于这样可以避免对表达式的重复求值，更重要的是在超出了替换方式模拟的过程应用之后，正则序的处理将会变得非常复杂。

1.1.6 条件表达式和谓词

我们用术语「谓词」指那些返回真或假的过程，也指那种能求出真或假的值的表达式。

and 和 or 这些逻辑运算符用来构造复杂谓词。解释器将会对 and 或 or 的参数从左至右逐个求值，直到一个参数的值是真作为结果，跳过对右边其他表达式的求值。and 和 or 都是特殊形式而不是普通的过程，因为他们的子表达式不一定都会被求值，not 则是一个普通的过程。

1.1.7 实例：采用牛顿法求平方根

在数学中，人们通常关心的是说明性的知识(是什么), 而在计算机科学里，人们则通常关心行动性的描述(怎么做). 说明性描述和行动性描述有着内在的联系，例如，说一个程序产生的结果是「正确」的，就是给出了一个有关该程序性质的说明性描述。在编程中存在着大量的研究工作，其目标就是通过一些技术，来设法证明一个程序是正确的。其根源就是行动性描述(程序是由它们构筑起来的)和说明性描述(它们可以用来推导出某些结果)之间的差异。有一个在当前程序设计语言设计领域中很重要的问题，就是所谓的「终极语言」，在这种语言中编程就是写说明性的语句，通过将解释器做得足够复杂，程序员描述了需要做什么之后，解释器就能自动产生怎样做的知识。一般而言这是不可能做到的，但在这一领域人们已经取得了巨大的进步。

1.1.8 过程作为黑箱抽象

一个过程定义应该能隐藏一些细节，使过程的调用者不必考虑和了解这些细节，而是作为一个黑箱来接受它。

过程的调用者不需要关心的细节之一就是过程中形式参数的名字，过程的形式参数是局部于这个过程的，一个过程的定义约束了它的所有形式参数，这样的名字被称为「约束变量」。如果在一个完整的过程定义中将某个约束变量统一更名，这一过程的意义将不会有任何改变。一个名字的定义被约束于的那一集表达式被称为这个名字的作用域，在一个过程定义中，被声明为这个过程的形式参数的那些约束变量，就以这个过程的过程体作为它们的作用域。

如果一个变量不是被约束的，我们就称之为「自由」的。如果在一个过程的定义中，将一个自由的变量的名字加入参数列表就会引起一个错误，因为这样就将一个原本自由的名字变成了约束的，使其捕捉到了一个错误的值。

我们也可以将一个过程的定义局部于另一个过程，使这个过程成为其的子过程或者说是辅助过程。子过程还可以共享父级过程的约束变量，在父过程被调用的时候，约束变量被与实际参数关联起来，变成了子过程的自由变量，这种方式被称为「词法作用域」。

计算机程序的构造和解释 是这样的一本书：它将大量编程中的基本技巧，用一本正经的语言讲出来，帮助你在构建大型软件时使用这些技巧来控制代码中的复杂性。而这些技巧的共性之一就是，将复杂的事物，通过隐藏细节的方式进行组合和抽象。我认为如果一个合格的程序员只需要读三本书的话，这本书便位列其中。

大家都知道散列算法，如 MD5, SHA, 但是对其具体特性恐怕都很模糊。说不准哪些用法是可靠的，哪些用法是不可靠的，只是通过加 salt, 或者反复散列的方式提高可靠性。本文将精确地讨论它们在各种使用方法下的可靠性，本文不讨论原理，只讨论使用，以下部分资料来自网络，感谢 wxy 帮忙检验文中的论断。

MD5 和 SHA 系列算法都属于同一类——我还没给这类算法找到一个足够贴切的名字。首先在大的分类上，它们都是散列算法。
散列是怎么个定义呢？典型的散列算法可以是任何一个：具有无限的定义域，且具有有限的值域的函数。甚至，宽松的广义散列算法可以是任何一个(数学意义上的)函数，因为函数本身的概念就是将一个或多个值映射到一个唯一的值。

从具体特征上来说，它们(的目标)都是足够安全的信息摘要算法。究竟何谓安全？
MD5 和 SHA 系列函数所追求的安全，在于下面两个方面。

• 单向性
• 抗冲突性

所谓单向性，就是指明文 M, 经过散列后的 hash(M). 从 hash(M) 无法推算出 M. 这是大部分摘要算法都具有的特征，因为大多数情况下，被摘要的信息长度要大于散列值，因为缺少信息，且值域明显小于定义域，即一个散列值会对应多个(无限个)原文，所以天然地就无法从散列值反向计算出原文。MD5 和 SHA 系列函数在单向性方面目前都还没有被发现明显的漏洞。

但是以上讨论的只是理论上的单向性，实际使用中，攻击者可以通过穷举，即暴力破解的方式推算出可能的原文。这种情况适用于已知信息原文定义域且范围较小的情况。例如如果直接对用户的密码进行散列，因为密码大多在十位字母左右，攻击者可以以很低的成本计算所有密码组合的散列值，以得到可能的信息原文。

从散列算法的角度，应对暴力破解攻击没有明显有效的手段，但也可以通过『提高计算成本』和『减少散列值长度』的方式提升单向性。

提高计算成本即通过将算法设计得更为复杂，增加更多次计算，来提高对单个信息进行散列的时间。对于正常单次散列来讲，即使增加十倍的计算时间，仍然是可以接受的。但当攻击者进行暴力破解时，同样需要原来十倍的计算时间，这个成本对攻击者来说可能无法接受。除此之外，还可以改造算法，使其只能运行于 CPU 上，无法使用显卡或专用芯片进行计算，以提高暴力破解的计算成本。
但似乎这种方式并没有被业界接受，SHA 系列函数中的新成员均减少而不是提高了计算成本。

减少散列值长度，即通过减少散列值的长度来使得多个(大量)信息原文映射到同一个散列值，使攻击者无法分辨究竟哪个才是真正的原文。
例如将散列值减少到 8 bit, 这样密码组合中 1/256 的密码都会映射到同一个散列值，根本无法分别哪个才是真正的密码。
这种方式显然很扯淡，因为这种方式会明显降低下面要提到的抗冲突性。

实际使用中，我们可以通过提高定义域范围的方式，来增强单向性。同样是散列用户密码的例子，我们可以将原来的 hash(M) 改为 hash(hash(M)). 因为 hash 的值域范围通常要比密码(约 10 位字母，即约 60 bit)大, 如 MD5 的值域是 128 bit, SHA-1 的值域是 160 bit. 因此我们通过第一次散列将第二次散列的定义域提高到了 2-4 倍，一定程度上提高了攻击者暴力破解的成本。

但是，攻击者会将 hash(hash(x)) 视为一个独立的散列函数 hash2(x), 除了正常地增加了一倍的计算时间，并没有受到我们增加作用域的影响。因此，这时我们需要引入 salt(佐料，干扰), 将散列算法改为 hash(hash(x + salt)), salt 需要与散列值一同储存。

在已知 salt 的情况下，对攻击者其实没有任何影响，因为这个函数依旧可以转换为 hash2(x + salt), 当然，有些攻击者会通过 Rainbow Table(彩虹表) 的方式进行协作和缓存，加 salt 会使他们无法使用 Rainbow Table.

Rainbow Table, 即事先对预定范围的数据进行散列，储存散列结果。然后通过数据库或者分布式技术(小型 Rainbow Table 就不需要了), 来优化从散列值到原文的『反向』查询。相似的技术还有『字典』，即收集大家常用的原文(密码，或其他短语), 代替穷举，以提高暴力破解的效率。

而在这个场景中，将 hash(hash(x + salt)) 更换为 hash(hash(x) + salt) 会获得更好的效果。因为前一种情况，攻击者可以将密码和 salt 视为一个整体来使用 Rainbow Table (虽然在 Rainbow Table 中很可能查不到这些信息); 后者则不能。因为后者是一个散列值加一个 salt, 长度已经远远超出了 Rainbow Table 的范围。当然，单纯加长 salt 也可以实现 hash(hash(x) + salt) 的效果。

在攻击者不知道 salt 的情况下，有两种选择。
一是将 hash2(x) 改为 hash2(x, salt), 这种情况适用攻击者知道 salt 的长度或范围的情况，因为这个函数有两个参数，因此破解成本与 x 或 salt 的长度呈指数函数，只要 salt 足够长，那么可以认为攻击者即使暴力破解也无能为力。
二是将第二个 hash 的输入视为一个散列值，换言之就是进行两次爆破，这种方式的计算成本相比于前一种会更高，因为暴力破解的成本同原文长度也是呈指数关系的。

所以，在未知 salt 的情况下，可以防御所有暴力破解，除非攻击者拥有极其惊人的计算力。
举个例子，如果密码为 10 位的字母，salt 为 3 位的字母，暴力破解需要相当于 Bitcoin 全网计算力的约 60 天时间。

虽然我们还拥有更强大的变种，例如：

hash(x, salt[]) = hash(hash(x + salt[1]) + hash(x + salt[2]) + ...)

但是我们认为，使用 hash(hash(x) + salt) 和足够长的 salt(大致相当于散列值的长度), 已经足够安全。

接下来，那么如何生成 salt 呢？是否有必要为每条数据(还是前面的例子，每个用户)使用单独的 salt 呢。通过前面的讨论我们看到，要保证单向性，对 salt 进行保密十分必要。如果你能够保证 salt 的绝对安全的话，那么是否使用单独的 salt 其实无关紧要。不要担心使用相同的 salt 会让攻击者找到某种规律而计算出 salt(当然前提是 salt 足够长), 因为 MD5, SHA 系列函数保证了单向性，攻击者无法从散列值推测出原文的任何信息。

至于 salt 的取值，没有什么特别的要求，基于保密的考虑，通常要使用随机生成的字符串，然后就是足够长(大约等于散列值的长度).

但我们认为仍有必要为每条数据使用单独的 salt, 这是基于下面两点考虑。
一是虽然暴力破解需要惊人的计算力，但是如果只需破解一个散列值，就可以获知所有数据的 salt, 这个破解也是值得的，也许攻击者就能够提供这么多的计算力也说不定，虽然如果你使用足够长的 salt 的话，这种可能性极小。
二是也许你不能保证 salt 的绝对安全，当你的 salt 泄漏后，每条数据使用不同的 salt 将会为攻击者制造最后一道障碍。

如果你所有的数据都使用同样的 salt, 那么攻击者在拿到数据后，只需进行一次暴力破解，即可破解出所有的数据(如果都命中了的话), 但如果你为每条数据使用不同的 salt, 那么攻击者将不得不为每条数据单独运行一次暴力破解，因为每条数据相当于在使用不同的散列函数，因为 salt 是不同的。

综上，我们认为网站的用户系统使用下面的散列即可保证安全性：

hash(hash(passwd) + salt)

其中 salt 是随机生成的，长度等于散列值长度的字符串。hash 可以是 MD5 或 SHA 系列函数。

我们接着来谈抗冲突性，所谓抗冲突性即从计算上不可能找到两个有同样散列值的原文。抗冲突性分为抗强冲突性，和抗弱冲突性。
抗强冲突性，即给定一个散列值，无法找到另一个具有同样散列值的信息原文。
抗弱冲突性，即无法找到两个具有同样散列值的信息原文。

加上单向性，这三条特性是呈阶梯状的，满足『抗弱冲突性』就一定满足『抗强冲突性』也就一定满足『单向性』同时也就满足『散列映射具有随机性和均匀性』。MD5 和 SHA 系列函数在设计上都满足这三条特征，但目前已经被发现了存在某些漏洞。

抗冲突性的主要应用场景就是为信息原文进行摘要，鉴别两段信息原文是否相同。
而攻击者的目标就是，对信息原文进行修改，然后在信息原文后(或者修改信息原文)添加给定的数据段，使其能够生成与之前相同的散列值，实现伪造数据原文。

在这种场景下攻击者是否也能够进行暴力破解呢？很难，因为在这种情况下，攻击者需要不断更换附加在信息原文后的数据，以获得和之前相同的散列值，在不理想的情况下，需要尝试所有的散列值，这个计算力被认为是无法接受的。但通过算法的一些漏洞，可以降低这个暴力破解的成本。

抗冲突性是检验散列算法设计是否优秀的重要指标，很多散列算法被淘汰都是因为抗冲突性存在漏洞。

目前 MD5 已在 2005 年被中国数学家王小云发现有抗强冲突性的漏洞，给定一个散列值，可以在几分钟内用普通计算机找到一个碰撞，即具有相同散列值的信息原文。

SHA-0 被发现漏洞可以将寻找碰撞的难度从 2^80 次暴力破解降低到 2^39 次，SHA-1 被发现漏洞可以将寻找碰撞的难度从 2^80 次降低到 2^63 次，SHA-2 系列函数还未发现漏洞。

因此目前使用 MD5 进行信息摘要并不安全，攻击者可以轻易地伪造一段散列值相同，但内容不同的原文，虽然攻击者还不能够自由地修改原文。
而 SHA-1 和 SHA-2 系列函数目前来讲是足够安全的。