第三章 函数 函数是数学中的一个重要而基本的概念； 在集合和关系基础上引入函数； 第三章 函数 函数是数学中的一个重要而基本的概念； 在集合和关系基础上引入函数； 函数是一种特殊的关系， 函数建立了从 一个集合到另一个集合的特殊对应关系； 我们研究一般意义上的函数，研究其普 遍性性质；

函数概念的发展历史 早期函数概念——几何观念下的函数 十八世纪函数概念——代数观念下的函数 十九世纪函数概念——对应关系下的函数 绝大部分函数是被当作曲线来研究。 十八世纪函数概念——代数观念下的函数 欧拉给出的定义是：一个变量的函数是由这个变量和一些数即常数 以任何方式组成的解析表达式。 十九世纪函数概念——对应关系下的函数 1837年狄利克雷(Dirichlet，德，1805－1859) 指出：“对于在某区间 上的每一个确定的x值，y都有一个或多个确定的值，那么y叫做x的 函数”。

函数概念的发展历史 现代函数概念——集合论下的函数 广义函数 随着以数学为基础的其它学科的发展， 函数的概念还会继续扩展 1930年新的现代函数定义为，若对集合M的任意元素x，总有集合N确定的元素y与之对应，则称在集合M上定义一个函数，记为y=f(x)，元素x称为自变元，元素y称为因变元。 广义函数 20世纪40年代，物理学研究的需要发现了一种叫做Dirac－δ函数，它只在一点处不为零，而它在全直线上的积分却等于1，这在原来的函数和积分的定义下是不可思议的； 广义函数概念的引入，把函数、测度及以上所述的Dirac－δ函数等概念统一了起来。 随着以数学为基础的其它学科的发展， 函数的概念还会继续扩展

§3.1 函数的基本概念 定义3.1 一个函数或映射f: X  Y是一个满足下列两个条件的关系： 对每个x∈X，必存在y∈Y，使得 (x, y)∈f ； （存在性条件） 对每个x∈X，也只存在一个y∈Y，使得(x, y)∈f （唯一性条件） 另一种定义： 设有集合X与Y，如果有一种对应关系f，使X的任一元素x能与Y中的一个唯一的元素y相对应，则这个对应关系f叫从X到Y的函数或叫从X到Y的映射。

§3.1 函数的基本概念 说明： x所对应的Y内的元素叫做像，x叫做y的像源； 函数的表示方式：f:XY或y=f(x)或X 𝑓 Y； 一般地说，当|X|=n，|Y|=m （m,n<+∞） X到Y可定义mn个不同的函数。 f:XY的定义域D(f)用Df表示，值域C(f)用Cf表示， Df=X，Y⊇Cf 这里注意，定义域是X，而不能是X的真子集，因为X中每 个元素都有对应的函数值； 值域可以等于Y，也可以是Y的真子集，因为没有要求Y中 每个元素都有像源。 每一个X中元素都在Y中有m个选择

定义3.2 一个函数f:X→Y如果Cf=Y，则称为从X到Y的满射或者称为从X到Y的函数，否则称为X到Y内的函数。 定义3.3 一个函数f:X→Y，如果对任意的i、j，若xi ≠xj，有f(xi) ≠ f(xj) ，则此函数称为从X到Y的单射（或者称从X到Y的一对一的函数），否则称为多对一函数； 不同的自变量对应不同的函数值； 即不同的像源对应不同的像； 定义中的一对一的函数不是一一对应。

定义3.4 一个函数f:X→Y，如果它是从X到Y的一对一函数，则此函数称为一一对应映射，也称为双射。 即：单射 + 满射 = 一一对应映射/双射 说明： 1、若X=Y，则称上述函数为X的变换 2、单射|X|≤|Y|；满射|X|≥|Y|；双射|X|=|Y|

满射， 单射， 不是单射 不是满射 不是单射，不是满射 单射、满射，因此是双射 abcd abc 1 2 3 1234 abcd 1 2 3

3.2 复合函数、反函数、多元函数 定义3.5 设函数f:X→Y，g:Y→Z，它们所组成的复合函数或称复合映射g○f也是一个函数h:X→Z即： h= g○f :{(x,z)｜x∈X，z∈Z且至少存在一 个y∈Y，有y=f(x)，z=g(y)} f g X Y Z

