列表与探测法"/>
散列表与探测法
动态查找的时候,如果用查找树同时对俩个变量名(字符串)进行查找,会导致效率不高的问题.
引入散列的思想:把字符串变成数字,使得对字符串的比较变成对数字的比较.
查找方式 | 时间复杂度 |
---|---|
顺序查找 | O(n) |
二分查找(静态查找) | O(log2N) |
二叉搜索树 | O(h)–h为二叉查找树的高度 |
平衡二叉树 | O(log2N) |
查找的本质:已知对象求位置
(1)有序安排对象:半序,全序
(2)直接算出的对象位置:散列
散列的基本概述
散列查找法的俩项基本工作:
计算位置:构造散列函数确定关键词的存储位置
解决冲突:应用某种策略解决多个关键词位置相同的问题
时间复杂度是O(1),查找时间和问题规模无关.
散列表(哈希表)
装填因子:设散列表空间大小是m,填入表中的元素个数是n.则称a=n/m是散列表的装填因子.
散列函数的构造方法
一个好的散列函数需要考虑以下俩个因素:
1)计算简单,以便于提高转换速度.
2)关键字对应的地址空间分布均匀,以尽量减少冲突.
数字构造
(1)直接定址法:取关键词的某个线性函数值作为散列地址,h(key)=a*key+b
(2)除留余数法
此时的p一般取Tablesize,满足p是素数.
(3)数字分析法
分析数字关键字在各位上的变化情况,取比较随机的位作为散列地址.
(4)折叠法
把关键词分割成位数相同的几部分,然后叠加.
(5)平方取中法
字符构造
1.一个简单的散列函数—ASCII码加和法
2.前三个字符移位法
3.好的散列函数—移位法
(设计关键词中所有的n个字符,并且分布的好)
Index Hash(const char*Key,int TableSize)
{unsigned int h=0;//散列函数值初始化为0while(*key !='\0'){h=(h<<5)+*k++;}return h%TableSize;
}
处理冲突的方法:
换个位置:开放地址法
一旦发生冲突之后(该地址已有其他元素),按照某种规则去寻找另外一个空的地址。
1)若发生了第i次冲突,试探的下一个位置将会增加d(i),基本公式是 h(key)=(h(key)+d) mod tablesize
2)根据d的不同设计三种解决冲突方法:线性探测,平方探测,双散列
线性探测
令d=i(以增量序列1,2……(TableSize-1)循环试探下一个存储地址
会产生聚集现象。
平方探测法
以增量序列±q^2的增量序列来循环探测下一个存储地址 q<=[tablesize/2]
二次探测不一定能够探测得到每个位置,但是如果散列表长度设置为某个(4k+3)形式的素数的时候,平方探测法就可以探查整个散列表的空间。
typedef struct HashTbl*HashTable;
struct HashTbl{int TableSize;Cell* TheCells;}HashTable inilt(int TableSize)
{HashTable H;if(TableSize<min){Error("散列表太小");return NULL;}//分配散列表H=(HashTable)malloc(sizeof(struct HashTbl));if(H==NULL){FatalError("空间溢出");}H->TableSize=nextPrime(TableSize);//分配散列表cellsH->TheCells=(Cell*)malloc(sizeof(Cell)*H->TableSize);if(H->TheCells==null)Error("空间溢出");for(i=0;i<H->TableSize;i++)H->TheCell{i].info=Empty;return H;}Position Find(int key,HashTable H)
{Position cur,new;int cnum=0;//记录冲突次数new=cur=Hash(Key,H->TableSize);while(H->TheCells[NewPos].info !=Empty && H->TheCells[New]. E!=Key){//字符串类型的关键词需要strcmp函数if(++cnum%2){new=cur+(cunm+1)/2*(cum+1)/2;while(new>=H->TableSize)new-=H->TableSize;}else{new=cur-cnum/2-cnum/2;while(new<0)new+=H->TableSize;}}return new;}
在开放地址散列表中,删除操作要很小心。通常只能”懒惰删除",也就是需要增加一个删除标记(Deleted),而并不是要真正删除它,以便于查找的时候不会断链,其空间可以在下次插入的时候重用。
双散列探测法
探测序列应该保证所有的散列存储单元都能够被探测得到,应该具有以下的效果。
d(i)为i*h2(key)
h2(key)=p-(key mod p)
再散列
当散列表的元素太多,装填因子a过大,查找效率会降低。
散列表扩大时候,原有元素要重新计算放置到新表中。
一般装填因子的范围是0.5~0.75
分离链接法
同一位置的冲突对象组织在一起,放在同一个单链表中:链地址法
ListNode* Find(int key,HashTable H)
{ListNode* P;int pos;pos=Hash(Key,H->TableSize);//初始散列位置P=H->Thelists[pos].Next;//获取链表头while(P!=null && strcmp(P->e,Key))P=P->next;return P;
}
散列表的性能分析
平均查找长度(ASL)用来度量散列表的查找效率:成功和不成功
关键词的比较次数取决于产生冲突的多少
影响冲突的三个因素:
1)散列函数是否均匀
2)处理冲突的方法
3)散列表的装填因子a
选择合适的h(Key),散列表的查找期望是常数O(1),它几乎与关键字的空间大小n无关!也适合于关键字直接比较量大的问题 。
它是以较小的装填因子为前提,因此散列方法是以空间换取时间的策略。
散列存储对关键字是随机的,不便于顺序查找关键字,也不适合范围查找或者最大值最小值查找。
开放地址法:散列表是一个数组,存储效率搞,随机查找。但是它容易出现聚集现象。
分离链接法:散列表是顺序存储和链式存储的结合,链表
部分的存储效率和查找效率都比较低。
更多推荐
散列表与探测法
发布评论