1.哈希函数的构造方法 直接定址法：H(k)=k 或H(k)=a*k+b（线形函数） 如：人口数字统计表 地址 1 2 3。100 年龄 1 2 3。
100 人数 67 3533 244。4 数字分析法：取关键字的若干数位组成哈希地址 如：关键字如下：若哈希表长为100则可取中间两位10进制数作为哈希地址 。
81346532 81372242 81387422 81301367 81322817 81338967 81354157 81368537 平方取中法：关键字平方后取中间几位数组成哈希地址 折叠法：将关键数字分割成位数相同的几部分（最后一部分的位数可以不同）然后取几部分的叠加和（舍去进位）作为哈希地址 。除留余数法：取关键字被某个不大于表长m的数p除后所得的余数为哈希地址 。
H(k)=k mod p p<=m 随机数法：H(k)=rondom(k) 。2.处理冲突的方法 假设地址集为0..n-1，由关键字得到的哈希地址为j(0<=j<=n-1)的位置已存有记录，处理冲突就是为该关键字的记录找到另一个"空"的哈希地址 。
在处理中可能得到一个地址序列Hi i=1,2, 。k 0<=Hi<=n-1），即在处理冲突时若得到的另一个哈希地址H1仍发生冲突，再求下一地址H2，若仍冲突，再求H3 。
怎样得到Hi呢？ 开放定址法：Hi=(H(k)+di) mod m (H(k)为哈希函数；m为哈希表长；di为增量序列） 当di=1,2,3, 。
m-1 时叫线性探测再散列 。当di=12,-12,22,-22,32,-32, 。
,k2,-k2时叫二次探测再散列 。当di=random(m)时叫伪随机探测序列 。
例：长度为11的哈希表关键字分别为17,60,29，哈希函数为H(k)=k mod 11，第四个记录的关键字为38，分别按上述方法添入哈希表的地址为8,4,3（随机数=9） 。再哈希法：Hi=RHi(key) i=1,2, 。
,k，其中RHi均为不同的哈希函数 。链地址法：这种方法很象基数排序，相同的地址的关键字值均链入对应的链表中 。
建立公益区法：另设一个溢出表，不管得到的哈希地址如何，一旦发生冲突，都填入溢出表 。3.哈希表的查找 例：如下一组关键字按哈希函数H(k)=k mod 13和线性探测处理冲突所得的哈希表a[0..15]: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 14 01 68 27 55 19 20 84 79 23 11 10 当给定值k=84，则首先和a[6]比在依次和a[7],a[8]比结果a[8]=84查找成功 。
当给定值k=38，则首先和a[12]比，再和a[13]比，由于a[13]没有，查找不成功，表中不存在关键字等于38的记录 。5.5 查找第k小元素 查找第k小元素即在n个元素中（未排序）找到第k小的元素 。
方法同快速排序，采用递归方式 。程序如下： program kspv; const n=7; type arr=array[1..n] of integer; var b:arr; i,k:integer; function p(s,t:integer):integer; var i,j,t1,x:integer; begin i:=s;j:=t;x:=b[i]; repeat while (b[j]>=x) and (j>i) do j:=j-1; if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end; while (b[i]<=x) and (i上一页