精华内容
下载资源
问答
  • 搜索2—散列法

    2021-03-01 10:54:40
    散列法 1.简单实现 2.解决冲突 示例 搜索2 散列法 散列法是一种搜索算法,它根据各元素的值来确定存储的位置,然后将位置保存在散列表中,从而实现数据的高速搜索。 散列表是一种数据结构,能够包含...

    目录

    搜索2

    散列法

    1.简单实现

    2.解决冲突

    示例


    搜索2

     

    散列法

     

    散列法是一种搜索算法,它根据各元素的值来确定存储的位置,然后将位置保存在散列表中,从而实现数据的高速搜索。

     

    散列表是一种数据结构,能够包含对关键数据集合高效地执行动态插入,搜索,删除等操作。、

    虽然链表(参考之前的文章)也能进行同样的操作,但搜索和删除的复杂度都高达O(n)。

    如果不发生冲突,散列法插入和搜索元素的算法复杂度仅为O(1)。

     

    散列表有容纳n个元素的数组S和根据关键字决定数组下标的函数组成。

    也就是说,我们输入关键字,由函数决定关键字在数组中存储的位置。

     

    1.简单实现

     

    散列表的实现:

    insert(key)
        S[h(key)]=key
    
    search(key)
        return S[h(key)]

     

    当输入的关键字为字符串或其他类型,要将其转换为相应的整数。

    h(k)是根据k的值求数组下标的函数,称为散列函数,h(k)的返回值称为散列值。

    为了保证散列值小于数组S的长度n,要进行取余运算

    例如:h(k)=k mod n 是一种简单的散列函数。(mod是取余运算符)

     

    2.解决冲突

     

    对于一个散列函数,会出现不同的key值对应相同的散列值的情况,即发生了“冲突”。

    当遇到“冲突”时,我们要解决冲突,常见的解决冲突的方法有:开放地址法,链地址法等等。

    在这里我们使用双散列结构中的开放地址法。

     

    H(k)=h(k,i)=(h_{1}(k)+i\times h_{2}(k)) mod n

     

    此函数拥有两个参数,k为关键字key的值,i为发生冲突后计算散列值的次数。

    要注意的是,每次移动h_{2}(k)个位置,必须保证S的长度n与h_{2}(k)互质,否则会出现无法生成坐标的情况。(比如m和h_{2}(k)都是偶数的情况)

    所以我让n为质数,然后取一个小于n的值为h_{2}(k)

    如下图所示:

     

     

     

    散列法的实现:

    int h1(int key) {
    	return key % n;
    }
    
    int h2(int key) {
    	return 1 + key % (n - 1);
    }
    
    int h(int key, int i) {
    	return (h1(key) + i * h2(key)) % n;
    }
    
    int insert(int S[],int key) {
    	i = 0;
    	while (1) {
    		int j = h(key, i);
    		if (S[j] == nil) {//用nil来表示S[J]当前位置为空
    			S[j] = key;
    			return j;
    		}
    		else i = i + 1;
    	}
    }
    
    int search(int S[], int key) {
    	i = 0;
    	while (1) {
    		int j = h(key, i);
    		if (S[j] == key) {
    			return j;
    		}
    		else if (S[j] == nil || i >= n) {
    			return nil;
    		}
    		else i = i + 1;
    	}
    }

     

    示例

    第一行输入命令数n,随后n行按顺序输入n个命令,输入的字符串靳由AGCT组成。

    insert str:向数组中添加字符串str。

    find str:当数组中包含str时,输出yes,不包含输出no。

    输入示例:

    6

    insert AAA 

    insert AAC

    find AAA

    find CCC

    insert CCC

    find CCC

    输出示例:

    yes

    no

    yes

     

    完整答案:

    #include<stdio.h>
    #include<string.h>
    #define m 13
    char S[100][100];
    
    int h1(int key) {
    	return key % m;
    }
    
    int h2(int key) {
    	return 1 + key % (m - 1);
    }
    
    int h(int key, int i) {
    	return (h1(key) + i * h2(key)) % m;
    }
    
    int GETCHAR(char ch) {
    	if (ch == 'A')return 1;
    	if (ch == 'G')return 2;
    	if (ch == 'C')return 3;
    	if (ch == 'T')return 4;
    }
    
    int GETKEY(char str[]) {
    	int sum = 0,p=1;
    	for (int i = 0; i < strlen(str); i++) {
    		sum += p*GETCHAR(str[i]);
    		p *= 5;
    	}
    
    	return sum;
    }
    
    int find(char str[]) {
    	int key = GETKEY(str);
    	for (int i = 0;; i++) {
    		int H = h(key, i);
    		if (strlen(S[H]) == 0)return 0;
    		else if (strcmp(S[H], str) == 0)return 1;
    	}
    
    
    }
    
    int insert(char str[]) {
    	int key = GETKEY(str);
    	for (int i = 0;; i++) {
    		int H = h(key, i);
    
    		if (strlen(S[H]) == 0) {
    			strcpy_s(S[H],100, str);
    			return 0;
    		}
    
    		else if (strcmp(S[H],str) == 0)return 1;
    	}
    
    	return 0;
    }
    
    int main() {
    	
    	char com[10], str[10];
    	int i, n;
    	for (i = 0; i < 100; i++) {
    		S[i][0] = '\0';
    	}
    	scanf("%d", &n);
    	for (i = 0; i < n; i++) {
    
    		scanf("%s", com);
    		scanf("%s", str);
    		if (com[0] == 'i') {
    			insert(str);
    		}
    		else if (find(str)) {
    			printf("yes");
    		}
    		else printf("no");
    
    
    	}
    
    
    	return 0;
    	
    
    }
    

    合理的运用不同用途的散列函数可以减少算法的复杂度,进而提高程序的效率。


    读《挑战程序设计竞赛》(侵删)第九天 2021.3.1

     

    展开全文
  • 散列表的存储空间是一个下标从0开始的一维数组,散列函数为H(key)=(key×3) mod 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。 1)请画出所构造的散列表。 2)分别计算等概率情况下查找成功和查找不...

    散列表相关题目(线性探测再散列法)


    一、题目

    将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,散列函数为H(key)=(key×3) mod 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。

    1)请画出所构造的散列表。

    2)分别计算等概率情况下查找成功和查找不成功的平均查找长度。

    二、解题思路及步骤

    下面是详细的解题过程及方法思路

    ①第(1)问

    在这里插入图片描述

    ②第(2)问

    在这里插入图片描述

    总结

    (1)注意红字部分的内容!!!
    (2)注意在使用线性探测再散列法找地址时,位置为(H(key)mod表长,此处为10),不是题干给出的哈希函数的7!!!
    (3)计算查找失败的ASL时,要考虑初始地址的范围,是题目中所给出的哈希函数中mod后面的值,本题中为7,范围为0~6。注意不是10!!!

    展开全文
  • 什么是散列法

    千次阅读 2014-06-10 11:28:06
    什么是散列法散列法是把字符串映射到整数的处理, 通常是到一个相对小的范围。一个“散列函数” 映射一个字符串(或其它的数据结构) 到一个有界的数字(散列存贮桶),这个数字可以更容易的用于数组的索引或者进行反复...
    什么是散列法?
    散列法是把字符串映射到整数的处理, 通常是到一个相对小的范围。一个“散列函数” 映射一个字符串(或其它的数据结构) 到一个有界的数字(散列存贮桶),这个数字可以更容易的用于数组的索引或者进行反复的比较。明显的, 一个从潜在的有很多组的字符串到小范围整数的映射不是唯一的。任何使用散列的算法都要处理“冲突” 的可能。有许多散列函数和相关的算法被开发了出来; 一个全面的说明已经超出了本文的范围。
    展开全文
  • 通常在发生这种冲突时我们会用到解决冲突的技术,包括桶式散列法、开放地址法、双重散列法。下面一一实现和介绍三种技术! 桶式散列法 “桶”是一种存储在散列表元素内的简单数据结构,它可以存储多个数据项,这种...

    解决冲突

    在处理散列表的时候,不可避免会遇到计算出的散列值已经存储了另外一个键,这就造成了冲突。通常在发生这种冲突时我们会用到解决冲突的技术,包括桶式散列法、开放地址法、双重散列法。下面一一实现和介绍三种技术!

    桶式散列法

    “桶”是一种存储在散列表元素内的简单数据结构,它可以存储多个数据项,这种数据结构其实就是数组,但我们一般可以用ArrayList,它会运行超出范围,并会自动分配更多的空间,这种数据结构会使实现更加高效。桶式散列的基本思想是:在散列表上在放一个数组,不同的散列值上有不同的数组,当出现散列值重复的时候,会判断数组里是否存在该数据,如果没有则添加,如果存在则不做任何操作,当然你也可以进行替换。

    要从散列表中移除数据项,先确定要移除项的所在散列值,通过散列值找到数组,然后判断是否存在该数据项,如果存在则执行删除操作,否则什么也不做。

    在使用桶式散列法时,应尽量保持数组元素的数量尽可能少,在 添加元素会最小化所做的工作。如果数组元素过多,当容量不够时,就会扩充两倍大。元素的数量与散列表的大小比率称为负载系数,当负载系数为1.0时,或者表(散列表)的大小恰好等于元素数量(散列表上都有元素)时,散列表的性能最佳!

    代码演示

     //桶式散列法解决冲突
        //在散列表里存储一个数据结构(一般是数组),它可以存储多个数据项
       public class BucketHash
        {
          
            private const int SIZE = 101;
            ArrayList[] data;
            public BucketHash()
            {
                data = new ArrayList[SIZE];
                for(int i = 0; i <= SIZE - 1; i++)
                {
                    data[i] = new ArrayList(4);
                }
            }
            //计算散列值
            public int Hash(String s)
            {
                long tot = 0;
                char[] charry;
                charry = s.ToCharArray();
                for(int i = 0; i <= s.Length - 1; i++)
                {
                    tot += 37 * tot + (int)charry[i];
    
                }
                tot = tot % data.GetUpperBound(0);
                //if (tot > 0)
                //    tot += data.GetUpperBound(0);
                return (int)tot;
            }
            //hashItem确定散列表的位置(确定ArrayList),item为添加的数
            public void Insert(string hashItem,string item)
            {
                int hash_value;
                hash_value = Hash(hashItem); //得到数据项的散列值,用于确定ArrayList
                if (!data[hash_value].Contains(item))//如果不存在则保存
                {
                    data[hash_value].Add(item);
                }
               
                 
            }
    
            public void Remove(string hashItem, string item)
            {
                int hash_value;
                hash_value = Hash(hashItem);
                if (data[hash_value].Contains(item))//如果存在则移除
                {
                    data[hash_value].Remove(item);
                }
            }
           public void ShowDistrib(string hashItem) //传入散列表对应的值
            {
                Console.WriteLine("解决散列表的重名冲突(桶式散列表)的测试!");
                int  hash_value = Hash(hashItem);
                try
                {
                    if (hash_value >= 0 && hash_value <= data.GetUpperBound(0))
                    {
    
                        ArrayList array = data[hash_value];
                        for (int i = 0; i < array.Count; i++)
                        {
    
                            Console.WriteLine("在散列表{0}桶中所有的值为:{1}", hash_value, array[i]);
    
    
                        }
                    }
                    else {
                        Console.WriteLine("散列表中不存在{0}的位置", hash_value);
    
                    }
                   
    
                }
                catch (ArgumentOutOfRangeException e)
                {
                    Console.WriteLine("该散列值不存在");
    
                }
                catch (Exception e) {
    
                    Console.WriteLine(e);
                }
               
            }
        }

     

    展开全文
  • 散列表、散列法、拉链法的一些概念介绍: 散列表 https://www.cnblogs.com/baxianhua/p/9244769.html 散列表也叫hash表 ,是根据关键码值而进行直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个...
  • 要知道的是,散列法搜索不像昨天介绍的两种搜索方式,线性搜索和二分搜索中元素可以排列在任意位置,而散列法搜索则是根据各元素的值来确定存储位置,然后将位置保管在散列表中,从而实现数据的高速搜索。...
  • 散列法及哈希表

    2012-09-04 22:52:51
    七、哈希表(Hash Table)及散列法(Hashing) 数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构...
  • 这是数据结构课程作业,用二次探测再散列法解决冲突建立哈希表并查找 从键盘读入 待查找 的权重数值,以除留余数法为哈希函数,二次探测再散列法解决冲突建立哈希表,基于哈希算法从数组中查找相应的记录,计算相应...
  • 散列表的存储空间是一个下标从0开始的一维数组,散列函数为: H(key) = (keyx3) MOD 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。 (1) 请画出所构造的散列表。 (2) 分别计算等概率情况下查找成功和...
  • 先将一组数据以除留余存储,就是说 假定一个线性表为a[]={18, 75, 60, 43, 54, 90, 46},选取散列函数为:h(K)=K%m 取m=13 得到的 h(K) 就是数据在 storeArray[ ] 中存储的下标 例: a[]={18, 75, 60, 43, 54, ...
  • 基于线性探测再散列法的Hash表的“查找成功的ASL”和“查找不成功的ASL”ASL指的是 平均查找时间关键字序列:(7、8、30、11、18、9、14)散列函数: H(Key) = (key x 3) MOD 7装载因子: 0.7处理冲突:线性探测...
  • 图解数据结构(5)——散列法及哈希表 七、哈希表(Hash Table)及散列法(Hashing) 数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。那么我们能不能综合两者的特性,做出...
  • 哈希表(除留余数法构造 线性探测再散列法处理冲突)#include &lt;stdio.h&gt;#include &lt;stdlib.h&gt;#include &lt;string.h&gt;int main(){ int a[11]={22,41,53,46,30,13,1,67},b[11]...
  • 哈希表(Hash Table)及散列法(Hashing) 数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?...
  • 这个映射函数就做散列函数,存放记录的数组叫做散列表。 理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。 如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间...
  • 哈希表(Hash Table)及散列法(Hashing) 数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?答案...
  • 题目来源:2010-408_计算机学科专业基础综合 ...将关键字序列(7 . 8 . 30 . 11 . 18 .... 14)散列存储到散列表中,散列表的存储空间是一个下标从0开始的一维数组散列函数 是: H(key)=(key x3)...
  • 散列

    2017-07-30 10:31:00
    理想的散列表数据结构是由一个包含有关键字的具有固定大小的数组 散列函数:关键字到存储单元的映射 冲突解决:分离链接 开放定址 转载于:https://www.cnblogs.com/m2492565210/p/7258440.html...
  • 哈希表定义 我们一般定义一个数组用来表示一个哈希表的存储元素的空间,并且通过哈希函数来实现确定某个元素的存入位置、查找某个元素、删除某个元素。哈希函数 我们定义哈希函数,一般采用除整取余法:hash(key)...
  • Link的解释:其中table[tmp][maxn - 1]++使得队尾元素【101】(n不超过100必不会达到101)在不断变大,作为下一个要插入的数组的下标以及当前数组中的数的个数 int Num [ maxn ] = { } , tmp , table [ maxn ] ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 742
精华内容 296
热门标签
关键字:

数组散列法