查找

查 找 一、基本概念与术语 关键字 关键字是数据元素（）中某个数据项的值，用它可以标识一个数据元素（记录）。能唯一确定一个数据元素（记录）的关键字，称为主关键字；而不能唯一确定一个数据元素（记录）的关键字，称为次关键字。 查找 查找表是由具有同一类型（属性）的数据元素（记录）组成的集合。分为静态查找表和动态查找表两类。 静态查找表：仅对查找表进行查找操作，而不能改变的表； 动态查找表：对查找表除进行查找操作外，可能还要进行向表中插入数据元素，或删除表中数据元素的表。 二、查找的性能性能分析 分析查找算法的效率，通常用平均查找长度ASL(Average Search Length)来衡量。在查找成功时，平均查找长度ASL是指为确定数据元素在表中的位置所进行的关键字比较次数的期望值。 ASL= P i · C i n ∑ i=1 对一个含n个数据元素的表，查找成功时 n ∑ i=1 P i =1 其中：Pi为表中第i个数据元素的查找概率， Ci为表中第i个数据元素的关键字与给定值kx相等时，按算法定位时关键字的比较次数。以顺序查找为例，n个数据元素的表，给定值kx与表中第i个元素关键字相等，即定位第i个记录时（从后向前比较），需进行n-i+1次关键字比较，即Ci=n-i+1。则查找成功时，顺序查找的平均查找长度为： ASL= P i ·（ n- i +1 ） n ∑ i=1 １ ─ ｎ 设每个数据元素的查找概率相等，即 Pi =　 ，则等概率情况下有 n ∑ i=1 ASL= （ n- i +1 ） = １ ─ ｎ ｎ＋１ ─── 　 ２ 查找不成功时，关键字的比较次数总是n+1次。 三、有序表的折半查找 有序表即是表中数据元素按关键字升序或降序排列。折半查找的为：在有序表中，取中间元素作为比较对象，若给定值与中间元素的关键字相等，则查找成功；若给定值小于中间元素的关键字，则在中间元素的左半区继续查找；若给定值大于中间元素的关键字，则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败。 【步骤】 ① low=1；high=length； // 设置初始区间 ② 当low>high时，返回查找失败信息 // 表空，查找失败 ③ low≤high，mid=(low+high)/2; // 取中点 a. 若kxtbl.elem[mid].key，low=mid+1； 转② // 查找在右半区进行 c. 若kx=tbl.elem[mid].key，返回数据元素在表中位置 // 查找成功 #define MAX 100 typedef struct{ KeyType key; ElemType date; }RecType; typedef struct{ RecType r[MAX]; int length; }sqlist; int Binary_Search( sqlist R, KeyType k ) { /* 在表r中查找关键字为k的数据元素，若找到返回该元素在表中的位置，否则，返回-1*/ int mid, low=1, high=r.length； while( low <= high ) { mid = ( low + high ) / 2； if( k < R.r[mid].key ) high = mid - 1； else if( k > R.r[mid].key ) low = mid + 1； else return mid; } return -1; } 【性能分析】 从折半查找过程看，以表的中点为比较对象，并以中点将表分割为两个子表，对定位到的子表继续这种操作。所以，对表中每个数据元素的查找过程，可用二叉树来描述，我们称这个描述查找过程的二叉树为判定树。 下面以关键字为：（7，14，18，21，23，29，31，35，38，42，46，49，52）的有序表为例说明折半查找的性能分析。 49 38 29 18 7 42 52 31 23 46 35 14 21 描述折半查找过程的判定树 查找表中任一元素的过程，即是判定树中从根到该元素结点路径上各结点关键码的比较次数，也即该元素结点在树中的层次数。从判定树可以看出，查找３１仅需比较一次；查找１８，４２需要比较２次；查找７，２３，３５，４９需要比较３次；查找１４，２１，２９，３８，４６，５２需要比较４次。设每个数据元素的查找概率相等，则有： ASL成功　＝　(1+2*2+4*3+6*4)/13 如果在上图中所有结点的空指针域上加上一个指向方形结点的指针，那么折半查找查找不成功时就是走了一条从根结点到方形结点的路径，此时查找不成功的平均查找长度为： ASL失败 ＝　(2*3+12*4)/14　（注意查找成功和失败时的分母相差1） 折半查找的平均查找长度为：ASLbs = ≈log2(n+1)-1；折半查找的时间效率为O(log2n)。 四、分块查找 分块查找又称索引顺序查找，是对顺序查找的一种改进。分块查找要求将查找表分成若干个子表，并对子表建立索引表，查找表的每一个子表由索引表中的索引项确定。索引项包括两个字段：关键字字段 (存放对应子表中的最大关键字值) ；指针字段 (存放指向对应子表的指针) ，索引表按关键字有序，则表或者有序或者分块有序（所谓分块有序指的是第二个子表中的所有记录的关键字均大于第一个子表中的最大关键字，第三个子表中的所有关键字均大于第二个子表中的最大关键字，依次类推）。查找时，先用给定值kx在索引表中检测索引项，以确定所要进行的查找在查找表中的查找分块 (由于索引项按关键字字段有序，可用顺序查找或折半查找) ，然后，再对该分块进行顺序查找。 关键字集合为：（88，43，14，31，78，8，62，49，35，71，22，83，18，52）按关键字值31，62，88分为三块建立的查找表及其索引表如下： 关键码字段 指针字段 索引表31 62 88 1 6 11 查找表 14 31 8 22 18 43 62 49 35 52 88 78 71 83 1 2 　3 　 4 5 6 7 8 9 10 11 12 13 14 五、二叉排序树 二叉排序树定义 二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树： 58 42 98 70 90 63 45 55 83 67 10⑴ 若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值。 ⑵ 左右子树也都是二叉排序树。 由右图可以看出，对二叉排序树进行中序遍历，便可得到一个按关键字有序的序列， 因此，一个无序序列，可通过构造一棵二叉排序树而成为有序序列（二叉排序树是 一种动态的树，其特点是树的结构通常不是一次生成的，而是在查找过程中，当树 中不存在关键字等于给定值的结点时再进行插入；新插入的结点，一定是一个新添 加的叶子结点）。 二叉排序树的插入 void insert( BiTree *t, ElemType e ) //二叉排序树插入的递归算法 { if( t == NULL ) { BiTree *s = (BiTree)malloc(sizeof(BiTree)); s->data = e; s->lchild = NULL; s->rchild = NULL; t = s;//注意：这里对参数t的修改，不会影响到实际传入的参数，所以这种修改传入的二叉树的指针的方式有问题 //应该将参数BiTree改为指向指针的指针：BiTree **t，具体需要实际代码验证，暂时知道这回事即可 }else if( t->data == e ) { return; } else if( e < t->data ) { insert( t->lchild, e ); } else if( e > t->data ) { insert( t->rchild, e ); } } void insert( BiTree *t, ElemType e )//二叉排序树插入的非递归算法 { //为插入新元素寻找插入位置，定义p指向当前待比较的结点，初始指向根结点，定义指针parent //指向p的双亲结点，初始为NULL BiTree *p = t, *parent = NULL; while( p != NULL ) { parent = p; if( e < p->data ) p = p->lchild; else p = p->rchild; } //建立值为e,左右指针为空的新结点 BiTree *s = (BiTree)malloc(sizeof(BiTree)); s->data = e; s->lchild = NULL; s->rchild = NULL; //将新结点插入到二叉排序数的确定位置上 if( parent == NULL ) t = s; else if( parent->data == e ) return; else if( e < parent->data ) parent->lchild = s; else parent->rchild = s; }//该实现代码同样存在上面类似的问题，主要参考其算法的思想 二叉排序树的建立 void create( BiTree *t, ElemType a[], int n ) { t = NULL; for( int i = 0; i < n; i ++ ) insert( t, a[i] ); } 二叉排序树的查找 BiTree search( BiTree *t, ElemType e )//二叉排序树查找的递归算法 { if( t == NULL ) { return NULL; } else { if( t->data == e ) return t; else if( e < t->data ) return ( search( t->lchild, key ) ); else return ( search( t->rchild, key ) ); } } BiTree search( BiTree *t, ElemType e )//二叉排序树查找的非递归算法 { BiTree *p = t; while( p != NULL ) { if( e == p->data ) return p; else if( e < p->data ) p = p->lchild; else p = p->rchild; } return NULL; } 二叉排序树的删除 bool delete( BiTree *t, ElemType k ) { BiTree *p = t, *father = NULL; //查找关键字为k的结点 while( p != NULL && p->data != k ) { if( k < p->data ) { father = p; p = p->lchild; } else { father = p; p = p->rchild; } } //删除查找到的结点 if( p == NULL ) { return false; } else { //p结点为叶子节点 else if( p->lchild == NULL && p->rchild == NULL ) { if( father != NULL ) { if( father->lchild == p ) father->lchild == NULL; else father->rchild == NULL; } else t == NULL; } //p结点的左子树为空，右子树不为空 else if( p->lchild == NULL && p->rchild != NULL ) { if( father != NULL ) { if( father->lchild == p ) father->lchild = p->rchild; else father->rchild = p->rchild; } else t = p->rchild; } //p结点的左子树不为空，右子树为空 else if( p->lchild != NULL && p->rchild == NULL ) { if( father != NULL ) { if( father->lchild == p ) father->lchild = p->lchild; else father->rchild = p->lchild; } else t = p->lchild; } //p结点的左右子树都不为空 else if( p->lchild != NULL && p->rchild != NULL ) { BiTree *q = p->lchild; father = p; while( q->rchild != NULL ) { father = q; q = q->rchild; } p->data = q->data; if( father->lchild == q ) father->lchild = q->lchild; else father->rchild = q->lchild; } } } 注：当被删除结点p的左右孩子均存在时，有三种方法〔本算法采用第一种方法〕： （1）在p的左子树中找最大的值代替p； （2）在p的右子树中找最小的值代替p； （3）令p的左子树为其父亲结点的左子树，而p的右子树链接到p的左子树上； 六、平衡二叉树(AVL树) 91 0 0 0 0 65 50 47 41 85 30 60 72 78 42 -3 3 0 -2 0 2 1平衡二叉树或者是一棵空树，或者是具有下列性质的二叉排序树：它的左子树和右子树都是平衡二叉树，且左子树和右子树高度之差的绝对值不超过1。 41 85 30 60 72 78 42 -1 1 1 0 0 1 0 a.非平衡二叉树 　　　　　 b.平衡二叉树 上图给出了两棵二叉排序树，每个结点旁边所注数字是以该结点为根的树中，左子树与右子树高度之差，这个数字称为结点的平衡因子。由平衡二叉树定义，所有结点的平衡因子只能取-1，0，1三个值之一。若二叉排序树中存在这样的结点，其平衡因子的绝对值大于1，这棵树就不是平衡二叉树。 假定向平衡二叉树中插入一个结点后破坏了平衡二叉树的平衡性，首先要找出插入新结点后失去平衡的最小子树根结点的指针（失去平衡的最小子树是指以离插入结点最近，且平衡因子绝对值大于1的结点作为根结点的子树），然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，这个二叉排序树就又成为一棵平衡二叉树。设a结点为失去平衡的最小子树根结点，对该子树进行平衡化调整归纳起来有以下四种情况： 1. RR型调整（在a的右孩子的右子树上插入结点，使得a结点的平衡因子从－1变成－2） B h a h E c D h 0 -1 x B h a E c D h h+1 -2 -1 x E h+1 c D a B h+1 0 0 a.插入前 b.插入后，调整前 c.调整后 【调整策略】 调整后的子树除了各结点的平衡因子绝对值不超过1，还必须是二叉排序树。由于结点c的左子树D可作为结点a的右子树，将结点a为根的子树调整为左子树是B，右子树是D，再将结点a为根的子树调整为结点c的左子树，结点c为新的根结点，如图(c)。 h+1 h+1 E c B a D x 0 0 h B a D c E h h 0 1 h x h B a D c E h+1 2 12. LL型调整（在a的左孩子的左子树上插入结点，使得a结点的平衡因子从1变成2） a.插入前 　 b.插入后，调整前 c.调整后 其调整策略同上面的RR型调整类似。 h D b h-1 G c F h-1 h E a 0 0 13. LR型调整（在a的左孩子的右子树上插入结点，使得a结点的平衡因子从1变成2） 右图为插入前的子树，根结点a的左子树 比右子树高度高1，待插入结点x将插入到结 点b的右子树上，并使结点b的右子树高度增 1，从而使结点a的平衡因子的绝对值大于1， 导致结点a为根的子树平衡被破坏，如下图 所示。 2 h-1 G c h E a D h b F x h 0 2 h D b h-1 G c F h-1 h E a x 1 2 -1 h-1 G h E a c D h b F x h 0 0 -1 a.插入后，调整前 　　　 b.先左旋转 　 c.再右旋转 h-1 c G h E a D h b F x h 0 0 1 h-1 G c h E a D h b F x h 1 1 -2 h D b h-1 G c F h-1 h E a x 2 -1 -1 d.插入后，调整前 e.先左旋转 f.再右旋转 4.RL型调整（在a的右孩子的左子树上插入结点，使得a结点的平衡因子从－1变成－2） 其调整策略和上面的LR型调整类似. 七、哈希表与哈希方法 以上讨论的查找方法，由于数据元素的存储位置与关键字之间不存在确定的关系，因此，查找时，需要进行一系列对关键字的查找比较，即“查找算法”是建立在比较的基础上的。理想的情况是依据关键字直接得到其对应的数据元素位置，即要求关键字与数据元素间存在一一对应关系，通过这个关系，能很快地由关键字得到对应的数据元素位置。 【例】11个元素的关键字分别为 18，27，1，20，22，6，10，13，41，15，25。选取关键字与元素位置间的函数为 f(key)=key mod 11 1. 通过这个函数对11个元素建立查找表如下： 　　　　 0 1 2 3 4 5 6 7 8 9　 10 22 1 13 25 15 27 6 18 41 20 10 2. 查找时，对给定值kx依然通过这个函数计算出地址，再将kx与该地址单元中元素的关键字比较，若相等，查找成功。 哈希表与哈希方法：选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值kx计算地址，将kx与地址单元中元素关键字进行比，确定查找是否成功，这就是哈希方法(杂凑法)；哈希方法中使用的转换函数称为哈希函数(杂凑函数)；按这个思想构造的表称为哈希表(杂凑表)。 对于n个数据元素的集合，总能找到关键字与存放地址相对应的函数。若最大关键为m，可以分配m个数据元素存放单元，选取函数f(key)=key即可，但这样会造成存储空间的很大浪费，甚至不可能分配这么大的存储空间。通常关键字的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键字映射到同一个哈希地址上，这种现象称为冲突，映射到同一哈希地址上的关键字称为同义词。可以说，冲突不可能避免，只能尽可能减少。所以，哈希方法需要解决以下两个问题： 1. 构造好的哈希函数 （1）所选函数尽可能简单，以便提高转换速度。 （2）所选函数对关键字计算出的地址，应在哈希地址集中大致均匀分布，以减少空间浪费。 2. 制定解决冲突的

