当前位置:首页 > 嵌入式培训 > 嵌入式学习 > 讲师博文 > 数据结构哈希表怎么设计及实现

数据结构哈希表怎么设计及实现 时间:2018-01-26      来源:未知

数据结构一直都是软件工程师必备技能之一,也是难点之一。数据结构其实是数据存储结构,它采用不同的存储方式和逻辑思路,实现各种数据和数据之间的关联,并且加上对应的算法,来解决问题。哈希表(散列表)是数据结构中一种散列存储方式,优点在于关键值key可以通过指定的算法直接得到数据的存储位置hash(key),这样一来不需要轮询,时间复杂度大大的降低。从而,哈希表满足了对数据操作高效率的要求。但是,哈希表也不是全能的,它的使用有一定的局限性。下面我们来介绍一下哈希表的设计和实现。

哈希表的设计

哈希表主要是确认关键值key和关键值存储位置hash(key)之间的具体关联算法。并且保证少的哈希冲突(多个不同数据通过算法得到存储位置相同,这时就是哈希冲突)产生。常见的哈希表的设置方法如下:

(1)直接定址法:直接的构造哈希表的方法,存储位置是通过线性函数得到的:

hash(key) = a * key + b {a、b为常数}

特点:这样得到的 hash(key) 和 key之间一一对应,一般不会产生冲突;

空间:这的哈希表要求地址空间大小与key集合大小相同;

应用:一般用于有序的key集合,例如各种编号。

(2)数字分析法: 分析已有数据的特点,选择尽量冲突少的数字来构造哈希表。

特点:数据是多位组成,数据和数据之间有相同的也有不同的,根据数据中每位的分布特点,选取若干位作为哈希表地址。

空间:根据选择的位的个数而定;

应用:数据位数多,且都相似, 例如生日,日期等等。

(3)除留余数法:n个数据,选取一个接近于n的质数p,这时哈希地址公式:

hash(key) = key % p 除法后得到的余数就是数据存储位置

特点:余数的取值范围 0 到 p-1 内,这样存储数据空间大小是固定的 p 个;

空间:p个存储空间;

应用: 数据值较大,数据个数较少。

(4)乘余取整法:先让关键值key乘上一个常数A(0 <1),提取乘积的小数部分。然后再用整数n乘以这个值,对结果向下取整,这个结果就是存储位置。<>

公式:hash(key) = (int)((((float)key*A) - (int)(key*A))*n)

应用:数据是小数,并且相差很少。

(5)平方取中法:一般哈希地址位置数据2的某次幂,例如:哈希地址总数为 m = 2^r。哈希地址hash(key) = 2^key 值中间的r位。

(6)折叠法:数据信息很长,可以将数据从左到有分成几个部分,每部分位数应与hash(key)存储位置的位数相同,将每部分都叠加求和,这个和就是hash(key)存储位置。

应用:例如:图书馆中图书的标准编号。

(7)随机数法:获取一个随机数,作为存储位置,公式:hash(key) = random(key);

应用:key关键字长度不等时使用。

哈希表的实现

这里我们以第三种方式除留余数法举例。

例子:已知存在以下数据 : 23 , 26 , 29 ,30,34 ,40

利用哈希表存储上面数据,并写出查找方法。

第一步:确认hash(key)和key之间的关联公式

数据有6个,先选取一个质数p = 7 或 11或 13

为尽量减少哈希冲突,当选择p=7时:余数2 5 1 2 6 5有冲突

当选择p=11时:余数1 4 7 8 1 6有冲突

当选择p=13时:余数10 0 3 4 8 1无冲突

所以公式:hash(key) = key % 13;

实现代码:
#include<stdio.h>
typedef int data_t;
#define M 13
int emptyHash(data_t *p)  // 判断哈希地址中是否空闲
{
         return *p == 0 ? 1:0;
}
int setHash(data_t *hp,data_t key)
{
         int i = key % M;
         if(emptyHash(&hp[i]))      // 判读指定位置是否空闲
                   hp[i] = key;                  // 存储到哈希表中
         else 
return 0;       // 失败
         return 1;           // 成功
}
int getHash(data_t *hp,data_t key)
{
         int i = key % M;
         if(hp[i] != key)    
         {
                   printf("数据没有存储到哈希表中\n");
                   return 0;
         }
         else
                   printf("数据在哈希表中,位置%d --> %d\n",i, hp[i]);
         return 1;
}
int main()
{
         data_t hash[13] = {0};          // 定义一个哈希表(数组)存储数据空间
         setHash(hash,23);
         setHash(hash,26);
         setHash(hash,29);           // 哈希表中存入数据
         setHash(hash,30);
         setHash(hash,34);
         setHash(hash,40);
         getHash(hash,34);           // 查找哈希表
         getHash(hash,32);                    
         return 0;
}

上一篇:嵌入式系统移植步骤

下一篇:嵌入式linux启动过程分析

热点文章推荐
华清学员就业榜单
高薪学员经验分享
热点新闻推荐
前台专线:010-82525158 企业培训洽谈专线:010-82525379 院校合作洽谈专线:010-82525379 Copyright © 2004-2022 北京华清远见科技集团有限公司 版权所有 ,京ICP备16055225号-5京公海网安备11010802025203号

回到顶部