定义3.6 设函数f:X→Y是一一对应函数，则f所构成 的逆关系称为f的逆映射成为f的反函数记作： f-1:Y→X 说明：关系都有逆关系，但函数不一定有反函数，因为要满 足存在性和唯一性条件。 例：设f:R→R，f={(x,x+1)|x∈R}，R是实数集 由于f是一一对应的， 因此存在反函数 f-1={(x+1,x)|x∈R}

说明： 与复合关系一样，复合函数定义了函数的复合运算，函 数的复合运算是满足结合律的，即： h◦(g◦f)= (h◦g)◦f = h◦g◦f； 在关系中，任何一个关系都存在逆关系。但由于函数是 一类特殊的关系，它必须满足唯一性的条件，因此不是 每个函数都存在反函数； 函数复合表示形式和关系复合相反，关系复合表示为f◦g， 函数复合表示为g◦f，目的是让f先运算，可以写成g(f(x))。

例1设f:X→Y是一个函数 X={x1,x2,x3} Y={y1,y2,y3,y4}， f={(x1,y2),(x2,y3),(x3,y1)}， 求f的逆关系 𝑓 ; 𝑓 ={(y1,x3),(y2,x1),(y2,x2)} 由于 𝑓 不满足附加条件（存在性，唯一性），因此不是一个函数，所以f没有反函数。 y2对应2个函数值x1,x2

例2设f:X→Y是一个函数， X={x1,x2,x3} Y={y1,y2,y3} f={(x1,y2),(x2,y3),(x3,y1)}, 𝑓 ={(y1,x3),(y2,x1),(y3,x2)} 𝑓 满足附加条件，因此g是f的反函数

一个函数存在反函数的条件：此函数是一一对应函数。 由上面的例子可得： 一个函数f:X→Y若存在反函数f-1 :Y→X，则必须满足： 对每个x∈X必有唯一的y∈Y与之对应，同时对每个y∈Y也必有唯一的x∈X与之对应，即表示此函数必须是一一对应。 不能没有，也不能有多个 双射 一个函数存在反函数的条件：此函数是一一对应函数。

