k1?344401659k3?212228844k5?047900151k7?034367980k2?325510778k4?329938157k6?372500191 k8?546332190 k9?509496993 k10?132489973我们选取m?4969，m?2?4967。得到检测数据
hj(k)?h(k)??jg(k)(mod49，
根据上式我们得到
0?hj(k)?4969h(k)?k(mod4969)，g(k)?k?1(mod4967),
，
通过计算，得到
k1?269，k2?1526和k3?2854。 我们首先将这几个数分配为文件的地址。 因为
k4?1526(mod4969)，但是前面我们已经将1526作为存储地址，那么我们
公式
hj(k)?h(k)?j?g(k)(modm)得出
h1(k4)?h(k4)?g(k4)?1526?216?1742(mod4969)，其中，j?1，
g(k4)?1?k4?216(mod4967)。这样我们得出第四个地址1742。同理，我们可以得出第五，六，七，八个文件分配的地址，分别为：
3960,4075,2376,578。
我们可以发现，第九个地址578的值之前已经被占据，我们采用与第四个地址相同的方法，得到新的分配给第九个文件的地址2580。同样的，我们得到第十个文件分配的自由地址为1958。其中，我们得到这第十个地址经过两次运算，第一次运算得到的1742之前已经是第四个文件的地址，我们需要继续采用公式
hj(k)?h(k)?j?g(k)(mod4969)的地址。
，其中，j的值为2。我们得到所求的第十个文件
26
表3.2 学生文件的散列函数
社会安全号码 h(k)269 1526 2854 1526 3960 4075 2376 578 578 1526 h1(k) 1742 2580 1742 h2(k) 1958 344401659325510778212228844329938157047900151372500191034367980546332190509496993132489973
3.5 校验位
检验字符（数据）串的误差我们同样可以应用同余理论进行解决。在这节中，我们将学习比特串的误差检测。那么什么是比特串？比特串是用来做什么的？我们将不再详细介绍，只需要知道比特串是用来代表计算机数据的。十进制的数据串即比特串常用来识别护照、支票、书籍或者其他的各种各样的目的。下面我们将要介绍一下同余理论时如何检测十进制的数据串的误差。
我们在传播或者处理比特串时可以产生误差。简单的检测方法是在比特串
x1x2...xnxn?1后面加上一个奇偶校验位。它的定义是：
?...?xn(mod xn?1?x1?x2 2)那么我们可以得出，如果字符串的前n个位有偶数个1，则
xn?1?1xn?1?0，否则的话，
。
x1x2...xnxn?1变化后的字符串满足下面的同余式：
?xn?xn?1?0(mo d2) x1?x2?...我们就是利用上面这个公式来检测和寻找误差。 假设我们发送了数据串
x1x2...xnxn?1y1y2...ynyn?1，接受到的数据串是数据串。如果
没有误差的话，那么这两个数据串应该相等，即
xi?yi,i?1,2,...,n?1。但是如若
存在误差，那么就改变了一个或多个位置，我们检验是否有
27
y1?y2?..?.yn?yn?1?0(mod2)
如果上述同余式不成立，那么应该至少一位字符出现错误。即使同余式成立，仍有可能出现误差。当误差减少并且是随机的，最通常的误差是出现单个误差，我们可以很容易发现。在最一般的情况下，我们可以检测出奇数个的误差，却不能检查出偶数个误差。
证明：奇偶校验分为奇校验和偶校验两种，两者类似，我们以奇校验为例说明。 奇校验是通过在末尾添加1或者0的方式使1的个数为奇数。校验时通过1的个数是否为奇数判断是否出错了。
如 11001100编码后为 11001100 1（最后一位添加为1，使1的个数是奇数5） 11100110编码后则为11100110 0（1的个数已经是奇数，添0）
当出错个数为奇数时，将导致1的个数的奇偶发生变化，可以检测出错误，而为偶数时，1的个数的奇偶不变，故检测不出。
例如上例，11001100 1 ，当有3个(奇数个)位出错，假设是后三位那么就变成 11001011 1这时1的个数就变成了6个，可以判断，出错了。而2个(偶数个)位出错，假设是后两位那么就变成 11001111 1这时1的个数为7个，仍然是奇数，就检测不出错误了。
这里所体验的基本原理是：一个奇数加上偶数仍然是奇数，加上奇数就变成偶数。
例 假设收到了1101111和11001000，其中每个字符串后面的最后一位均是奇偶校验位。对于第一个数据串，我们有1?1?0?0?1?1?1?1?0(mod2)，所以，我们收到的字符串或者就是所传送的，或者就是包含了偶数个误差。同样的，对于第二个字符串，我们有1?1?0?0?1?0?0?0?1(mod2)，就可以得出结论：收到的字符串不是所传送的，我们可以要求重新发送。
十进制字符串在许多不同的场合被用来作为认证数。而我们本节所学习的校验位被用来找出这些字符串中的误差，我们可以运用各种不同的方案来计算校验位。如：校验位可以用来发现护照号码中的错误，在一些欧洲的国家，在他们应用的方案中，如果x1x2x3x4x5x6是护照号码，那么校验位x7可以被这样选择：
6mod x7?7x1?3x2?x3?7x4?3x5?x( 10)我们下面举一个十进制的例子。
例3.8 假设有一个护照的号码是211894，我们为了找出校验位
x7，计算
28
x7?7?2?3?1?1?1?7?8?3?9?1?4?5( mod10)那么得到校验位是5，并且我们会将七位数字211894印在护照上面。
按照上述方法，我们将计算出的一个校验位加在护照上，总是能够发现误差。为了进一步证明这一点，我们假设在某一位上制造一个误差a，即
yj?xj?a(mod10)。其中
xj是第j位正确的数字。但是
x7yj不正确且替换了正确的
a(mod10),当
数字。从校验位的定义我们可以知道，可以变为7a或者3a或者
两个数字的误差不是5或者-5，即他们不是xi?xj?5式子中的xi和xj。利用这种方案我们可以检测出许多混乱的三位数字的可能误差。 下面将注意力转移到图书出版过程中校验位的使用：
国际标准书号（ISBN）几乎可以识别所有出版的书。国际标准书号是由出版商分配的市委数字的代码。校验位在国际标准书号中可以用来发现当国际标准书号被复制时经常出现的误差，也就是说单个误差和因为两个数字颠倒位置而造成的误差。例如：一本书第一版的国际标准书号是0-201-06561-4。第一组的数字是0，代表本书的语种—英语；第二组的数字是201代表出版公司—艾迪生·维斯理出版公司；第三组的数字是06561表示出版公司分配给本书的一组数；最后一组数4因为分组的型号是根据语种和出版商的不同而不同的，所分得的校验位。
校验位是如何被确定的？又是怎样用来发现经常出现的误差的？ 假设一本书的国际标准书号是
x1x2...x10x10，其中是校验位。前九个数字是十
0,1,2,...9?x进制数字，属于集合?而校验位10是一个十一进制的数字，属于集合
?0,1,2,...9,X?，其中X是十一进位的数字，在十进制符号下代表整数10。我们
选择校验位满足同余式
?ixi?110i?0(mod11)
x10很容易知道，校验位可以由同余式
x10??ixi(mod11)i?19计算得到。即校验
位是前九位数字的加权和除11的剩余。
例 某本书的国际标准书号是0-201-06561。找出这本书的第一版的国际标准书号的校验位。
x10?1?0?2?2?3?0?4?1?5?0?6?6?7?5?8?6?9?1?4(mod11)
29
所以国际标准书号是0-201-06561-4。若一本书的国家标准书号是3-540-19102开始的，则根据同余式
x10?1?3?2?5?3?4?4?0?5?1?6?9?7?1?8?0?9?2?10(mod11)
十进制10对应于十一进制X,我们可以知道校验位是X。所以国际标准书号是3-540-19102-X。
国际标准书号还可以检测出单个的错误或者两个数字是否倒置了。
30