主要内容散列散列在随机存储中：负载因子α=n/m散列表的空间大小为m填入表中的结点数为n冲突某个散列函数对于不相等的关键码计算出了相同的散列地址在实际应用中，不产生冲突的散列函数极少存在同义词发生冲突的两个关键码把关键码值映射到存储位置的函数，通常用h来表示Address＝Hash(key)构造散列函数时的几点要求：散列函数的定义域必须包括需要存储的全部关键码，如果散列表允许有m个地址时,其值域必须在0到m-1之间。散列函数计算出来的地址应能均匀分布在整个地址空间中：若key是从关键码集合中随机抽取的一个关键码，散列函数应能以同等概率取0到m-1中的每一个值。散列函数应是简单的，能在较短的时间内计算出结果。除留余数法折叠法平方取中法基数转换法直接定址法除留余数法H(key)=key%p或H(key)=key%p+c这里p<m；余数总在0～p-1之间。示例：有一个关键码key=962148，散列表大小m=25，即HT[25]。取质数p=23。散列函数hash(key)=key%p。则散列地址为hash(962148)=962148%23=12。可以按计算出的地址存放记录。需要注意的是，使用上面的散列函数计算出来的地址范围是0到22，因此，从23到24这几个散列地址实际上在一开始是不可能用散列函数计算出来的，只可能在处理冲突时达到这些地址。选取p为质数的理由：设key值都为奇数，选p为偶数；则H(key)=key%p，结果为奇数，一半单元被浪费掉。设key值都为5的倍数，选p为95；则H(key)=key%p，结果为：0、5、10、15、……90。4/5的单元被浪费掉。折叠法（移位法、分界法）key=381，412，975选取768或570作为散列地址。平方取中法e.g:（4731）2＝22382361；选取82（在m＝100情况下）。此方法在词典处理中使用十分广泛。它先计算构成关键码的标识符的内码的平方，然后按照散列表的大小取中间的若干位作为散列地址。设标识符可以用一个计算机字长的内码表示。因为内码平方数的中间几位一般是由标识符所有字符决定，所以对不同的标识符计算出的散列地址大多不相同，即使其中有些字符相同。标识符内码内码的平方散列地址A0101001A1013420420042A9014423420342B024004DMAX0415013021526443617100443DMAX104150130345264473522151420352AMAX01150130135423617100236AMAX101150130343454246522151420652基数转换法将关键字k转换为另外一种数字基数，再对表的大小取模。如：k=(345)10(423)9%表的大小直接地址法H(key)=key或H(key)=a×key＋b如：k1,k2分别有值10、1000；选10、1000作为存放地址。在实际工作中应根据关键码的特点，选用适当的方法。有人曾用“轮盘赌”的统计分析方法对它们进行了模拟分析，结论是平方取中法最接近于“随机化”。查找