函数的复合函数满足结合律 (f1○f2)○f3= f1○( f2○f3) 证明：∀a∈A (f1○f2)○f3(a)= (f1○f2)○ (f3(a))=f1(f2(f3(a))) f1○( f2○f3)(a)=f1○ (( f2○f3) (a))=f1(f2( f3(a)) 所以结合律得证

函数的复合运算不一定满足交换律 例如：f:R→R，g:R→R f(x)=x+1，g(x)=1+x2 ， (f◦g)(x)=f(g(x))=f(1+x2)=1+1+x2=x2+2 (g◦f)(x)=g(f(x))=g(1+x)=1+(1+x)2=x2+2+2x f◦g≠g◦f 另外，如果f:A→B，g:B→C，g◦f存在，而f◦g不存在。因为每个函数有自己的定义域

1.设A、B、C是集合， f:A→B，g f:B→C 若f和g都是单射函数，则g◦f也是单射函数； 一些结论： 1.设A、B、C是集合， f:A→B，g f:B→C 若f和g都是单射函数，则g◦f也是单射函数； 若f和g都是满射函数，则g◦f也是满射函数； 若f和g都是双射函数，则g◦f也是双射函数。 2.当逆函数都存在的情况下（前提条件） f:A→B当f-1存在，则f◦f-1=QA，f-1◦f=QB f:A→B当f-1存在( f-1) -1=f 设f:A→B，g:B→C，f和g的逆函数都存在， 则(f◦g) -1=g-1◦f-1 QA、QB为恒等函数

目前讨论的函数f:X→Y，因为只有一个变量，可以称为一元函数。如果有N个象源才能得对应的象，则称为N元函数 定义3.7 设有集合X1,X2,X3…Xn及Y，则 f:X1×X2×X3…Xn→Y 表示从n元有序组X1×X2×X3…×Xn到Y的一个函数； 当X=X1=X2=X3…=Xn=Y时，即为f:Xn→X，可称为n元运算； 当n=1时，叫一元运算，n>1时叫做多元运算。

鸽洞原理 一般描述：n个鸽洞，养了n+1只鸽子或者更多鸽子，则必 有一个鸽洞有2只或者更多的鸽子。 数学描述：A和B是集合，并且都是有限的集合，f是A到B 的函数，如果|A|>|B|，则A中至少有两个元素，其函数值 相等。（元素：鸽子；函数值：鸽洞） 推广：n个鸽洞，养了n×m只以上的鸽子，至少有一个洞 内住m+1或者更多的鸽子。 数学描述： A和B是有限集合，f是A到B的函数，如果 |A|>n×m，|B|=n，则A中至少有m+1个元素，其函数值相等。

例：任意取n+1个正整数，证明其中必有至少两个正整数，它们的差必被n除尽。 证明： 由于任意正整数被n除后，只能是0,1…n-1，其中有n种情况（即n个鸽洞） 所以在n+1个正整数（鸽子）中，必有两个数被n除后，其余数相同，那么这两个数的差也必能被n除尽。

例：在平面上有6个点，其任意两个点都用一条边相连，所构成的图称为完全图。现在给每条线涂色，可随意涂上红色和黑色。 证明：在任意涂色后，图中必存在一个涂色边颜色相同的三角形。

证明：设平面上有六个点，v1,v2,v3…v6，为便于叙述，先画与v1相连的5条边。 由于和v1相连的有五条边，根据鸽洞原理，其中必有三条边或者更多条边，有相同的颜色，假设（v1,v3）、（v1,v4）、（v1,v6）为红色。

现考虑（v3,v4），会出现两种情况： 1. 如果（v3,v4）为红色，则三角形v3、v4、v5构成全为红色边的三角形；

2.如果（v3,v4）为黑色，则考虑（v4,v6）也会有两 种情况： a.如果（v4,v6）为红色，则v1、v4、v6为同色三角形； b.如果（v4,v6）为黑色。

如果（v4,v6）为黑色，则考虑（v3,v6） (i)如果（v3,v6）为红色，v1, v3,v6为同色三角形（红色） (ii)如果（v3,v6）为黑色，v4, v3,v6为同色三角形（黑色）

3.3 常用函数介绍 定义3.8 设有函数f:A→B，若存在一个b∈B，使得对任何a∈A都有f(a)=b，则称f为A到B的常值函数或者是常数函数。 所有的自变量的函数的值都是一个常数； 多对一函数。 定义3.9 设有函数f:A→A，若对任何a∈A，都有f(a)=a，则称f:A→A为恒等函数。 双射

定义3.11 设有函数f:A→B，其中B={0,1}对A的子集A’，总存在下面的关系： 定义3.10 设有函数f:R→R，其中R为实数集合，若对于任意的a、b∈R，如有a<b，必有f(a)≤f(b)，则称函数f为单调递增；若任意a、b∈R，如有a<b，必有f(a)<f(b)，则称为函数f为严格单调递增。类似的方法可以定义单调递减和严格单调递减。 定义3.11 设有函数f:A→B，其中B={0,1}对A的子集A’，总存在下面的关系： 则称函数f为集合A’ 的指示函数或特征函数。 特征函数表示集合与某一特性间的联系。

例： Dirichlet函数： 无法画出图像； 以任何正有理数为其周期（从而无最小正周期）； 处处无极限、不连续、不可导； 在任何区间上不黎曼可积； 是偶函数； 在[0,1]上勒贝格可积。

例：国际标准书号 ISBN ISBN是由“-”号隔开 10个字符组成的编码 ISBN由四部分组成： 组号-出版社号-出版社中该书的唯一代码-检验码 如：0-8065-0959-7 0表示英语国家，8065表示Citadel出版社 检验码是 S mod 11 S=第一位+第二位×2+…+第9位×9 如果S mod 11计算出来是10，则校验码是X 注：身份证号码的校验位（第18位）与此类似。

假设某国际标准书号号码前9位是：7-309-04547；计算加权和S： S= 7×10+3×9+0×8+9×7+0×6+4×5+5×4+4×3+7×2 = 226； 计算S÷11的余数M：M = 226 mod 11 = 6； 计算11 - M 的差N：N = 11 − 6 = 5 如果N = 10，校验码是字母“X”； 如果N为其他数字，校验码是数字N。 所以，本书的校验码是5。 故该国际标准书号为 ISBN 7-309-04547-5。

散列函数（Hash function） Hash函数是一种计算方法，它可以把一个值A映射到一个特定的范围[begin, end]之内； 通过这些值就可以很快的找到与之对应的映射地址{index1, index2, … , indexN}； Hash函数中多个值可能会映射到相同地址，这样就会产生冲突。 如图中的红线所示； 在设计哈希函数时要尽量减少冲突的产生。 不用查表！

散列函数（Hash function） 设计算机的内存中有11个内存单元，下标为0到10，要在这些内存单元中对非负整数进行存储或者检索，可以用散列函数； 一个散列函数式根据要存储或者检索的数据进行计算其地址的首选值； 例如，要存储整数n，可以用n mod 11作为地址的首选值，其散列函数可以为： H(n)=n mod 11

存储方法： 现在要存入257，由于H(257)=257 mod 11=4，则257应该存入4，但是单元4已经被15占用，这种现象被称为碰撞。 即：对于一个散列函数H，如果有H(x)=H(y)，但x ≠ y，即称为碰撞。 解决碰撞的一个简单方法：用下一个未被使用的单元（单元0在单元10之后），则257应该存入6单元中。 1 2 3 4 5 6 7 8 9 10 132 102 15 257 558 32

1 2 3 4 5 6 7 8 9 10 132 102 15 257 558 32 检索方法 如果要检索一个已存入的数n，要计算m= H(n)，并从地址m开始查找，如n不在该单元，则查找下一个地址单元，如遇到空单元或者回到开始位置，则n不存在。 总结 如果碰撞不发生，并且碰撞发生后可以快速解决，则散列函数计算存储和检索式一种很快的方法。 例：人事数据库中就常根据身份证号码散列来存储和检索。

Hash函数的理解： Hash函数是把一个大范围空间映射到一个小范围空间， 因此是多对一映射； 输入的实际值的个数必须比小范围更小，不然冲突就会很多； Hash函数的目的一般是为了节省空间，或者提高速度。 不同的应用对Hash函数有着不同的要求； 用于加密的Hash函数主要考虑它和单向函数的差距； 用于查找的Hash函数主要考虑它映射到小范围的冲突率。

Hash表： 哈希表是一种数据结构，它把KEY 和 VALUE用某种方 式对应起来。 使用hash()函数把一个KEY值映射到一个index上， 即hash(KEY) = index； 这样就可以把一个KEY值同某个index对应起来； 然后把与这个KEY值对应的VALUE存储到index所标 记的存储空间中。 每次想要查找KEY所对应的VALUE值时，只需要做一次 hash()运算就可以找到了。

分布式Hash表： 哈希表把所有的东西都存储 在一台机器上，当这台机器 坏掉了之后，所存储的东西 就全部消失了。 分布式哈希表可以把一整张 哈希表分成若干个不同的部 分，分别存储在不同的机器 上，这样就降低了数据全部 被损坏的风险。

分布式哈希表通常采用一致性哈希函数来对机器和数据进 行统一运算。 一致性哈希：是对机器（通常是其IP地址）和数据（通常是其KEY值）进行统一的运算，把他们全都映射到一个地址空间中。 假设有一个一致性哈希函数可以 把一个值映射到32bit的地址空间 中，从0一直到2^32 – 1，可以用 一个圆环来表示这个地址空间。

通过hash() 把这N台机器映射到环 的N个位置，划分整个地址空间使 每台机器控制一个范围的地址空间。 向这个系统中添加数据，使用 hash()函数计算其index，找出它 所对应的地址在环中属于哪个地址 范围，就可以把这个数据放到相应 的机器上。这样，也就是把一个哈 希表分布到了不同的机器上。 蓝色的圆点表示机器，红色的圆点表示某个数据经过hash()计算 后所得出的地址，虚线表示数据会存储在哪台机器上。 图中，按照逆时针方向，每个机器占据的地址范围为从本机器 开始一直到下一个机器为止。

一致性哈希(consistent hashing ) 有 N 个 cache 服务器，如何将一个object映射到 N 个 cache 上？ 思路：采用hash(object)%N的通用方法计算object的 hash 值，然后 均匀地映射到 N 个 cache。 问题： cache 服务器 m 出现故障，这样所有映射到cache服务器m 的对象 都会失效，需要把 cache m 从 cache 中移除，这时候 cache 就变 成了 N-1 台，映射需要相应修改：hash(object)%(N-1) ； 添加一台cache，这时候 cache 变成了 N+1 台，映射需要相应修改： hash(object)%(N+1) ； 还有一个问题： 想让后面添加的节点多做工作，显然上面的 hash 算法也做不到。有 什么方法可以实现呢，这就是一致性 hash 算法。 这意味着突然之间几乎所有的 cache 都失效了，洪水般的访问都会直接冲向后台服务器！

consistent hashing算法的原理 单调性：如果已经有一些内容通过哈希分派到了 相应的cache中，又有新的cache加入到系统中。 哈希的结果应能够保证原有已分配的内容可以被 映射到新的cache中去，而不会被映射到旧的 cache集合中的其它cache 。 简单 hash 算法 hash(object)%N 难以满足单调性 要求。 consistent hashing算法的原理 在移除 / 添加一个 cache 时，它能够尽可能小地 改变已存在 key 映射关系，尽可能地满足单调性 的要求。 就是将对象和 cache 都映射到同一个 hash 数值 空间中，并且使用相同的 hash 算法。

判定哈希算法好坏的另外三个指标： 1、平衡性(Balance)： 3、分散性(Spread)： 4、负载(Load)： Hash结果能够尽可能分布到所有的cache中去，这样可以使得所 有的cache空间都得到利用。 3、分散性(Spread)： 分布式环境中，终端可能只能看到一部分cache。当终端希望通 过Hash将内容映射到cache上时，由于不同终端所见的cache范 围有可能不同，从而导致Hash的结果不一致，最终的结果是相 同的内容被不同的终端映射到不同的cache中。 这种情况显然是应该避免的，因为它导致相同内容被存储到不同 cache中去，降低了系统存储的效率。 分散性的定义就是上述情况发生的严重程度。 4、负载(Load)： 负载问题实际上是从另一个角度看待分散性问题。对于一个特定 的cache而言，可能被不同的用户映射为不同的内容。

1、平衡性(Balance)解决方法： hash算法是不保证平衡的，如cache B发生故障； “虚拟节点”（ virtual node ） object1存储到了cache A中，而object2、object3、object4都存 储到了cache C中，这样就造成了非常不平衡的状态。 “虚拟节点”（ virtual node ） 是实际节点（机器）在 hash 空间的复制品（ replica ），一个 实际个节点（机器）对应若干个“虚拟节点”，这个对应个数也 成为“复制个数”，“虚拟节点”在 hash 空间中以hash值排列。 通过虚拟节点的引入，实现平衡性： object1->Cache1-1 object2->Cache1-2 object3->Cache3-2 object4->Cache3-1

Bloom filter 是一个简单、节省空间的概率数据结构来代表一组数据且支持成员查询； 被用来检测一个元素是不是集合中的一个成员，这种检测只会对在集合内的数据错判，而不会对不是集合内的数据进行错判， 这样每个检测请求返回有“在集合内（可能错误）”和“不在集合内（绝对不在集合内）”两种情况； Bloom filter 是牺牲了正确率换取时间和空间； 以前有“时间换空间或者空间换时间” Bloom Filter在时间、空间这两个因素之外又引入了另一个因素：错误率。 在增加了错误率这个因素之后，Bloom Filter通过允许少量的错误来节省大量的存储空间。

Bloom filter 采用的是哈希函数的方法 当这个点是 1 时，那么这个元素在集合内，反之则不在集合内； Bloom filter的缺点 当检测的元素很多的时候可能有冲突； 解决方法就是使用 k 个哈希 函数对应 k 个点，如果所有点都是 1 的话，那么元素在集合内，如果有 0 的话，元素则不在集合内。

Bloom filter工作过程 开始时集合内没有元素； 当来了一个元素 a，进行判断， 这里哈希函数有两个，计算 出对应的比特位上为 0 ，即 是 a 不在集合内，将 a 添加进 去； 之后的元素，要判断是不是 在集合内，也是同 a 一样的方 法，只有对元素哈希后对应 位置上都是 1 才认为这个元 素在集合内（可能会误判）；

随着元素的插入，Bloom filter 中修改的值变多，出现误判的几率也随之变大，当新来一个元素时，满足其在集合内的条件，即所有对应位都是1，这样就可能有两种情况： 一是这个元素就在集合内，没有发生误判； 还有一种情况就是发生误判，出现了哈希碰撞，这个元素本不在集合内。

Bloom Filter的缺点： 需要解决的问题： Bloom Filter无法从Bloom Filter集合中删除一个元素，因为该元 素对应的位会牵动到其他的元素。 一个简单的改进就是 counting Bloom filter，用一个counter数组代替位 数组，就可以支持删除了。 Bloom Filter的hash函数选择会影响算法的效果。 需要解决的问题： 如何根据输入元素个数n，确定位数组m的大小及hash函数个数， 即hash函数选择会影响算法的效果。 当hash函数个数k=(ln2)*(m/n)时错误率最小。 在错误率不大于E的情况 下，m至少要等于n*lg(1/E) 才能表示任意n个 元素的集合。但m还应该更大些，因为还要保证bit数组里至少一半为 0，则应该m ≥ nlog2(1/E)*log2E 。 例：错误率0.01，则此时m应大概是n的13倍，k大概是8个。

单向函数 给定任意的两个集合X、Y，函数f:X→Y被称为单 向函数，如果： 对于每一个x∈X，f(x)的值很容易计算； 对于几乎所有的属于值域任意一个y，则在计算上不 可能求出x使得y= f(x) 例：把一个陶瓷盘子很容易打碎，但是把碎片拼成 一个盘子基本上是不可能的。 在密码学中最常用的单向函数有两类： 公开密钥密码中使用的单向陷门函数； 消息摘要中使用的单向散列函数。

注意： 不能将单向函数与不可逆函数的概念混同 目前还没有理论证明单向函数的存在 单向函数可能是一个数学意义上的可逆或者一一对应的函数，而一个不可逆函数却不一定是一个单向函数； 目前还没有理论证明单向函数的存在 因为单向函数的存在意味着计算机中的一个具有挑战性的猜想P=NP，即NP完全问题的解决，NP完全理论却不是以证明单向函数而存在； 现实中存在与单向函数相近似的函数，但是只是表现出单向函数的性质，没有从理论上证明 整数相乘：如两个素数相乘，不管素数多大都很容易计算乘积，但是由乘积分解出两个因子是非常困难的。

陷门单向函数 单向函数不能用于加密因为没人能解开； 陷门单向函数是一个有秘密陷门的单向函数 拆一个复杂设备（手表）就是一个陷门单向函数 在一个方向上易于计算，而在另一个方向上难于计算机；但是如果知道一个窍门或者秘密，则也能容易在另一个方向上计算这个函数； 已知x容易计算f(x)，已知f(x)，难于计算x，但是如果知道y，则易于计算x。 拆一个复杂设备（手表）就是一个陷门单向函数 拆手表容易，装手表困难； 如果有图纸说明，则装手表也比较容易。

单向函数不能用作加密，因为单向函数加密的信 息是无人能解开它的，但可以用陷门单向函数构 造公开密钥密码。 公钥密码体制的设计就是寻找陷门单向函数。 计算f(x)相当于加密，陷门y相当于私有密钥，而利用 陷门y求f(x)中的x则相当于解密。 1976年，Diffie W.和Hellman M.E.在他们的《密码学的 新方向》一文中提出了公钥密码和陷门单向函数概念 时，但并没能给出一个陷门单向函数的实例；

1978年，Rivest R. L. ，Shamir A. 和Adleman L. M 1978年，Rivest R.L.，Shamir A.和Adleman L.M.在其文《实现 数字签名和公钥密码体制的一种方法》中最先提出了一种可 行的实现方法，这就是我们现在广泛使用的RSA体制。 RSA体制的提出真正使得互不相识的通信双方在一个不安全 的信道上进行安全通信最终成为可能，是今天CA服务的源泉； 第一个陷门单向函数和第一个公钥密码体制RSA是Rivest R.L.， Shamir A.和Adleman L.M.在1978年才提出的； 此后，人们又尝试过很多种单向函数的设计方法，比如利用 背包问题、纠错码问题、因子分解问题、离散对数问题、有 限自动机合成问题等，但至今除了离散对数和因子分解问题， 其它陷门单向函数都被证明存在安全缺陷或者因为其复杂性 不能归约到某个困难问题而无法得到广泛的认可。