方案

气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载

常用的哈希函数 1. 直接定址法 Hash(key)=a·key+b (a、b为常数) 即取关键字的某个线性函数值为哈希地址，这类函数是一一对应函数，不会产生冲突，但要求地址集合与关键字集合大小相同，因此，对于较大的关键字集合不适用。 【例】关键字集合为{100，300，500，700，800，900}，选取哈希函数为 Hash(key)=key/100，则存放如下： 0 1 2 3 4 5 6 7 8 9 100 300 500 700 800 900 2. 除留余数法 Hash(key)=key mod p (p是一个整数) 即取关键字除以p的余数作为哈希地址。使用除留余数法，选取合适的p很重要，若哈希表表长为m，则要求p≤m，且接近m或等于m。p一般选取小于表长的最大质数，也可以是不包含小于20质因子的合数。 3. 数字分析法 设关键字集合中，每个关键字均由m位组成，每位上可能有r种不同的符号。 【例】若关键字是4位十进制数，则每位上可能有十个不同的数符0～9，所以r=10。 【例】若关键字是仅由英文字母组成的字符串，不考虑大小写，则每位上可能有26种不同的字母，所以r=26。 数字分析法根据r种不同的符号，在各位上的分布情况，选取某几位，组合成哈希地址。所选的位应是各种符号在该位上出现的频率大致相同。 【例】有一组关键字如下： 3 4 7 0 5 2 4 第1、2位均是“3和4”，第3位也只有 3 4 9 1 4 8 7 “ 7、8、9”，因此，这几位不能用，余 3 4 8 2 6 9 6 下四位分布较均匀，可作为哈希地址选用。 3 4 8 5 2 7 0 若哈希地址是两位，则可取这四位中的任 3 4 8 6 3 0 5 意两位组合成哈希地址，也可以取其中两 3 4 9 8 0 5 8 位与其它两位叠加求和后，取低两位作哈 3 4 7 9 6 7 1 希地址。 3 4 7 3 9 1 9 ───────────── ① ② ③ ④ ⑤ ⑥ ⑦ 4. 平方取中法 对关键字平方后，按哈希表大小，取中间的若干位作为哈希地址。 5. 折叠法(Folding) 此方法将关键字自左到右分成位数相等的几部分，最后一部分位数可以短些，然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。这种方法称为折叠法。有两种叠加方法： 1. 移 位 法 ── 将各部分的最后一位对齐相加。 2. 间界叠加法 ── 从一端向另一端沿各部分分界来回折叠后，最后一位对齐相加。 【例】关键字为 key=05326248725，设哈希表长为三位数，则可对关键字每三位一部分来分割。 关键字分割为如下四组： 253 463 587 05 用上述方法计算哈希地址 253 463 587 + 05 ─── 1308 Hash(key)=308 移位法 253 ┐ ┌ 364 ┘ └ 587 ┐ + 50 ┘ ─── 1254 Hash(key)=254 间界叠加法 对于位数很多的关键字，且每 一位上符号分布较均匀时，可采用 此方法求得哈希地址。 处理冲突的方法 1. 开放定址法 所谓开放定址法，即是由关键字得到的哈希地址一旦产生了冲突，也就是说，该地址已经存放了数据元素，就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。找空哈希地址方法很多，下面介绍三种： a. 线性探测法 Hi=(Hash(key)+di) mod m ( 1≤i < m ) 其中： Hash(key)为哈希函数 m为哈希表长度 di 为增量序列 1，2，……，m-1，且di=i 【例】关键字集为 {47，7，29，11，16，92，22，8，3}，哈希表表长为11， Hash(key)=key mod 11，用线性探测法处理冲突，建表如下： 0 1 2 3 4 5 6 7 8 9 10 11 22 47 92 16 3 7 29 8 47、7、11、16、92均是由哈希函数得到的没有冲突的哈希地址而直接存入的； Hash(29)=7，哈希地址上冲突，需寻找下一个空的哈希地址： 由H1=(Hash(29)+1) mod 11=8，哈希地址8为空，将29存入。另外，22、8同样在哈希地址上有冲突，也是由H1找到空的哈希地址的； 而Hash(3)=3，哈希地址上冲突，由 H1=(Hash(3)+1) mod 11=4 仍然冲突； H2=(Hash(3)+2) mod 11=5 仍然冲突； H3=(Hash(3)+3) mod 11=6 找到空的哈希地址，存入。 线性探测法可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。为此，可采用二次探测法，或双哈希函数探测法，以改善“堆积”问题。 b. 二次探测法 Hi=(Hash(key)±di) mod m 其中： Hash(key)为哈希函数 １ ─ 2 m为哈希表长度，m要求是某个4k+3的质数(k是整数) di 为增量序列 12，-12，22，-22，……，q2，-q2且q≤(m-1) 仍以上例用二次探测法处理冲突，建表如下： 0 1 2 3 4 5 6 7 8 9 10 11 22 3 47 92 16 7 29 8 对关键字寻找空的哈希地址只有3这个关键字与上例不同， Hash(3)=3，哈希地址上冲突，由 H1=(Hash(3)+12) mod 11=4 仍然冲突； H2=(Hash(3)-12) mod 11=2 找到空的哈希地址，存入。 c. 双哈希函数探测法（了解） Hi=(Hash(key)+i*ReHash(key)) mod m (i=1，2，……，m-1) 其中： Hash(key)，ReHash(key)是两个哈希函数， m为哈希表长度 双哈希函数探测法，先用第一个函数Hash(key)对关键字计算哈希地址，一旦产生地址冲突，再用第二个函数ReHash(key)确定移动的步长因子，最后，通过步长因子序列由探测函数寻找空的哈希地址。 比如，Hash(key)=a时产生地址冲突，就计算ReHash(key)=b，则探测的地址序列为 H1=(a+b) mod m，H2=(a+2b) mod m，……，Hm-1=(a+(m-1)b) mod m ^ ^ 0 1 2 3 4 5 6 7 8 9 10 22 3 89 ^ 11 ^ 47 ^ 37 92 ^ 16 ^ 50 ^ 29 7 ^ 8 ^ 10 ^ 2. 哈希链表法 设哈希函数得到的哈希地址域在区间 [0，m-1]上，以每个哈希地址作为一个指 针，指向一个链，即分配指针数组 ElemType *eptr[m]； 建立m个空链表，由哈希函数对关键字转 换后，映射到同一哈希地址i的同义词均 加入到*eptr[i]指向的链表中。 【例】关键字序列为 47,7,29,11,16, 92,22,8,3,50,37,89,94,21，哈希函数为 Hash(key)=key mod 11 用拉链法处理冲突，建表如右图所示。 图. 拉链法处理冲突时的哈希表 (向链表中插入元素均在表头进行) 3. 建立一个公共溢出区 设哈希函数产生的哈希地址集为[0，m-1]，则分配两个表： 一个基本表 ElemType base_tbl[m]；每个单元只能存放一个元素； 一个溢出表 ElemType over_tbl[k]；只要关键字对应的哈希地址在基本表上产生冲突，则所有这样的元素一律存入该表中。查找时，对给定值kx通过哈希函数计算出哈希地址i，先与基本表的base_tbl[i]单元比较，若相等，查找成功；否则，再到溢出表中进行查找。 哈希表的查找分析 哈希表的查找过程基本上和造表过程相同。一些关键字可通过哈希函数转换的地址直接找到，另一些关键字在哈希函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键字进行比较的过程。所以，对哈希表查找效率的量度，依然用平均查找长度来衡量。 查找过程中，关键字的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。 影响产生冲突多少有以下三个因素： 1. 哈希函数是否均匀 2. 处理冲突的方法 3. 哈希表的装填因子 分析这三个因素，尽管哈希函数的“好坏”直接影响冲突产生的频度，但一般情况下，我们总认为所选的哈希函数是“均匀的”，因此，可不考虑哈希函数对平均查找长度的影响。就线性探测法和二次探测法处理冲突的例子看，相同的关键字集合、同样的哈希函数，但在数据元素查找等概率情况下，它们的平均查找长度却不同： 线性探测法的平均查找长度 ASL=(5×1+3×2+1×4)/9=5/3 二次探测法的平均查找长度 ASL=(5×1+3×2+1×2)/9=13/9 填入表中的元素个数 哈希表的装填因子定义为：α= ──────────── 哈希表的长度 α是哈希表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。实际上，哈希表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。以下给出几种不同处理冲突方法的平均查找长度： 平均查找长度 处理冲突的方法 查找成功时 查找不成功时 线性探测法 二次探测法 与双哈希法 拉链法 哈希方法存取速度快，也较节省空间，静态查找、动态查找均适用，但由于存取是随机的，因此不便于顺序查找。 求ASL成功和ASL不成功 设一组关键字为35、27、38、26、45、55、57、63，表长为10、哈希函数为H(key) ＝ key % 7，线性探测再散列解决冲突。求ASL成功和ASL不成功 0 1 2 3 4 5 6 7 8 9 ….. 35 57 63 38 45 26 27 55 1 1 3 1 2 1 1 2 ASL成功＝(1/8)* ( 1+1+3+1+2+1+1+2 ) ASL不成功＝(1/7)* ( 9+8+7+6+5+4+3 ) (其中的分母取7而不取10。这里取7表示用该哈希函数能定为到的从0到6这7个位置。) 哈希表的插入算法 hashinsert( int s[], int m, int key ) { H = hash( key ); if( s[H] == 空 ) s[H] = key; else{ H1 = (H+1)%m; while( s[H1] != 空 ) H1 = (H1+1)%m; } s[H1] = key; } 哈希表的查找算法 hashsearch( int s[], int m, int key ) { H = hash( key ); if( s[H] == 空 ) return -1; else if( s[H] == key ) return H; else{ H1 = (H+1)%m; while( s[H1] != key && s[H1] != 空 && H1 != H ) H1 = (H1+1)%m; } if( s[H1] == key ) return H1; else return -1; } 哈希表的删除 用除留余数法作为哈希函数，用线性探测再散列解决冲突，设计算法删除关键字并将所有可以前移的元素前移填空位置，以尽量保证不断裂 解题思路： 先计算关键字的地址，若为空则空操作； 若不空，则与给定的关键字比较，若不等，按解决冲突的函数规则继续往下查找； 若相等，则在剩下的元素中查找和要查找的关键字是同义词的最后一个关键字，将其填入要删除的关键字的位置，并将该位置置空。 相关算法如下： HashDelete( ElemType s[], int m, int key ) { H = hash(key); if( s[H] == 空 ) return -1; else if( s[H] == key ) delete( s, H, H, key ); else { H1 = (H+1)%m; while( s[H1] != key && s[H1] != 空 && H1 != H ) H1 = (H1+1)%m; } if( s[H1] == key ) delete( s, H, H1, key ); else return -1 } delete( ElemType s[], int i, int j, int key ) //i为hash(key)得到的值；j为key在s中的位置； //本函数的作用是将s中和关键字key是同义词的关键字找到并确定其 //最后一个位置,然后将最后一个填充到j的位置，将最后一个的置空 { last = j; H1 = (j+1)%m; while( H1 != i ) { if( s[H1] == 空 ) break; else if( hash(s[H1] == i ) ) last = H1; H1 = (H1+1)%m; } s[j] = s[last]; //将最后一个同义词前移 s[last] = 空; //置空 }