查找-之散列表/哈希表

本文涉及的产品
函数计算FC,每月15万CU 3个月
简介: 前面的查找不可避免的要进行比较,是否能直接通过关键字key得到要查找的元素位置?

问题:

前面的查找不可避免的要进行比较,是否能直接通过关键字key得到要查找的元素位置?

解决方法:

散列技术

通过记录的存储位置和关键字建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f(key)

f为散列函数/哈希函数

散列表/哈希表(Hash table)--采用散列技术实现数据存储的一块连续的存储空间


散列过程:

1)存储时,散列函数计算数据的散列地址,并按照该散列地址存储该数据

2)查找时,散列函数计算数据的散列地址,按照散列地址访问该记录。


散列适用于:查找

散列技术不适用的情况:

1)同样的关键字,对应很多记录的

2)范围查找

散列函数的设计要素:

计算简单:关键字不会冲突,不超过其它查找技术与关键字的比较时间

散列地址分布均匀


算法时间复杂度:O(1)

散列函数的构造:

1)直接定址法

f(key)=a*key+b (a,b为常数)

特点:简单、均匀不会产生冲突

         需要事先知道关键字key的分布情况

适用:查找表较小且连续的情况,现实中不常用

2)数字分析法

抽取关键字的一部分计算散列地址

适用:关键字位数较大情况,事情知道关键字分布、且关键字的若干位分布较均匀

3)平方取中法

先平方再取中间的位数

适用:不知道关键字分布、位数不是很大的情况

4)折叠法

关键字从左到右分割成位数相等的几部分,然后几部分叠加求和、按照散列表表长取后几位作为散列地址

适用:关键字分布未知、关键字位数较多的情况

5)除留余数法


    f(key)=key mod p(p<=m)

p选择不好会产生同义词

p的选择:若散列表表长为m,则p<=m的最小质数或不包含小于20质因子的合数

6)随机数法

选择一个随机数,取关键字key的随机函数值作为它的散列地址

     f(key)=random(key)

适用:关键字的长度不等情况

散列冲突的处理方法:

关键字key1!=key2 但有散列地址f(key1)=f(key2)


1)开放定址法

线性探测法:


一旦发生冲突、寻找下一个空的散列地址(散列表足够大,空散列地址总可以找到)


fi(key)=(f(key)+di)mod m (di=1,2,3.....,m-1)


不是同义词却争夺一个地址--堆积


二次探测法:(双向寻找)


增加平方运算的目的是不让关键字集聚在某一块区域


fi(key)=(f(key)+di)mod m (di=1^2 ,-1^2 ,2^2 ,-2^2 ,.....,q^2,-q^2, q<m/2)


随机探测法:


   冲突时,对于位移量di采用随机函数计算得到


fi(key)=(f(key)+di)mod m (di为随机数列)

2)再散列函数法

准备多个散列函数--当前散列函数发生冲突则换另一个

fi(key)=RHi(key)(i=1,2,3,.....,k)

RHi为不同的散列函数

3)链地址法

将所有关键字为同义词的记录存储在一个单链表中

发生冲突时,在当前位置给单链表增加结点

8a1ce2581fd6e14e3a20a1ac3152ffa9_20200204215212547.png

 示意图

查找时需要遍历单链表的性能损耗

4)公共溢出区法

分为基本表和溢出表,发生冲突的存放在溢出表中

基于除留余数法+开放定址法的散列表实现:

1)散列表结构定义

2)初始化散列表

3)散列函数计算(采用除留余数法)

4)插入关键字进散列表(散列冲突的处理采用开放定址法)

5)散列表查找关键字(散列冲突的处理采用开放定址法)

#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12
#define NULLKEY -32768
//散列表结构定义
typedef struct
{
    int *elem;//数据元素存储基址,动态分配数组
    int count;//当前数据元素个数
}HashTable;
int m=0;//散列表长  
//初始化散列表  
Status InitHashTable(HashTable *H)
{   
int i; 
m=HASHSIZE;  
H->count=m;
H->elem=(int*)malloc(m*sizeof(int));
for(i=0;i<m;i++)   
      H->elem[i]=NULLKEY;
return OK; 
}
//散列函数
int Hash(int key)
{
   return key%m;//除留余数法
}
// 插入关键字进散列表
void InsertHash(HashTable *H,int key)
{
  int addr=Hash(key);//求散列地址
  while(H->elem[addr]!=NULLKEY)//如果不为空,则冲突
           addr=(addr+1)%m;// 开放地址法线性探测
 H->elem[addr]=key;//有空位后插入关键字
}
//散列表查找关键字
Status SearchHash(HashTable H,int key,int *addr)
{
    *addr=Hash(key);
    while(H.elem[*addr]!=key)//判断hash地址对应的值是否和关键字key相等
    {
         *addr=(*addr+1)%m;//开放地址线性探测
         if(H.elem[*addr]==NULLKEY || *addr==Hash(key))
              {
                   return UNSUCCESS;
              }
    }
    return SUCCESS;
}


相关实践学习
【文生图】一键部署Stable Diffusion基于函数计算
本实验教你如何在函数计算FC上从零开始部署Stable Diffusion来进行AI绘画创作,开启AIGC盲盒。函数计算提供一定的免费额度供用户使用。本实验答疑钉钉群:29290019867
建立 Serverless 思维
本课程包括: Serverless 应用引擎的概念, 为开发者带来的实际价值, 以及让您了解常见的 Serverless 架构模式
目录
相关文章
|
23天前
|
存储 缓存 数据库
哈希表
【10月更文挑战第24天】哈希表是一种非常实用的数据结构,它在各种计算机应用中发挥着重要作用。通过深入了解哈希表的原理、实现和应用,我们可以更好地利用它来解决实际问题。
|
5月前
|
存储
闭散列哈希表
闭散列哈希表
|
存储 算法 Serverless
|
存储 算法 Shell
哈希表、哈希桶(C++实现)【STL】
哈希表、哈希桶(C++实现)【STL】
165 0
|
6月前
|
存储 Serverless
哈希及哈希表的实现
哈希及哈希表的实现
60 0
查找-散列表(哈希表)详解篇
查找-散列表(哈希表)详解篇
|
存储 算法 Java
哈希表(散列表)详解
什么是哈希表,以及如何使用哈希表
|
存储 算法 JavaScript
关于散列表(哈希表)我所知道的
关于散列表(哈希表)我所知道的
63 0
|
存储 Java Serverless
哈希表以及哈希冲突
哈希表以及哈希冲突
139 0
哈希表以及哈希冲突
|
存储 算法 C++
C++:哈希:闭散列哈希表
讲解了哈希的概念以及哈希函数,简单实现了闭散列哈希。闭散列哈希的重点之一是取模操作。
C++:哈希:闭散列哈希表