会计学根据(gēnjù)设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为纪录在表中的存储位置，这种表便称为哈希表，这一影像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址。散列方法在表项的存储位置与它的关键字之间建立一个(yīɡè)确定的对应函数关系Hash()，使每个关键字与结构中一个(yīɡè)唯一存储位置相对应：Address＝Hash(Rec.key)在查找时，首先对表项的关键字进行函数计算，把函数值当做表项的存储位置，在结构中按此位置取表项比较。若关键字相等，则查找成功。在存放表项时，依相同函数计算存储位置，并按此位置存放。构造散列函数时的几点要求：散列函数的定义域必须包括需要存储的全部关键码，如果散列表允许有m个地址时,其值域必须在0到m-1之间。散列函数计算(jìsuàn)出来的地址应能均匀分布在整个地址空间中：若key是从关键字集合中随机抽取的一个关键字，散列函数应能以同等概率取0到m-1中的每一个值。散列函数应是简单的，能在较短的时间内计算(jìsuàn)出结果。1.直接定址法此类函数直接取关键字或关键字的某个线性函数值作为散列地址：Hash(key)＝a*key+b{a,b为常数}这类散列函数是一对一的映射，一般不会产生冲突。但是(dànshì)，它要求散列地址空间的大小与关键字集合的大小相同。2.数字分析法设有n个d位数，每一位可能有r种不同的符号。这r种不同的符号在各位上出现(chūxiàn)的频率不一定相同，可能在某些位上分布均匀些；在某些位上分布不均匀，只有某几种符号经常出现(chūxiàn)。可根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址。942148941269940527941630941805941558942047940001①②③④⑤⑥3.平方取中法此方法在词典处理中使用十分广泛。它先计算构成关键字的标识符的内码的平方，然后按照散列表的大小取中间的若干位作为散列地址(dìzhǐ)。设标识符可以用一个计算机字长的内码表示。因为内码平方数的中间几位一般是由标识符所有字符决定，所以对不同的标识符计算出的散列地址(dìzhǐ)大多不相同，即使其中有些字符相同。在平方取中法中，一般取散列地址(dìzhǐ)为2的某次幂。例如，若散列地址(dìzhǐ)总数取为m=2r，则对内码的平方数取中间的r位。如果r=3，所取得的散列地址(dìzhǐ)参看图的最右一列。4.折叠法此方法把关键字自左到右分成位数相等的几部分，每一部分的位数应与散列表地址位数相同，只有最后一部分的位数可以短一些。把这些部分的数据叠加起来，就可以得到(dédào)具有该关键字的记录的散列地址。有两种叠加方法：移位法—把各部分的最后一位对齐相加；分界法—各部分不折断，沿各部分的分界来回折叠，然后对齐相加，将相加的结果当做散列地址。示例：设给定的关键字为key=23938587841，若存储空间限定3位,则划分(huàfēn)结果为每段3位.上述关键字可划分(huàfēn)为4段：23938587841把超出地址位数的最高位删去,仅保留最低的3位，做为可用的散列地址。一般当关键字的位数很多，而且关键字每一位上数字的分布大致比较均匀时，可用这种方法(fāngfǎ)得到散列地址。5.除留余数法设散列表中允许的地址数为m,取一个不大于m，但最接近于或等于m的质数p,或选取(xuǎnqǔ)一个不小于20的质因数的合数作为除数，利用以下公式把关键字转换成散列地址。散列函数为：hash(key)=key%ppm其中,“%”是整数除法取余的运算，要求这时的质数p不是接近2的幂。示例：有一个关键字key=962148，散列表大小m=25，即HT[25]。取质数p=23。散列函数hash(key)=key%p。则散列地址为：hash(962148)=962148%23=12可以按计算出的地址存放(cúnfàng)记录。需要注意的是，使用上面的散列函数计算出来的地址范围是0到22，因此，从23到24这几个散列地址实际上在一开始是不可能用散列函数计算出来的，只可能在处理溢出时达到这些地址。以上介绍了几种常用的散列函数。在实际工作中应根据关键字的特点，选用适当的方法。有人曾用“轮盘赌”的统计分析方法对它们进行了模拟分析，结论是平方取中法最接近于“随机化”。在应用平方取中法时，若关键字不是(bùshi)整数而是字符串时，可以把每个字符串转换成整数。转换的方法：把字符串从右向左，按一个固定长度(例如4)进行分段，必要时可在最左