精华内容
下载资源
问答
  • 【数据结构实验五】- 散列查找
    2022-02-25 18:58:52

    实验五


    一、实验题目:

    散列查找

    二、实验目的:

    ⑴ 掌握散列查找的基本思想;
    ⑵ 掌握闭散列表的构造方法;
    ⑶ 掌握线性探测处理冲突的方法;
    ⑷ 验证散列技术的查找性能。

    三、实验内容:

    ⑴ 对于给定的一组整数和散列函数,采用线性探测法处理冲突构造散列表;
    ⑵ 设计查找算法,验证查找性能。

    实现提示

    首先将待查找集合存储到闭散列表ht中,然后随机生成待查元素的下标,考查在查找成功情况下的比较次数。

    1.散列查找

    程序代码:
    #include <stdlib.h>
    #include <iostream>
    using namespace std;
    struct hashNode
    {
        int data;
        bool used;
    };
    
    void InithashTable(hashNode table[],int size)
    {
        int key,j,i;
        int count=0;
    
       	cout<<"Please input key value.\n";
      	cin>>key;
       	count++;
       	int p=5;
       	while(key!='#'&&count<=size){
       	j=key%p;
      
      
       	while(table[j].used==1&&table[j].data!=0)
       		j=(j+1)%size;
        	if(table[j].used==0) 
    		{
       			table[j].data=key;
       			if(table[j].data!=0)
       			table[j].used=1;
       		}
    	   cin>>key;
    	   count++;
    	   }
    }
    
    int HashSearch(hashNode table[],int size,int key)
    {
    	int j=key%5;
    	int count=0;
    	int i;
    	i=j;
    	while(table[i].data!=0)
    	{
    		if(++count&&table[i].data==key)
    		{
    			cout<<"查找成功,比较次数为:"<<count<<endl;
    			return i;
    		}
    		i=(i+1)%size;
    		if(i==j) break;
    	}
    	cout<<"查找失败";
    }
    
    void dispHashTable(hashNode table[],int size)
    {
    	for(int i=0;i<size;i++)
        {
            if(table[i].used==1)
    		{
            	cout<<"下标:"<<i<<"散列值:";
            	cout<<table[i].data<<"\n";
    		}
        }
    }
    
    int main()
    {
    	int size;
    	cout<<"Please input size.\n";
        cin>>size;
        hashNode table[size];
        int i;
        for(i=0;i<size;i++)
        {
            table[i].data=0;
            table[i].used=0;
        }
    	InithashTable(table,size);
    	dispHashTable(table,size);
        int location=HashSearch(table,size,15);
        cout<<"查找位置为:"<<location;
    }
    
    程序运行结果截图:

    在这里插入图片描述

    四、实验心得体会

    通过本次实验我掌握了散列查找的基本思想;掌握了闭散列表的构造方法;掌握了线性探测处理冲突的方法;验证了散列技术的查找性能。
    在这个过程中我的程序技能更加完善。

    更多相关内容
  • 散列查找

    2021-06-05 09:42:45
    散列函数:一个把查找表中的关键字映射成该关键字对应的地址的函数,记为Hash(key)=Addr(这里的地址可以是数组下标、索引或内存地址等)。 散列函数可能会把两个或两个以上的不同关键字映射到同一地址,称这种情况为...

    散列表(Hash Table)

    散列表:根据关键字而直接进行访问的数据结构。也就是说,散列表建立了关键字和存储地址之间的一种直接映射关系。
    在这里插入图片描述
    理想情况下,对散列表进行查找的时间复杂度为O(1),即与表中元素的个数无关。

    处理冲突的方法——拉链法

    对于不同的关键字可能会通过散列函数映射到同一地址,为了避免非同义词发生冲突,可以把所有的同义词存储在一个线性链表中,这个线性链表由其散列地址唯一标识。
    在这里插入图片描述
    假设散列地址为i的同义词链表的头指针存放在散列表的第i个单元中,因而查找、插入和删除操作主要在同义词链中进行。

    拉链法的小优化

    拉链法适用于经常进行插入和删除的情况。
    在这里插入图片描述

    散列查找

    散列表的查找过程与构造散列表的过程基本一致。对于一个给定的关键字key,根据散列函数可以计算出其散列址,执行步骤如下:
    在这里插入图片描述
    在这里插入图片描述
    初始化: Addr=Hash(key)
    在这里插入图片描述
    ① 检测查找表中地址为Addr的位置上是否有记录,若无记录,返回查找失败;若有记录,比较它与key的值,若相等,则返回查找成功标志,否则执行步骤②。
    在这里插入图片描述
    ② 用给定的处理冲突方法计算“下一个散列地址”,并把Addr置为此地址,转入步骤①。
    在这里插入图片描述
    装填因子。散列表的装填因子一般记为a,定义为一个表的装满程度,即 α = 表 中 记 录 数 n 散 列 表 长 度 m \alpha={表中记录数n\over 散列表长度m} α=mn
    在这里插入图片描述
    散列表的平均查找长度依赖于散列表的填装因子a,而不直接依赖于n或m。直观地看,a越大,表示装填的记录越“满”,发生冲突的可能性越大,反之发生冲突的可能性越小。
    在这里插入图片描述
    在不同的情况下,不同的散列函数会发挥不同的性能,因此不能笼统地说哪种散列函数最好。在实际选择中,采用何种构造散列函数的方法取决于关键字集合的情况,但目标是为了尽量降低产生冲突的可能性。

    散列函数

    散列函数:一个把查找表中的关键字映射成该关键字对应的地址的函数,记为Hash(key)=Addr(这里的地址可以是数组下标、索引或内存地址等)。

    散列函数可能会把两个或两个以上的不同关键字映射到同一地址,称这种情况为冲突,这些发生碰撞的不同关键字称为同义词。一方面,设计得好的散列函数应尽量减少这样的冲突;另一方面,由于这样的冲突总是不可避免的,所以还要设计好处理冲突的方法。

    散列函数的构造方法

    1)散列函数的定义域必须包含全部需要存储的关键字,而值域的范围则依赖于散列表的大小或地址范围。

    2)散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中,从而减少冲突的发生。

    3)散列函数应尽量简单,能够在较短的时间内计算出任一关键字对应的散列地址。

    常见的散列函数

    1)除留余数法
    在这里插入图片描述
    这是一种最简单、最常用的方法,假定散列表表长为m,取一个不大于m但最接近或等于m的质数p,利用以下公式把关键字转换成散列地址。散列函数为:H(key) = key%p
    在这里插入图片描述
    除留余数法的关键是选好p,使得每个关键字通过该函数转换后等概率地映射到散列空间上的任一地址,从而尽可能减少冲突的可能性。
    在这里插入图片描述
    2)直接定址法
    直接取关键字的某个线性函数值为散列地址,散列函数为:H(key)= a*key+ b。a和b是常数。
    在这里插入图片描述
    这种方法计算最简单,且不会产生冲突。它适合关键字的分布基本连续的情况,若关键字分布不连续,空位较多,则会造成存储空间的浪费。

    3)数字分析法
    设关键字是r进制数(如十进制数),而r个数码在各位上出现的频率不一定相同,可能在某些位上分布均匀一些,每种数码出现的机会均等;而在某些位上分布不均匀,只有某几种数码经常出现,此时应选取数码分布较为均匀的若干位作为散列地址。
    在这里插入图片描述
    这种方法适合于已知的关键字集合,若更换了关键字,则需要重新构造新的散列函数。

    4)平方取中法
    取关键字的平方值的中间几位作为散列地址。具体取多少位要视实际情况而定。
    在这里插入图片描述
    这种方法得到的散列地址与关键字的每位都有关系,因此使得散列地址分布比较均匀,适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。
    在这里插入图片描述
    5)折叠法
    将关键字分割成位数相同的几部分(最后一部分的位数可以短一些),然后取这几部分的叠加和作为散列地址,这种方法称为折叠法。关键字位数很多,而且关键字中的每位上数字分布大致均匀时,可以采用折叠法得到散列地址。

    处理冲突的方法——开放定址法

    开放定址法,是指可存放新表项的空闲地址既向它的同义词表项开放,又向它的非同义词表项开放。其数学递推公式为:HI= (H(key)+dI)% m。i=0,1,2,…k (k≤m-1);m表示散列表表长;di为增量序列。
    在这里插入图片描述
    1)线性探测法。当di=0,1,2,…,m-1时,称为线性探测法。
    在这里插入图片描述
    这种方法的特点是:冲突发生时,顺序查看表中下一个单元(探测到表尾地址m-1时,下一个探测地址是表首地址0),直到找出一个空闲单元 (当表未填满时定能找到一 个空闲单元)或查遍全表。
    在这里插入图片描述
    线性探测法可能使第i个散列地址的同义词存入第i+1个散列地址,这样本应存入第i+1个散列地址的元素就争夺第i+2个散列地址的元索的地址…从而造成大量元素在相邻的散列地址上“聚集”(或堆积)起来,大大降低了查找效率。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    查找操作

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    删除操作

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    2)平方探测法。当di=02, 12, -12, 22, -22,…,k2, -k2时,称为平方探测法,其中k≤m/2,散列表长度m必须是一个可以表示成 4k+3的素数,又称二次探测法。
    在这里插入图片描述
    平方探测法是一种较好的处理冲突的方法,可以避免出现“堆积”问题,它的缺点是不能探测到散列表上的所有单元,但至少能探测到一半单元。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    4)伪随机序列法。当di = 伪随机数序列时,称为伪随机序列法。
    在这里插入图片描述
    在这里插入图片描述
    注意:在开放定址的情形下,不能随便物理删除表中的已有元素,因为若删除元素,则会截断其他具有相同散列地址的元素的查找地址。因此,要删除一个元素时, 可给它做一个删除标记,进行逻辑删除。但这样做的副作用是:执行多次删除后,表面上看起来散列表很满,实际上有许多位置未利用,因此需要定期维护散列表,要把删除标记的元素物理删除。
    在这里插入图片描述

    处理冲突的方法——再散列法

    再散列法。当di= Hash2(key)时,称为再散列法,又称双散列法。需要使用两个散列函数, 当通过第个散列函数H(key)得到的地址发生冲突时,则利用第二个散列函 数Hash2(key)计算该关键字的地址增量。
    在这里插入图片描述
    它的具体散列函数形式如下:
    Hi= (H(key) + I*Hash2(key))%m
    初始探测位置H0= H(key)%m。i 是冲突的次数,初始为0。在散列法中,最多经过m-1次探测就会遍历表中所有位置,回到H0位置。

    查找效率分析(ASL)

    散列表的查找效率取决于三个因素:散列函数、处理冲突的方法和装填因子。
    在这里插入图片描述
    虽然散列表在关键字与记录的存储位置之间建立了直接映像,但由于“冲突”的产生,使得散列表的查找过程仍然是一个给定值和关键字进行比较的过程。
    在这里插入图片描述
    因此,仍需要以平均查找长度作为衡量散列表的查找效率的度量。
    在这里插入图片描述
    读者应能在给出散列表的长度、元素个数及散列函数和解决冲突的方法后,在求出散列表的基础上计算出查找成功时的平均查找长度和查找不成功的平均查找长度。
    在这里插入图片描述

    展开全文
  • 散列查找算法_哈希表

    2019-12-08 11:11:01
    编写程序实现对给定数组序列进行散列表的建立,并在建立散列表的基础上进行查找,并返回查找成功与否. 首先定义一个固定长度的列表data,以及一个比列表长度大的哈希表,并初始化为0. 程序先调用自己写的Create函数...
  • 散列查找的实现

    2021-12-29 23:48:08
    散列函数:将关键码映射为散列表中适当存储位置 时间复杂度:O(1) 装填因子 处理冲突的办法:开放定址法,拉链法

    散列函数:将关键码映射为散列表中适当存储位置

    int Hash(const char *Key, int TableSize) //字符串关键字的散列函数构造——移位法
    {
        unsigned int H = 0; //散列函数值初始化为0
        while(*Key!='\0') //位移映射
            H = (H<<5) + *Key++;
        return (H % TableSize);
    }

    散列查找的时间复杂度:O(1),与表的长度无关

    只能用于对关键字的随机查找

    装填因子\alpha = 表中元素个数/ 散列表空间大小,常取0.5~0.8

    平均查找长度ASL:是关于\alpha的函数

    处理冲突的办法:开放定址法,分离链接法


    开放定址法

    -当冲突发生时,形成一个探查序列,沿此序列逐个探查,直到找到空的地址

    -线性探测、二次探测、伪随机探测

    数据存储

    typedef int ElementType;
    typedef int Index; //散列地址勒烯
    typedef Index Position; //数据所在位置和散列地址是同一类型
    typedef enum { //散列单元状态类型
        Legitimate, //合法元素
        Empty, //空单元
        Deleted //已删除元素
    }EntryType;
    typedef struct HashEntry Cell; //散列表单元类型
    struct HashEntry {
        ElementType Data; //存放元素
        EntryType Info; //单元状态
    };
    typedef struct TblNode *HashTable; //散列表类型
    struct TblNode { //散列表结点定义
        int TableSize; //表的最大长度
        Cell *Cells; //存放散列单元数据的数组
    };
    

    散列表的创建

    int NextPrime(int N) //返回大于N且不超过MAXTABLESIZE的最小素数,用作散列表的空间大小
    {
        int i,p;
        p = (N%2)?N+2:N+1; //从大于N的下一个奇数开始
        while(p <= MAXTABLESIZE) {
            for(i = (int)sqrt(p); i>2; i--)
                if (!(p%i))
                    break; //p不是素数
            if(i==2)
                break; //for循环正常结束,说明p是素数
            else p += 2; //否则试探下一个奇数
        }
        return p;
    }
    
    HashTable CreateTable(int TableSize)
    {
        HashTable H;
        int i;
        H = (HashTable)malloc(sizeof(struct TblNode));
        H->TableSize = NextPrime(TableSize); //保证散列表最大长度是素数
        H->Cells = (Cell*)malloc(H->TableSize*sizeof(Cell)); //声明单元数组
        for (i = 0; i<H->TableSize; i++) //初始化单元状态为空单元
            H->Cells[i].Info = Empty;
        return H;
    }
    

    散列表的查找——平方探测法

    Position Find(HashTable H, ElementType Key)
    {
        Position CurrentPos, NewPos;
        int CNum = 0; //记录冲突次数
        NewPos = Hash(Key, H->TableSize); //散列初始位置
        CurrentPos = NewPos;
        while(H->Cells[NewPos].Info!=Empty && H->Cells[NewPos].Data!=Key) {
            //当该位置的单元非空,并且不是要找的元素时,发生冲突
            //统计一次冲突,并判断奇偶次
            if(++CNum % 2) { //奇数次冲突
                NewPos = CurrentPos + (CNum+1)*(CNum+1)/4;
                if(NewPos >= H->TableSize)
                    NewPos = NewPos % H->TableSize; //调整为合法位置
            }
            else { //偶数次冲突
                NewPos = CurrentPos - CNum*CNum/4;
                while(NewPos<0)
                    NewPos += H->TableSize; //调整为合法位置
            }
        }
        return NewPos; //Key的位置或者是一个空单元的位置
    }

    散列表的插入

    bool Insert(HashTable H, ElementType Key) //插入关键字Key
    {
        Position Pos = Find(H, Key); //检查Key是否已存在
        if(H->Cells[Pos].Info!=Legitimate) { //如果这个单元没有被占,说明Key可以插入在此
            H->Cells[Pos].Info = Legitimate; //将此单元状态改为被占用
            H->Cells[Pos].Data = Key; //存入关键字
            return true;
        }
        else {
            printf("键值已存在");
            return false;
        }
    }

    散列表的删除

    bool Delete(HashTable H, ElementType Key) //删除关键字Key
    {
        Position CurrentPos, NewPos;
        int CNum = 0; //记录冲突次数
        NewPos = Hash(Key, H->TableSize); //散列初始位置
        CurrentPos = NewPos;
        while(H->Cells[NewPos].Info!=Empty && H->Cells[NewPos].Data!=Key) {
            //当该位置的单元非空,并且不是要找的元素时,发生冲突
            //统计一次冲突,并判断奇偶次
            if(++CNum % 2) { //奇数次冲突
                NewPos = CurrentPos + (CNum+1)*(CNum+1)/4;
                if(NewPos >= H->TableSize)
                    NewPos = NewPos % H->TableSize; //调整为合法位置
            }
            else { //偶数次冲突
                NewPos = CurrentPos - CNum*CNum/4;
                while(NewPos<0)
                    NewPos += H->TableSize; //调整为合法位置
            }
        }
        if(H->Cells[NewPos].Data == Key) { //找到该关键字则删除
            H->Cells[NewPos].Info = Deleted //修改位置信息为被删除
            return true;
        }
        else { //没找到关键字
            print("该关键字不存在,输入错误\n")
            return false; //返回错误
        }
    }

    分离链接法

    将所有关键字为同义词的记录存储在一个单链表中,用一维数组存储头指针

    数据结构定义

    - 表头不存储数据

    typedef char ElementType[KEYLENGTH+1]; //#define KEYLENGTH 15 关键字字符串的最大长度
    typedef int Index; //散列地址类型
    //单链表结点的定义
    typedef struct LNode *PtrToLNode;
    struct LNode {
        ElementType Data;
        PtrToLNode Next;
    };
    typedef PtrToLNode Position;
    typedef PtrToLNode List;
    
    typedef struct TblNode *HashTable; //散列表类型
    struct TblNode { //散列表结点定义
        int TableSize; //表的最大长度
        List Heads; //指向链表头结点的数组
    };
    HashTable H; //表头不存储数据

    散列表的结构如下图所示 

     初始化散列表

    int NextPrime(int N) //返回大于N且不超过MAXTABLESIZE的最小素数
    {
        int i,p;
        p = (N%2)?N+2:N+1; //从大于N的下一个奇数开始
        while(p <= KEYLENGTH) {
            for(i = (int)sqrt(p); i>2; i--)
                if (!(p%i))
                    break; //p不是素数
            if(i==2)
                break; //for循环正常结束,说明p是素数
            else p += 2; //否则试探下一个奇数
        }
        return p;
    }
    
    HashTable CreateTable(int TableSize)
    {
        HashTable H;
        int i;
        H = (HashTable)malloc(sizeof(struct TblNode)); //申请散列表头结点空间
        H->TableSize = NextPrime(TableSize); //保证散列表最大长度是素数
        H->Heads = (List)malloc(H->TableSize*sizeof(struct LNode)); //动态分配散列表头结点数组
        for (i = 0; i<H->TableSize; i++) { //初始化表头结点
            H->Heads[i].Data[0] = '\0';
            H->Heads[i].Next = NULL;
        }
        return H;
    }
    

    散列表的查找

    Position Find(HashTable H, ElementType Key)
    {
        Position P;
        Index Pos;
        Pos = Hash(Key, H->TableSize); //散列初始位置
        P = H->Heads[Pos].Next; //从该链表的第一个结点开始
        while(P && strcmp(P->Data, Key)) //字符串大小的比较,如果相同则结果为0
            P = P->Next;
        return P;
    }

    散列表的插入

    bool Insert(HashTable H, ElementType Key)
    {
        Position P, NewCell;
        Index Pos;
        P = Find(H, Key);
        if(!P) { //关键词未找到则可以插入
            NewCell = (Position)malloc(sizeof(struct LNode));
            strcpy(NewCell->Data, Key); //把字符串Key复制给NewCell->Data
            Pos = Hash(Key, H->TableSize); //初始散列位置
            //头插法:将NewCell插入为H->Heads[Pos]链表的第一个结点
            NewCell->Next = H->Heads[Pos].Next;
            H->Heads[Pos].Next = NewCell;
            return true;
        }
        else {
            printf("键值已存在");
            return false;
        }
    }

    散列表的删除

    bool Delete(HashTable H, ElementType Key)
    {
        Position TempCell;
        Index Pos;
        TempCell = Find(H, Key);
        if(TempCell) { //找到关键词则可以删除
            Pos = Hash(Key, H->TableSize); //初始散列位置
            H->Heads[Pos].Next = TempCell->Next;
            free(TempCell);
            return true;
        }
        else {
            printf("键值不存在\n");
            return false;
        }
    }

     

    展开全文
  • 散列查找 ——哈希查找

    万次阅读 2018-04-23 18:14:48
    散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f(key)。建立了关键字与存储位置的映射关系,公式如下: 存储位置 = f(关键字) 这里把这种对应关系f...
    1. 散列表相关概念

      散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f(key)。建立了关键字与存储位置的映射关系,公式如下:

                      存储位置 = f(关键字)
      

      这里把这种对应关系f称为散列函数,又称为哈希(Hash)函数。
      采用散列技术将记录存在在一块连续的存储空间中,这块连续存储空间称为散列表或哈希表。那么,关键字对应的记录存储位置称为散列地址。
        散列技术既是一种存储方法也是一种查找方法。散列技术的记录之间不存在什么逻辑关系,它只与关键字有关,因此,散列主要是面向查找的存储结构。

    2. 散列函数的构造方法

      2.1 直接定址法

      所谓直接定址法就是说,取关键字的某个线性函数值为散列地址,即
      这里写图片描述
      优点:简单、均匀,也不会产生冲突。
      缺点:需要事先知道关键字的分布情况,适合查找表较小且连续的情况。
      由于这样的限制,在现实应用中,此方法虽然简单,但却并不常用。

      2.2 数字分析法

      如果关键字时位数较多的数字,比如11位的手机号”130****1234”,其中前三位是接入号;中间四位是HLR识别号,表示用户号的归属地;后四为才是真正的用户号。如下图所示。
      这里写图片描述

      如果现在要存储某家公司的登记表,若用手机号作为关键字,极有可能前7位都是相同的,选择后四位成为散列地址就是不错的选择。若容易出现冲突,对抽取出来 的数字再进行反转、右环位移等。总的目的就是为了提供一个散列函数,能够合理地将关键字分配到散列表的各个位置。

      数字分析法通过适合处理关键字位数比较大的情况,如果事先知道关键字的分布且关键字的若干位分布比较均匀,就可以考虑用这个方法。

      2.3 平方取中法
      这个方法计算很简单,假设关键字是1234,那么它的平方就是1522756,再抽取中间的3位就是227,用做散列地址。
      平方取中法比较适合不知道关键字的分布,而位数又不是很大的情况。

      2.4 折叠法
      折叠法是将关键字从左到右分割成位数相等的几部分(注意最后一部分位数不够时可以短些),然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址。
      比如关键字是9876543210,散列表表长为三位,将它分为四组,987|654|321|0,然后将它们叠加求和987 + 654 + 321 + 0 = 1962,再求后3位得到散列地址962。
      折叠法事先不需要知道关键字的分布,适合关键字位数较多的情况。

      2.5 除留余数法
      此方法为最常用的构造散列函数方法。对于散列表长为m的散列函数公式为:
      这里写图片描述
      mod是取模(求余数)的意思。事实上,这方法不仅可以对关键字直接取模,也可以再折叠、平方取中后再取模。
      很显然,本方法的关键在于选择合适的p,p如果选不好,就可能会容易产生冲突。
      根据前辈们的经验,若散列表的表长为m,通常p为小于或等于表长(最好接近m)的最小质数或不包含小于20质因子的合数。

      2.6 随机数法
      选择一个随机数,取关键字的随机函数值为它的散列地址。也就是f(key) = random(key)。这里random是随机函数。当关键字的长度不等时,采用这个方法构造散列函数是比较合适的。
      总之,现实中,应该视不同的情况采用不同的散列函数,这里只能给出一些考虑的因素来提供参考:
      (1)计算散列地址所需的时间
      (2)关键字的长度;
      (3)散列表的长度;
      (4)关键字的分布情况;
      (5)记录查找的频率。
      综合以上等因素,才能决策选择哪种散列函数更合适。

    3. 处理散列冲突的方法
        在理想的情况下,每一个关键字,通过散列函数计算出来的地址都是不一样的,可现实中,这只是一个理想。市场会碰到两个关键字key1 != key2,但是却有f(key1) = f(key2),这种现象称为冲突。出现冲突将会造成查找错误,因此可以通过精心设计散列函数让冲突尽可能的少,但是不能完全避免。
      3.1 开放定址法
      所谓的开放定址法就是一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入。
      它的公式为:
      这里写图片描述
      比如说,关键字集合为{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34},表长为12。散列函数f(key) = key mod 12。
      当计算前5个数{12, 67, 56, 16, 25}时,都是没有冲突的散列地址,直接存入,如下表所示。
      这里写图片描述
      计算key = 37时,发现f(37) = 1,此时就与25所在的位置冲突。于是应用上面的公式f(37) = (f(37) + 1) mod 12 =2,。于是将37存入下标为2的位置。如下表所示。
      这里写图片描述
      接下来22,29,15,47都没有冲突,正常的存入,如下标所示。
      这里写图片描述
      到了48,计算得到f(48) = 0,与12所在的0位置冲突了,不要紧,我们f(48) = (f(48) + 1) mod 12 = 1,此时又与25所在的位置冲突。于是f(48) = (f(48) + 2) mod 12 = 2,还是冲突……一直到f(48) = (f(48) + 6) mod 12 = 6时,才有空位,如下表所示。
      这里写图片描述
      把这种解决冲突的开放定址法称为线性探测法。

      考虑深一步,如果发生这样的情况,当最后一个key = 34,f(key) = 10,与22所在的位置冲突,可是22后面没有空位置了,反而它的前面有一个空位置,尽管可以不断地求余后得到结果,但效率很差。因此可以改进di=12, -12, 22, -22………q2, -q2(q<= m/2),这样就等于是可以双向寻找到可能的空位置。对于34来说,取di = -1即可找到空位置了。另外,增加平方运算的目的是为了不让关键字都聚集在某一块区域。称这种方法为二次探测法。
      这里写图片描述
      还有一种方法,在冲突时,对于位移量di采用随机函数计算得到,称之为随机探测法。
      既然是随机,那么查找的时候不也随机生成di 吗?如何取得相同的地址呢?这里的随机其实是伪随机数。伪随机数就是说,如果设置随机种子相同,则不断调用随机函数可以生成不会重复的数列,在查找时,用同样的随机种子,它每次得到的数列是想通的,相同的di 当然可以得到相同的散列地址。
      这里写图片描述
      总之,开放定址法只要在散列表未填满时,总是能找到不发生冲突的地址,是常用的解决冲突的方法。
      3.2 再散列函数法
      对于散列表来说,可以事先准备多个散列函数。
      这里写图片描述
      这里RHi 就是不同的散列函数,可以把前面说的除留余数、折叠、平方取中全部用上。每当发生散列地址冲突时,就换一个散列函数计算。
      这种方法能够使得关键字不产生聚集,但相应地也增加了计算的时间。

    3.3 链地址法
    将所有关键字为同义词的记录存储在一个单链表中,称这种表为同义词子表,在散列表中只存储所有同义词子表前面的指针。对于关键字集合{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34},用前面同样的12为余数,进行除留余数法,可以得到下图结构。
    这里写图片描述
    此时,已经不存在什么冲突换地址的问题,无论有多少个冲突,都只是在当前位置给单链表增加结点的问题。
    链地址法对于可能会造成很多冲突的散列函数来说,提供了绝不会出现找不到地址的保证。当然,这也就带来了查找时需要遍历单链表的性能损耗

    3.4 公共溢出区法
    这个方法其实更好理解,你冲突是吧?那重新给你找个地址。为所有冲突的关键字建立一个公共的溢出区来存放。
    这里写图片描述
    在查找时,对给定值通过散列函数计算出散列地址后,先与基本表的相应位置进行比对,如果相等,则查找成功;如果不相等,则到溢出表中进行顺序查找。如果相对于基本表而言,有冲突的数据很少的情况下,公共溢出区的结构对查找性能来说还是非常高的。

    1. 散列表查找实现
    #include<stdio.h>
    #include<stdlib.h>
    
    typedef struct hash{
        int *elem;  //数据元素存储基地址,动态分配数组 
        int count;
    }HashTable;
    
    //初始化散列表
    void Init_HashTable(HashTable *h,int m)
    {
        int i;
        h->elem=(int *)malloc(sizeof(int)*m);
        if(!h->elem)
        {
            printf("散列表长度不能为0\n"); 
        }
        for(i=0;i<m;i++)
        {
            h->elem[i]=NULL;
        }
    }
    
    //散列函数(采用的是除留余数法)
    int Hash(int key,int m)
    {
        return key%m;
     } 
    
    //将数组插入到散列表
    void Insert_HashTable(HashTable *h,int key,int m)
    {
        int addr = Hash(key,m);
    
        //开放地址法的线性探测 
        int i;
        for(i=1;h->elem[addr];i++)
        {
            if(!i%2)
            {
                i=i/2;
            }
            addr=(key+((-1)^i)*i^2)%m;
        }
        h->elem[addr]=key; 
     }
    
     //散列表查找关键字
     void Search_HashTable(HashTable *h,int key,int m)
     {
        int addr = Hash(key,m);
        int i=1;
        for(;h->elem[addr]&&h->elem[addr]!=key;i++) //哈希表位置为addr的值不为空,且不等于key,则线性探测 
        {
            if(!i%2)
            {
                i=i/2;
            }
            addr=(key+((-1)^i)*i^2)%m;
        }
        if(h->elem[addr]==key)                                          
        {
            printf("the %d is at the %d of the HashTable\n",key,addr);
        }else{
            printf("no found\n");
        }
      } 
    int main(void)
    {
        int m = 10,key,i;
        HashTable *h;
        int a[8]={10,15,29,36,59,46,68,58};
        printf("请输入要查找的数");
        scanf("%d",&key);
        Init_HashTable(h,m);
        for(i=0;i<8;i++)
        {
            Insert_HashTable(h,a[i],m);
        }
        Search_HashTable(h,key,m);
        for(i=0;i<m;i++)
        {
            printf("%5d",h->elem[i]);
        }
        return 0;
     } 

    5.散列表的性能分析
    如果没有冲突,散列查找是所介绍过的查找中效率最高的。因为它的时间复杂度为O(1)。但是,没有冲突的散列只是一种理想,在实际应用中,冲突是不可避免的。
    那散列查找的平均查找长度取决于哪些因素呢?
    (1)散列函数是否均匀
    散列函数的好坏直接影响着出现冲突的频繁程度,但是,不同的散列函数对同一组随机的关键字,产生冲突的可能性是相同的(为什么??),因此,可以不考虑它对平均查找长度的影响。
    (2)处理冲突的方法
    相同的关键字、相同的散列函数,但处理冲突的方法不同,会使得平均查找长度不同。如线性探测处理冲突可能会产生堆积,显然就没有二次探测好,而链地址法处理冲突不会产生任何堆积,因而具有更好的平均查找性能。
    (3)散列表的装填因子
    所谓的装填因子a = 填入表中的记录个数/散列表长度。a标志着散列表的装满的程度。当填入的记录越多,a就越大,产生冲突的可能性就越大。也就说,散列表的平均查找长度取决于装填因子,而不是取决于查找集合中的记录个数。
    不管记录个数n有多大,总可以选择一个合适的装填因子以便将平均查找长度限定在一个范围之内,此时散列表的查找时间复杂度就是O(1)了。为了这个目标,通常将散列表的空间设置的比查找表集合大。

    6.散列表的适应范围
    散列技术最适合的求解问题是查找与给定值相等的记录。对于查找来说,简化了比较过程,效率会大大提高。
      但是,散列技术不具备很多常规数据结构的能力,比如
        同样的关键字,对应很多记录的情况,不适合用散列技术;
        散列表也不适合范围查找等等。

    展开全文
  • 散列表查找散列表概念如何构造散列函数处理冲突的方法开放定址法线性探插法二次探查法双重散列法拉链法(链地址法)例子散列表查找开放定址法数据结构线性探查法查找算法插入算法拉链法数据结构定义查找算法插入算法...
  • 散列查找(重点讲解查找失败的ASL) 习题集

    千次阅读 多人点赞 2020-10-22 19:48:42
    本文以例题形式讲解散列查找中,散列表的构建,以及查找成功的ASL和失败的ASL。重点讲解求解失败的ASL的过程,巨详细
  • (1)自己定义一个散列函数,例如f(x)=x mod 11,从键盘输入一个数列,依次插入到散列表中去,采用线性探测方法解决碰撞问题。...(2)输入一个数字,根据所选择的散列函数进行相应的查找,输出查找结果。
  • 一、散列函数构造法 二、直接定
  • 我将主要讲解介绍 查找的相关知识,如查找算法等,希望你们会喜欢。
  • 二分查找 条件1:经过排序的数据集合 条件2:只适合于顺序存储的数据结构 设有数据集合 {5,13,17,42,46,55,70,94} 元素 5 13 17 42 46 55 70 94 下标 0 1 2 3 4 5 6 7 表示 low high ...
  • 哈希查找/散列查找(HashSearch)

    千次阅读 2020-08-02 21:38:12
    这就好比" 字典",我们查找字典中的某个关键字(key)时,只需要查找目录即可找到该关键字(key)存放的页码(位置/地址),而查找的目录是有限的,且是线性的(常数阶/线性阶),所以无论字典存放的元素、关键字再...
  • 已知的几种查找方法: (1)顺序查找:O(n); (2)二分查找(静态查找):O(logn); (3)二叉搜索树:O(h)(h为二叉查找树高度);...散列查找的两项基本工作: (1)计算位置:构造散列函数确定...
  • 散列查找实验(闭散列) 题目编号:582 题目描述: 请设计一个整型闭散列表,散列函数为除留余数法,处理冲突时的探查方法为线性探查法,其中散列表的长度、除留余数法的模和关键码的个数由键盘输入,再根据输入由...
  • 因为查找操作时,找到空地址代表查找失败,但事实上,也许是散列到这里的数据对象已经绕过这里存在了别处。 一般来说,发生了第i次冲突,我们试探的下一个地址将增加di。即h1(key)=(h(key) + di) mod TableSize。...
  • 本节主要讲散列表查找实现思想,几种常见散列函数和解决冲突方法。
  • C实现 散列查找

    千次阅读 2018-12-25 14:07:05
    (1)掌握散列查找的基本思想; (2)掌握闭散列表的构造方法; (3)掌握线性探测处理冲突的方法; (4)验证散列技术的查找性能。 2.实验内容 (1)对于给定的一组整数和散列函数,采用线性探测法处理冲突构造散列表; ...
  • 数据结构 第十一讲 散列查找(哈希) 一、散列表 编译处理时,涉及变量及属性(如:变量类型)的管理: 插入:新变量定义 查找:变量的引用 编译处理中对变量的管理:动态查找问题 利用查找树(搜索树)进行变量...
  • 实现散列查找(数据结构与算法 - 查找)

    千次阅读 多人点赞 2020-04-25 10:31:00
    本关讨论散列存储,散列函数使用除留余数法,冲突解决方法采用独立链表地址法。假设有 8 个关键码: 7 , 15 , 23 , 31 , 12 , 14 , 10 , 17 ,采用散列函数hash(key)=key%7,其存储结构图如图 1 所示,它由 7 个独立...
  • 请设计一个整型闭散列表,散列函数为除留余数法,处理冲突时的探查方法为线性探查法,其中散列表的长度、除留余数法的模和关键码的个数由键盘输入,再根据输入由键盘输入所有的关键码。分别对三个待查值在散列表中...
  • 时间复杂度最好也只是O(N),有没有一种查找方式可以一找就找到呢,有,那就是散列查找散列查找的关键就是创建散列表。 散列表:是实现字典操作的一种有效数据结构。最坏查找时间为O(n),理论上可以达到的平均查询...
  • 分别对三个待查值在散列表中进行查找,输出查找结果采用头插法。 * 输入描述 各个命令以及相关数据的输入格式如下: 第一行输入闭散列表的长度n 第二行输入除留余数法的模m 第三行输入关键码的个数num 第...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 83,240
精华内容 33,296
关键字:

散列查找