精华内容
下载资源
问答
  • 数组、链表到散列

    千次阅读 2016-10-20 17:07:39
    为什么我们需要各种各样的数据结构?对我们而言,通常对于数据...一般来讲,数据结构将直接影响对其处理的算法的选择,在本文中的散列函数算法又会反过来影响散列表这种结构之于数据的存贮效率,可以说,数据结构与算法

    为什么我们需要各种各样的数据结构?

    对我们而言,通常对于数据的操作无外乎以下几种方式:增、删、改、查。其中除增加外,其他几种操作均要求对集合进行搜索。而结构化的数据模型可以通过数组、链表或者树形结构等建立,不同的建模方式对于数据处理中的各种操作有不同的性能表现。一般来讲,数据结构将直接影响对其处理的算法的选择,在本文中的散列函数算法又会反过来影响散列表这种结构之于数据的存贮效率,可以说,数据结构与算法的关系就好比是一卵双生。

    数组、链表存储数据的方式

    下面通过一张图让我们看清数组和链表是如何存储集合中的数据的:
    

    这里写图片描述
    通过上图我们可以得到以下发现:

    用数组存储数据,我们利用了数组单元在物理位置上的邻接关系来表示表中元素之间的逻辑关系。由于这个原因,用数组有如下的优缺点。

    优点是:
    无须为表示表中元素之间的逻辑关系增加额外的存储空间;
    可以方便地随机访问表中任一位置的元素。
    缺点是:
    插入和删除运算不方便,除表尾的位置外,在表的其他位置上进行插入或删除操作都必须移动大量元素,其效率较低;
    由于数组要求占用连续的存储空间,存储分配只能预先进行静态分配。因此,当表长变化较大时,难以确定数组的合适的大小。确定大了将造成浪费。

    用单向链表存储数据,一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息,第二个部分存储下一个节点的地址,而最后一个节点则指向一个空值。。单向链表只可向一个方向遍历。一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点,一直访问到需要的位置。由于这个原因,用链表有如下的优缺点。

    优点是:
    向链表中插入或者从链表中删除一项的操作不需要移动很多项,而只涉及常数个节点的链的改变。
    缺点是:
    在删除最后一项比较复杂,因为必须找出指向最后节点的项,把它的next链改为null,然后再更新持有最后节点的链。
    其无法提供随机访问能力,单向链表只可向一个方向遍历。

    • 最后我们知道这两种结构对存储空间的利用率都很高,谁说这不是一个优点呢,至少对于散列来说是的。
    • 而散列是一种用于以常数平均时间执行插入、删除和查找的技术。但是那些需要元素间任何排序信息的操作将不会得到有效支持。

    什么是散列

    在解释散列的含义之前,我们先来深入的观察一下普通数组这种数据结构,由上图所示,将集合{a,b,c,d,e,f}存储在数组中时占据了索引为0~5的6个存储空间,我们可以形式化的表示为有序对(An ordered pair)的集合,即{(a,0),(b,1),(c,2),(d,3),(e,4),(f,5)}。但其实这个集合中任意一个有序对的元素之间的关系是未定义的(undefined),因此这样的有序对集合可以有6!个。然而我们是否可以构造一个关系,使得待存储的集合{a,b,c,d,e,f}中的任意一个元素通过这个关系都能找到一个指定的索引值,由下图更形象的表示:
    这里写图片描述

    根据上图我们知道原有集合中的元素被散列之后所得到的有序对的集合为{(d,0),(b,2),(c,2),(a,3),(f,4),(e,5)}。其中,散列表中的1号槽为空,表示经过散列函数作用之后,原集合中没有任何元素被散列至该位置,而2号槽中则存在两个元素,将两个不同元素散列至相同位置的情形我们称为碰撞(Collision)。如上图所示,我们通过使用链表将不同元素链接起来解决碰撞,在后文中还将介绍另外一种称为开放寻址(Open addressing)的解决方法。这里更具体的说明一下链接法的链接形式:因为散列至同一个槽的元素并无顺序上的先后要求,因此为效率计,我们将总是采用在链表头插入碰撞元素的做法,最终导致的结果是,在一个链表中,越靠近表头的节点,在原数组中被散列的次序越靠后。综上所述,可以对散列函数hash进行如下形式化定义:
    设在大小为N的集合中存在元素elem,存储原集合中元素的散列表共有m个槽位,则有
    hash: elem→γ∈{0,1,2,…,m-1}
    这就是散列的基本想法。剩下的问题就是要选择一个函数,决定当两个关键字散列到同一个值的时候(碰撞)应该做什么以及如何确定散列表的大小。

    散列函数

    这个散列函数涉及关键字中的所有字符,并且一般可以分布得很好。这个散列函数利用到事实:允许溢出。这可能会引进负数,因此在末尾有附加的测试。
    这个散列函数就表的分布而言未必是最好的,但确实具有极其简单的优点而且速度也很快。如果关键字特别长,那么该散列函数计算起来将会花费过多的时间。在这种情况下通常的经验是不适用所有的字符。

    public static int hash(String key,int tableSize){
        int hashVal = 0;
    for(int i = 0; i <key.length(); i++)
        hashVal = 37*hashVal + key.charAt(i);
    hashVal %= tableSize;
    if(hashVal < 0)
    hashVal += tableSize
    
    return hashVal;
    }

    剩下的主要问题就是如果解决冲突的消除问题。如果当一个元素被插入时域一个已经插入的元素散列到相同的值,那么就会产生一个冲突,这个冲突需要消除。解决这种冲突的方法有几种,我们将讨论其中最简单的两种:分裂链接法和开放寻址法。

    分离链接法

    解决冲突的第一种方法叫做分离链接法(separate chaining),其做法是将散列到用一个值的所有元素保存到一个表中。
    这里写图片描述
    为执行一次查找,我们使用散列函数来确定究竟遍历哪一个链表。然后我们再在确定的链表中执行一次查找。为了执行insert,我们检查相应的链表看看该元素是否已经处在合适的位置(如果允许插入重复元,那么通常需要留出一个格外的域,这个域当出现匹配事件时增1)。如果这个元素是个新元素,那么它将被插入到链表的前端,这不仅因为方便,还因为常常发生这样的事实:新近插入的元素最有可能不久又被访问。
    紧接着我们需要考虑:散列表的大小为多少较好?

    设所有元素之间均相互独立,且每个元素被散列至每个槽的概率均相等 ————> 假设①
    并设原集合的尺寸为n,散列表的大小为m,装载因子α=n/m ————–>假设②
    最重要的是,我们并不考虑散列函数所消耗的计算开销 —————->假设③
    由假设①,元素被散列至每个槽的概率相等,再根据假设②中散列表的大小为m,有P{elem→γ∈{0,1,2,…,m-1}}=1/m
    设待查找的关键字为k,因此存在两种情况:Ⅰ、待查找关键字k不存在; Ⅱ、关键字k存在
    然而其实情况Ⅰ的搜索开销即为情况Ⅱ的最坏情况运行时间,因为关键字k不存在时将查找整个链表
    以下是更详细的分析:
    ——>Ⅰ、由假设①,并且根据假设②有装载因子α=n/m,所以α表示每个槽的结点数。因为当待查找的关键字k不存在时,我们必将搜索到该槽中的最后一个结点处,因此在这种情况下的搜索开销为O(α)。
    ——>Ⅱ、对于关键字k存在的情况,其实不做详细分析我们就已经知道,这种情况下的运行时间必然不超过O(α),然而单单分析本身就是一件很有趣的事情,为何不做得彻底一些?更重要的是,下面所用到的这种方法,其体现的思想对于分析随机过程将具有极大的益处。
    这里写图片描述
    综上可知,如果我们将散列表设定为与原集合大小相同时,装载因子α=1,此时的搜索时间为O(1),但其实设置为原集合尺寸的1/2或是2倍并没有多大区别。需要注意的是虽然散列表越大导致搜索时间减少,但其所占内存空间将会增大。

    开放寻址法

    分离链接散列算法的缺点是使用一些链表。由于给新单元分配地址需要时间(特别是其他语言中),因此这就导致算法的速度有一些减慢,同时算法实际上还要求对第二种数据结构的实现。同链接法一样,开放寻址是一种用于解决碰撞的策略。不同之处在于,在链接法中,每个关键字只能对应一个固定的槽,而在开放寻址中,每个关键字可以对应算列表中中的多个槽,因为有可能在首次寻址过程中,该槽已被先前的关键字所占据,因而接下来我们根据事先所制定的某个规则继续试探下一个槽是否可用,直至找到一个可用的槽并将关键字存储在其中为止。一般来说,因为所有的数据都要放置如表内,所以这方法需要的表的大小要比分离链接散列的表大,而且其装填因子应该低于α=0.5。我们把这样的表叫做探测散列表。

    线性探测法

    设 hash(key, i)=(hash’(key)+i) mod m,其中 i=0,1,…,m-1,hash’为辅助散列函数
    在线性试探中,首次探查位置取决于hash’(key)的值,若发生碰撞,则接下来所探查的位置为(hash’(key)+1) mod m,从而所形成的探查序列为

    平方探测法

    设 hash(key,i)=(hash’(key)+c1i+c2i2) mod m,如上所述,i=0,1,…,m-1,hash’为辅助散列函数,c1,c2为辅助参数
    可以发现,线性试探法实际是二次试探的特殊情况,若取参数c1=1,c2=0,那么二次试探将“退化”为线性试探。同样的,整个探查序列也是由hash’(key)所决定的,因为虽然探查序列中各元素之间的增量[c1i+c2i2]不再以线性的方式进行,但对于每个元素来说,引导因子i总是以步长1的方式递增,这就导致所有元素的探查序列的增加方式是相同的,因此整个散列表同样提供m种不同的探查序列。但随着散列表中元素的增加,这种跳跃式的增量方式使得插入/搜索操作的运行时间受到的影响较小。
    虽然平方探测排除了一次聚集,但是散列到同一个位置上的那些元素将探测相同的备选单元,这叫做二次聚集。二次聚集是理论上的一个小缺憾。对于每次查找,它一般要引起另外的少于一半的探测。下面的技术将会排除这个缺憾,不过这要付出计算一个附加的散列函数的代价。

    双散列

    设 hash(key,i)=(hash’(key)+i×hash”(key)) mod m,其中i=0,1,…,m-1,hash’,hash”均为辅助散列函数
    双重试探法的首个探查位置为hash’(key),当产生碰撞之后,接下来的探查位置为(hash’(key)+hash”(key)) mod m,因此我们发现在双重试探法中,不仅初始探查位置依赖于关键字key,探查序列中的增量hash”(key)同样依赖于关键字key,因而整个散列表提供了m2种不同的探查序列,较之于前两种开放寻址具备了更多的灵活性。这里还要注意的是应保证hash”(key)与m互质,因为根据固定的偏移量所寻址的所有槽将形成一个群,若最大公约数p=gcd(m, hash”(key))>1,那么所能寻址的槽的个数为m/p

    再散列

    对于使用平方探测的开放寻址散列法,如果散列表被填的太满,那么操作的运行时间将开始消耗过长,且插入操作可能失败。这可能发生在有太多的移动和插入混合的场景。此时,一种解决方法是建立一个大约两倍大的表(并且使用一个相关的新散列函数),扫描整个原始散列表,计算每个(未删除的)元素的新散列值并将其插入到新表中。
    整个操作就叫做再散列(rehashing)。显然这时一种开销非常大的操作,其运行时间为O(N) ,因为有N个元素要再散列而表的大小约为2N,不过,由于不是经常发生。因此实际效果根本没有那么差。特别是在最后的再散列之前必然已经存在N/2次insert,因此添加到每个插入上的发费基本上是一个常数开销。如果这种数据结构是程序的一部分,那么其影响是不明显的。
    再散列可以用平方探测以多种方法实现。一种做法是只要表满到一半就再散列。另一种极端的方法是只有当插入失败时才再散列。第三种方法即途中策略:当散列表到达某一个装填因子时进行再散列。由于随着装填因子的增长散列表的性能确实下降,所以第三种方式可能是理想的策略。

    展开全文
  • 这是数据结构课程作业,用二次探测再散列法解决冲突建立哈希表并查找 从键盘读入 待查找 的权重数值,以除留余数法为哈希函数,二次探测再散列法解决冲突建立哈希表,基于哈希算法从数组中查找相应的记录,计算相应...
  • 搜索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)互质,否则会出现无法生成坐标的情况。

    所以我让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[H],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

    ( 2021.7.8 第一次修改)

    展开全文
  • 散列表相关题目(线性探测再散列法

    千次阅读 多人点赞 2020-12-02 02:05:00
    散列表的存储空间是一个下标从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!!!

    展开全文
  • 基于线性探测再散列法的Hash表的“查找成功的ASL”和“查找不成功的ASL”ASL指的是 平均查找时间关键字序列:(7、8、30、11、18、9、14)散列函数: H(Key) = (key x 3) MOD 7装载因子: 0.7处理冲突:线性探测...
    

    基于线性探测再散列法的Hash表的“查找成功的ASL”和“查找不成功的ASL”

    ASL指的是 平均查找时间

    关键字序列:(7、8、30、11、18、9、14)

    散列函数:
    H(Key) = (key x 3) MOD 7

    装载因子:
    0.7

    处理冲突:线性探测再散列法


    查找成功的ASL计算方法:

    因为现在的数据是7个,填充因子是0.7。所以数组大小=7/0.7=10,即写出来的散列表大小为10,下标从0~9。
    第一个元素7,带入散列函数,计算得0。
    第二个元素8,带入散列函数,计算得3。
    第三个元素30,带入散列函数,计算得6。
    第四个元素11,带入散列函数,计算得5。
    第五个元素18,带入散列函数,计算得5;此时和11冲突,使用线性探测法,得7。
    第六个元素9,带入散列函数,计算得6;此时和30冲突,使用线性探测法,得8。
    第七个元素14,带入散列函数,计算得0;此时和7冲突,使用线性探测法,得1。
    所以散列表

    地址0123456789
    key714 8 1130189 

    所以查找成功的计算:
    如果查找7,则需要查找1次。
    如果查找8,则需要查找1次。
    如果查找30,则需要查找1次。
    如果查找11,则需要查找1次。
    如果查找18,则需要查找3次:第一次查找地址5,第二次查找地址6,第三次查找地址7,查找成功。
    如果查找9,则需要查找3次:第一次查找地址6,第二次查找地址7,第三次查找地址8,查找成功。
    如果查找地址14,则需要查找2次:第一次查找地址0,第二次查找地址1,查找成功。
    所以,ASL=(1+2+1+1+1+3+3)/ 7=12/ 7


    查找不成功的ASL计算方法:

    鉴于网络上有各种版本,本人认为此种计算方法比较合理。验证实例可以参考2010年的计算机408考研真题的第一道计算大题和答案。

    1. 定义什么叫查找不成功
    举个例子来说吧。在已知上面散列表的基础上,如果要查找key为4的关键字。根据散列函数可以计算Hash(key)=Hash(4)=5。此时在地址为5的地方取出那个数字,发现key=11,不等于4。这就说明在装填的时候会发生冲突。根据冲突处理方法,会继续检测地址为6的值,发现key=30,依然不等。这个时候到了地址为6,但是依然没有找到。那么就说明根本就没有key=4这个关键字,说明本次查找不成功。注意:为什么到地址6?因为散列函数中有 mod7 ,对应的地址为0~6,即0~6查找失败的查找次数。
    再举一个例子。查找key为0的关键字,根据散列函数可以计算Hash(key)=Hash(0)=0。此时在地址为0的地方取出那个数字,发现key=7,不等于0。这就说明在装填的时候会发生冲突。根据冲突处理方法,会继续检测地址为1的值,发现key=14,依然不等。这个时候到了地址为3,发现为空依然没有找到。所以停止查找,本次查找不成功。因为如果key=0这个关键字存在的话,依照冲突处理函数,就一定能找到它。总不能丢了吧。



    2. 根据第一点定义的不成功,依次推下去:
    查找地址为0的值所需要的次数为3,
    查找地址为1的值所需要的次数为2,
    查找地址为2的值所需要的次数为1,
    查找地址为3的值所需要的次数为2,
    查找地址为4的值所需要的次数为1,
    查找地址为5的值所需要的次数为5,
    查找地址为6的值所需要的次数为4。


    3.计算
    查找不成功ASL=(3+2+1+2+1+5+4)/ 7=18/ 7

    以上就是基于线性探测再散列法的Hash表的平均查找时间ASL的计算,当然还有其他的处理冲突方式的平均查找时间,具体另当讨论
    展开全文
  • 开放散列(open hashing)/ 拉链(针对桶链结构) 封闭散列(closed hashing)/ 开放定址 通过构造性能良好的哈希函数,可以减少冲突,但一般不可能完全避免冲突,因此解决冲突是哈希法的另一个关键问题。创建...
  • 数组 数组是指的有限个类型相同的变量的集合。组成数组的各个变量称为数组的元素,有时也称为下标变量。 数组的特点 对于数组有以下特点 数组内的元素应该具有相同的数据类型 数组元素用整个数组的名字和它自己在...
  • 散列表的存储空间是一个下标从0开始的一维数组,散列函数为: H(key) = (keyx3) MOD 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。 (1) 请画出所构造的散列表。 (2) 分别计算等概率情况下查找成功和...
  • 哈希表(Hash Table)及散列法(Hashing) 数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?...
  • 散列存储方法

    万次阅读 2016-04-09 10:43:18
    散列数组存储方式的一种发展,相比数组散列的数据访问速度要高于数组。要依据数据的某一部分来查找数据时数组一般要从头遍历数组才能确定想要查找的数据位置,而散列是通过函数通过“想要查找的数据”作为“输入...
  • 哈希表的开散列法(拉链法)

    千次阅读 2018-03-01 21:56:28
    散列法又叫链地址法(开链法)。 开散列法:首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在...
  • 先将一组数据以除留余存储,就是说 假定一个线性表为a[]={18, 75, 60, 43, 54, 90, 46},选取散列函数为:h(K)=K%m 取m=13 得到的 h(K) 就是数据在 storeArray[ ] 中存储的下标 例: a[]={18, 75, 60, 43, 54, ...
  • 要知道的是,散列法搜索不像昨天介绍的两种搜索方式,线性搜索和二分搜索中元素可以排列在任意位置,而散列法搜索则是根据各元素的值来确定存储位置,然后将位置保管在散列表中,从而实现数据的高速搜索。...
  •  即不同关键字通过相同哈希函数计算出相同的哈希地址,对于哈希冲突的处理方法,通常有两种:闭散列法和开散列法,本文先介绍闭散列法,也叫开放地址法。当发生哈希冲突时,如果哈希表未被装满,说明在...
  • 什么是散列法

    千次阅读 2014-06-10 11:28:06
    什么是散列法散列法是把字符串映射到整数的处理, 通常是到一个相对小的范围。一个“散列函数” 映射一个字符串(或其它的数据结构) 到一个有界的数字(散列存贮桶),这个数字可以更容易的用于数组的索引或者进行反复...
  • 最近复习了下数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅资料终于知道如何计算...将关键字序列(7、8、30、11、18、9、14)散列存储...
  • 散列表类似于数组,可以把散列表的散列值看成数组的索引值,访问散列表和访问数组元素一样快速,他可以在常数时间内实现查找和插入操作。 由于无法通过散列值知道键的大小,因此散列表无法实现有序性操作。 散列...
  • 以vector为容器(可自动扩展),供用户多次输入(而不是在源代码中设置数组)来建立散列,以拉链解决冲突(头插入建链),可进行多次搜索
  • 哈希表(除留余数法构造 线性探测再散列法处理冲突)#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表其实就是将键值经过一系列计算(Horner运算法则,不懂得请自行百度),在规定大小(可进行再散列,这里只是做讲解)的散列表中进行存储,散列表的长度一般为素数(具体原因个人也没理解,但如果用非素数,...
  • 先说明一下,她们两个属于不同的范畴,双散列属于开放定址,仍是一种解决冲突的策略。而再散列是为了解决插入操作运行时间过长、插入失败问题的策略。简而言之,她们的区别在于:前者让散列表做的“对”(把冲突...
  • 题目来源:2010-408_计算机学科专业基础综合 ...将关键字序列(7 . 8 . 30 . 11 . 18 .... 14)散列存储到散列表中,散列表的存储空间是一个下标从0开始的一维数组散列函数 是: H(key)=(key x3)...
  • 线性探测再散列

    万次阅读 热门讨论 2019-10-07 09:57:11
    把这个值解释为一块连续存储空间(即数组空间)的单元地址(即下标),将该记录存储到这个单元中。在此称该函数H为哈函数或散列函数。按这种方法建立的表称为哈希表或散列表。 处理冲突的方法: 开放寻址:Hi=(H...
  • 今天是开通博客后第一次做算法导论习题呢。。。首先是算法导论散列表11.1的答案,然后是乘法散列的一点总结
  • 虽然上文有提到怎么解释的开放地址处理hash冲突,但是当时只是给了个简单的图,没有 详细讲解一下, 我当时有点不明白,回头查查资料,然后亲自动手,整理了一下。 然后我就三幅图详细讲解一下: 什么叫线性探测再...
  • 通常在发生这种冲突时我们会用到解决冲突的技术,包括桶式散列法、开放地址法、双重散列法。下面一一实现和介绍三种技术! 桶式散列法 “桶”是一种存储在散列表元素内的简单数据结构,它可以存储多个数据项,这种...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,635
精华内容 12,254
关键字:

数组散列法