哈希表算法 _生活百科

哈希表算法【哈希表算法】哈希表是种数据结构，它可以提供快速的插入操作和查找操作。哈希表也有一些缺点它是基于数组的，数组创建后难于扩展某些哈希表被基本填满时，性能下降得非常严重。这个问题是哈希表不可避免的，即冲突现象：对不同的关键字可能得到同一哈希地址。
基本介绍中文名：哈希表算法
外文名：Hash Tables
类型：数据结构
优点：提供快速的插入操作和查找操作
缺点：基于数组的
优缺点哈希表是种数据结构，它可以提供快速的插入操作和查找操作。第一次接触哈希表时，它的优点多得让人难以置信。不论哈希表中有多少数据，插入和删除（有时包括侧除）只需要接近常量的时间即0(1）的时间级。实际上，这只需要几条机器指令。对哈希表的使用者——人来说，这是一瞬间的事。哈希表运算得非常快，在电脑程式中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器)哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。哈希表也有一些缺点它是基于数组的，数组创建后难于扩展某些哈希表被基本填满时，性能下降得非常严重，所以程式虽必须要清楚表中将要存储多少数据（或者準备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。而且，也没有一种简便的方法可以以任何一种顺序〔例如从小到大〕遍历表中数据项。如果需要这种能力，就只能选择其他数据结构。然而如果不需要有序遍历数据，并且可以提前预测数据量的大小。那幺哈希表在速度和易用性方面是无与伦比的。概念及作用一般的线性表，树中，记录在结构中的相对位置是随机的，即和记录的关键字之间不存在确定的关係，因此，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上，查找的效率依赖于查找过程中所进行的比较次数。理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关係f，使每个关键字和结构中一个唯一的存储位置相对应。哈希表最常见的例子是以学生学号为关键字的成绩表，1号学生的记录位置在第一条，10号学生的记录位置在第10条...如果我们以学生姓名为关键字，如何建立查找表，使得根据姓名可以直接找到相应记录呢？用上述得到的数值作为对应记录在表中的位置，得到下表：上面这张表即哈希表。如果将来要查李秋梅的成绩，可以用上述方法求出该记录所在位置：李秋梅:lqm 12+17+13=42 取表中第42条记录即可。问题：如果两个同学分别叫刘丽刘兰该如何处理这两条记录？这个问题是哈希表不可避免的，即冲突现象：对不同的关键字可能得到同一哈希地址。构造方法1、直接定址法例如：有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函式取关键字自身。但这种方法效率不高,时间複杂度是O(1),空间複杂度是O(n),n是关键字的个数2、数字分析法有学生的生日数据如下：年.月.日75.10.0375.11.2376.03.0276.07.1275.04.2176.02.15...经分析,第一位，第二位，第三位重複的可能性大，取这三位造成冲突的机会增加，所以儘量不取前三位，取后三位比较好。3、平方取中法取关键字平方后的中间几位为哈希地址。4、摺叠法将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（捨去进位）作为哈希地址，这方法称为摺叠法。例如：每一种西文图书都有一个国际标準图书编号，它是一个10位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到10,000时，可採用此法构造一个四位数的哈希函式。如果一本书的编号为0-442-20586-4,则：5、除留余数法取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。H(key)=key MOD p (p处理冲突方法如果两个同学分别叫刘丽刘兰，当加入刘兰时，地址24发生了冲突，我们可以以某种规律使用其它的存储位置，如果选择的一个其它位置仍有冲突，则再选下一个，直到找到没有冲突的位置。选择其它位置的方法有：1、开放定址法Hi=(H(key)+di) MOD m i=1,2,...,k(k查找C代码//开放定址哈希表的存储结构int hashsize[]={997,...};typedef struct{elemtype*elem ;int count ;int sizeindex ;}HashTable ;#define SUCCESS 1#define UNSUCCESS 0#define DUPLICATE-1Status SearchHash(HashTable H,KeyTypeK,int&p,int&c){p=Hash(K);while(H.elem.key!=NULLKEY&&!EQ(K,H.elem.key))collision(p,++c);if(EQ(K,H.elem.key)return SUCCESS ;else return UNSUCCESS ;}Status InsertHash(HashTable&H,EleType e){c=0 ;if(SearchHash(H,e.key,p,c))return DUPLICATE ;else if(c{H.elem =e ;++H.count ;return OK ;}else RecreateHashTable(H);}