考研网 发表于 2018-12-14 19:17:04

2019考研计算机数据结构复习重点:哈希表

《数据结构(C语言版)》复习重点在二、三、六、七、九、十章,考试内容两大类:概念,算法,自从计算机专业课统考以后,专业课考试题型分为2类,一类选择题,一类综合应用题。接下来是新东方在线整理的2019考研计算机数据结构复习重点哈希表。
      哈希表
    1、 构造方法:
    a) 直接定址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key +
b,其中a和b为常数(这种散列函数叫做自身函数)。若其中H(key)中已经有值了,就往下一个找,直到H(key)中没有值了,就放进去。
    b)
数字分析法:分析一组数据,比如一组员工的出生年月日,这时我们发现出生年月日的前几位数字大体相同,这样的话,出现冲突的几率就会很大,但是我们发现年月日的后几位表示月份和具体日期的数字差别很大,如果用后面的数字来构成散列地址,则冲突的几率会明显降低。因此数字分析法就是找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址。
    c)
平方取中法:当无法确定关键字中哪几位分布较均匀时,可以先求出关键字的平方值,然后按需要取平方值的中间几位作为哈希地址。这是因为:平方后中间几位和关键字中每一位都相关,故不同关键字会以较高的概率产生不同的哈希地址。
    d)
折叠法:将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(去除进位)作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐,然后相加;间界叠加是从一端向另一端沿分割界来回折叠,然后对齐相加。
    e) 除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD
p,p<=m。不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要,一般取素数或m,若p选的不好,容易产生同义词。
    2、 处理冲突方法:
    a) 开放定址法:Hi=(H(key) + di) MOD
m,i=1,2,…,k(k<=m-1),其中H(key)为散列函数,m为散列表长,di为增量序列,可有下列三种取法:
    1.1. di=1,2,3,…,m-1,称线性探测再散列;
    1.2. di=1^2,-1^2,2^2,-2^2,3^2,…,±k^2,(k<=m/2)称二次探测再散列;
    1.3. di=伪随机数序列,称伪随机探测再散列。
    b) 再哈希法:Hi=RHi(key),i=1,2,…,k
RHi均是不同的散列函数,即在同义词产生地址冲突时计算另一个散列函数地址,直到冲突不再发生,这种方法不易产生“聚集”,但增加了计算时间。
    c)
链地址法(拉链法):将所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函数产生的哈希地址在区间上,则设立一个指针型向量Chain
ChainHash;其每个分量的初始状态都是空指针。凡哈希地址为i的记录都插入到头指针为ChainHash的链表中。在链表中的插入位置可以在表头或表尾;也可以在中间,以保持同义词在同一线性链表中按关键字有序。
    d)
建立一个公共溢出区:假设哈希函数的值域为,则设向量HashTable为基本表,每个分量存放一个记录,另设立向量OverTable为溢出表。所有关键字和基本表中关键字为同义词的记录,不管它们有哈希函数得到的哈希地址是什么,一旦发生冲突,都填入溢出表。
页: [1]
查看完整版本: 2019考研计算机数据结构复习重点:哈希表