计算机哈希算法(求哈希表)

不知不觉，2020年已经过去近三个月了。在家学习的同时，别忘了复习2021年考研！小编给大家带来2021计算机考研复习：哈希表，一起来看看吧。

哈希表

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是哈希值table long，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) 链地址法（拉链法）：将所有关键字为同义词的记录存储在同一个线性链表中。假设某个哈希函数生成的哈希地址在区间[0,m-1]内，则建立一个指针向量Chain ChainHash[m]；每个组件的初始状态都是空指针。所有哈希地址为i的记录都被插入到链表中，头指针为ChainHash[i]。链表中的插入位置可以是链表的头部或尾部；它也可以位于中间，以将按关键字排序的同义词保留在同一个线性链表中。

d) 建立公共溢出区：假设哈希函数的取值范围为[0,m-1]，则设置向量HashTable[0.m-1]为基本表，每个组件存储一条记录，并设置另一个向量OverTable[0.v]为溢出表。所有关键字与基本表关键字同义的记录，无论哈希函数得到的哈希地址是多少，一旦发生冲突，都会被填充到溢出表中。

以上是2021年计算机考研复习：哈希表。更多2021计算机考研复习知识点将持续更新。

相关建议

【直播】文都2021年考研振兴计划（双优通关班）

  相关文章:

  第1篇    减法的四种算法(减法的四个运算定律)    作者：admin

   8月底，考研大纲即将公布。预注册将于9月进行，正式注册将于10月进行。考研初试离我们越来越近了。朋友们早出晚归，努力复习、收集各种材料。很多人的状态可以用“忙、累、慌、乱”来形容。是不是意味着复习越努力、收集的信息越多，考研成功的概率就越大呢？并非如此。考研，你要学

  第2篇    mpa管理类联考考什么(管理类mpa联考过国家线难吗)    作者：admin

   1.学校声誉虽然MPA的学习内容与各学校的基础课程非常相似，但附加课程却明显不同，具有很强的特色。课程的设置和重点与各学校的专业特长和教学领域有很大关系。例如，对外经济贸易学校有以海关为主的课程，农业院校有以农业或扶贫为主的课程等。考生在选择时应根据自己的喜好考虑学校的声

  第3篇    考研政治真题试卷pdf(考研政治真题试卷2022)    作者：admin

   摘要本文主要从五个角度论证研究生政考试卷的重要性和必要性。首先，研究生政治考试试卷是研究生政治考试的重要组成部分。掌握真题真题可以帮助你更好的应对考试。其次，通过分析真题，可以了解考研政治的考点和命题思路，有助于提高备考效果。第三，通过分析真题，可

  第4篇    云南大学2021年硕士研究生拟录取(2020年云南大学研究生)    作者：admin

   云南大学研究生2023录取摘要云南大学是云南省重点大学之一，以优良的学风和丰富的研究资源而闻名。随着时间的流逝，云南大学2023年研究生招生即将拉开帷幕。本文将从五个角度论证并详细介绍云南大学2023年研究生招生的重要性以及招生政策的变化。1.录取政策的变化云南大学的研究生招生政策将随着时间的推移进行调整，以更好地适应当今社会的需求。2023年招生

  第5篇    南京大学的新闻传播研究生好考吗(南京大学新闻传播专业考研)    作者：admin

   南京大学新闻传播硕士考研经验摘要本文旨在分享我作为南京大学新闻与传播专业研究生的经历。我将从多个角度来论证这一点，包括准备计划、复习方法和技巧、面试准备、学术研究和准备阶段的实践经验。本文总结了我在考研期间所学到的知识，希望对即将考