精华内容
下载资源
问答
  • 开放寻址法
    千次阅读
    2019-09-22 16:13:49

    开放寻址法的装载因子

      给定一个能存放n个元素的、具有m个槽位的哈希表T,采用开放寻址法时T的装载因子为: α = n / m , n ≤ m \alpha=n/m,n \leq m α=n/mnm

    开放寻址法

      解决哈希表(在一些文献中又称作散列表)冲突的方法有:链接法(chaining)开放寻址法(open addressing)。本文讲解开放寻址法。
      在开放寻址法中,所有元素都存在哈希表里。也就是说,每个表项或包含动态集合的一个元素,或包含 N I L NIL NIL(空)。当查找某个元素时,要系统地检查所有的表项,直到找到所需的元素或者最终查明该元素不在表中。在开放寻址法中,哈希表可能被填满,以至于不能插入任何新的元素,该方法导致的一个结果便是装载因子 α \alpha α绝对不会超过1。
      开放寻址法的好处是其不使用指针,直接使用
    哈希函数
    来算出存取的位置,这样也可以加快存取速度。

    插入关键字

      为了使用开放寻址法插入一个元素,需要连续地检查哈希表,或称为探查(probe),直到找到一个空槽来放置待插入的关键字为止。检查的顺序依赖待插入的关键字。对于每一个关键字 k k k,使用开放寻址法探查序列为 < h ( k , 0 ) , h ( k , 1 ) , ⋯   , h ( k , m − 1 ) > <h(k,0), h(k,1),\cdots, h(k,m-1)> <h(k,0),h(k,1),,h(k,m1)>,假设散列表T中的元素仅为关键字,关键字 k k k等同于包含关键字 k k k的元素。 T T T中的每一个槽或包含一个关键字,或包含 N I L NIL NIL(如果该槽为空)。 H A S H − I N S E R T HASH-INSERT HASHINSERT过程以一个哈希表 T T T和一个关键字 k k k为输入,要么返回其关键字 k k k的存储槽位,要么因为散列表已满而返回出错标志。

    HASH-INSERT(T, k)
    i=0
    repeat
    	j=h(k,i)
    	if T[j] == NIL
    		T[j] = k
    		return j
    	else i=i+1
    until i==m
    error “hash table overflow"
    

    查找关键字

      查找关键字k的算法的探查序列与将k插入时的算法一样。因此,在查找的过程中碰到一个空槽时(该位置为NIL),查找算法就停止,因为如果 k k k在表中,它就应该在此处,而不会在探查序列随后的位置上。过程HASH-SEARCH的输入为一个哈希表 T T T和一个关键字 k k k,如果槽 j j j中包含了关键字 k k k,则返回 j j j;如果 k k k不存在 T T T中,则返回 N I L NIL NIL

    HASH-SEARCH(T, k)
    i=0
    repeat
    	j=h(k,i)
    	if T[j] == NIL
    		T[j] = k
    		return j
    	else i=i+1
    until i==m
    return NIL
    

    删除关键字

      从开放寻址法的哈希表中删除元素比较麻烦。当我们从槽 i i i中删除关键字时,不能仅仅将其置为 N I L NIL NIL来标识其为空。如果这样做,就会有问题:在插入关键字 k k k时,发现槽 i i i被占用了,则 k k k就被插入到后面的位置上;如果此时将槽 i i i中的关键字删除后,就无法检索到关键字 k k k了。有个解决办法,就是在槽 i i i中置一个特殊的值 D E L E T E D DELETED DELETED替代 N I L NIL NIL来标记该槽。这样就要对过程 H A S H − I N S E R T HASH-INSERT HASHINSERT做相应的修改,将这样的槽当做空槽,是得在此仍然可以插入新的关键字。对 H A S H − S E A R C H HASH-SEARCH HASHSEARCH无需做改动,因为它在搜索时会绕过 D E L E T E D DELETED DELETED标识。但是查找时间就不依赖于装载因子了。
      这里给出的算法参考了Knuth 6.4 Algorithm R(TAOCP),该算法对应使用线性探测来确定关键字 k k k插入位置的HASH-INSERT过程的关键字k删除算法。 H A S H − L I N E A R − P R O B E − D E L E T E HASH-LINEAR-PROBE-DELETE HASHLINEARPROBEDELETE过程以一个哈希表 T T T和一个关键字 k k k为输入。该过程没有使用删除标记 D E L E T E D DELETED DELETED这种方式,而是将关键字 k k k删除后,将该位置之后的关键字做移动这种方式(即重新调整各个关键字的顺序)。
    $(i+1) %m $

    nextIndex(i,m)
    return (i + 1 <= m + 1) ? (i+1) : 1
    

    使用线性探测确定关键字 k k k的索引

    HASH-LINEAR-PROBE(T, k)
    for i=0 to m-1
    	index = (h(k) + i) mod m
    	if T[index] == k or T[index] == NIL
    		return index
    return NIL
    
    HASH-LINEAR-PROBE-DELETE(T, k)
    i = HASH-SEARCH(T,k)
    if T[i] == NIL
    	return
    T[i] = NIL
    j = i
    for i = i+1 to nextIndex(i,m)
    	if T[i] == NIL
    		return
    	r = HASH-LINEAR-PROBE(T, T[i])
    	if r == NIL //无法探测到T[i]应该存放的位置
    		return
    	if i <= r < j or r<j<i or j<i<=r  //r循环地位于i和j之间
    		continue
    	if r != NIL and r != i //T[i]存放的位置不应该是当前位置
    		T[j] = T[i]
    		T[i] = NIL
    		j = i
    		i = i+1
    

    开放寻址法探查序列的计算方法

      有三种技术常用来计算开放寻址法中的探测序列:线性探查、二次探查和双重探查。这几种技术都能保证对每个关键字 k , < h ( k , 0 ) , h ( k , 1 ) , ⋯   , h ( k , m − 1 ) > k,<h(k,0), h(k,1),\cdots, h(k,m-1)> k,<h(k,0),h(k,1),,h(k,m1)>都是 < 0 , 1 , ⋯   , m − 1 > <0, 1,\cdots, m-1> <0,1,,m1>的一个排列。但是,这些技术都不能满足均匀哈希的假设,因为它们能产生的不同探查序列数都不超过 m 2 m^2 m2 个(均匀散列要求有 m ! m! m! 个探查序列)。在三种技术中,双重探查产生的探查序列最多,似乎能给出最好的效果。

    1. 线性探查(linear probing)
        给定一个普通的哈希函数 h ′ : U → 0 , 1 , ⋯   , m − 1 h':U\to{0,1,\cdots,m-1} h:U0,1,,m1,称之为辅助哈希函数,线性探查方法采用的哈希函数为:
      h ( k , i ) = ( h ′ ( k ) + i )    m o d    m ,    i = 0 , 1 , ⋯   , m − 1 h(k,i) = (h'(k) + i) \; mod \;m,\; i=0,1,\cdots,m-1 h(k,i)=(h(k)+i)modm,i=0,1,,m1
      给定一个关键字 k k k,首先探查 T [ h ′ ( k ) ] T[h'(k)] T[h(k)](此时的 i = 0 i=0 i=0),即由辅助哈希函数所给出的槽位。再探查 T [ h ′ ( k ) + 1 ] T[h'(k)+1] T[h(k)+1],以此类推,直至槽 T [ m − 1 ] T[m-1] T[m1]。然后又绕到槽 T [ 0 ] T[0] T[0] T [ 1 ] T[1] T[1] ⋯ \cdots ,直到最后探查到槽 T [ h ′ ( k ) − 1 ] T[h'(k)-1] T[h(k)1]。在线性探查方法中,初始探查位置绝对了整个序列,故只有 m m m种不同的探查序列。
        线性探查法比较容易实现,但它存在着一个问题,称为一次群集。随着连续被占用的槽不断增加,平均查找时间也随之不断增加。群集现象很容易出现,这是因为当一个空槽前有 i i i个满的槽时,该空槽为下一个将被占用的概率是 ( i + 1 ) / m (i+1)/m (i+1)/m。连续被占用的槽就会变得越来越长因而平均查找时间也会越来越大。
    2. 二次探查
        二次探查采用如下形式的哈希函数:
      h ( k , i ) = ( h ′ ( k ) + c 1 i + c 2 i 2 )    m o d    m ,    i = 0 , 1 , ⋯   , m − 1 h(k,i) = (h'(k) + c_1i + c_2i^2) \; mod \;m,\; i=0,1,\cdots,m-1 h(k,i)=(h(k)+c1i+c2i2)modm,i=0,1,,m1
      其中 h ′ h' h是一个辅助哈希函数, c 1 c_1 c1 c 2 c_2 c2为正的辅助常数, i = 0 , 1 , ⋯   , m − 1 i=0,1,\cdots,m-1 i=0,1,,m1。初始的探查位置为 T [ h ′ ( k ) ] T[h'(k)] T[h(k)],后续的探查位置要加上一个偏移量,该偏移量是一个关于 i i i的二次函数。这种探查方法的效果比线性探查好得多,但是,为了能够充分利用哈希表, c 1 c_1 c1 c 2 c_2 c2 m m m的值要受到限制。此外,如果两个关键字的初始探查位置相同,那么它们的探查序列也是相同的,这是因为 h ( k 1 , 0 ) = h ( k 2 , 0 ) h(k_1,0)=h(k_2,0) h(k1,0)=h(k2,0)蕴含着 h ( k 1 , i ) = h ( k 2 , i ) h(k_1,i)=h(k_2,i) h(k1,i)=h(k2,i)。像线性探查一样,初始探测位置决定了整个序列,这样也仅有 m m m个不同的探查序列。
    3. 双重哈希
        双重哈希是用于开放寻址法的最好方法之一,因为它所产生的排列具有随机选择排列的许多特性。双重哈希采用如下的哈希函数:
      h ( k , i ) = ( h 1 ( k ) + i h 2 ( k ) )    m o d    m ,    i = 0 , 1 , ⋯   , m − 1 h(k,i) = (h_1(k) + ih_2(k)) \; mod \;m,\; i=0,1,\cdots,m-1 h(k,i)=(h1(k)+ih2(k))modm,i=0,1,,m1
      其中 h 1 h_1 h1 h 2 h_2 h2均为辅助哈希函数。初始探查位置为 T [ h 1 ( k ) ] T[h_1(k)] T[h1(k)],后续的探查位置加上偏移量 h 2 h_2 h2。因此,不像线程探查或者二次探查,这里的探查序列以两种不同方式依赖于关键字 k k k,因为初始探查位置、偏移量或者二者都可能发生变化。
        为了能查找整个哈希表,值 h 2 ( k ) h_2(k) h2(k)必须要与表的大小 m m m互素(习题11.4-4)。有一种简便的方法确保这个条件成立,就是 m m m为2的幂,并设计一个总产生奇数的 h 2 h_2 h2。另一种方法是取m为素数,并设计一个总是返回较 m m m小的正整数的函数 h 2 h_2 h2
        一个结论:如果对某个关键字 k k k m m m h 2 ( k ) h_2(k) h2(k)有最大公约数 d ≥ 1 d\geq1 d1,则在对关键字 k k k的一次不成功查找中,在返回槽 h 1 ( k ) h_1(k) h1(k)之前,要检查散列表中 1 / d 1/d 1/d个元素。于是,当 d = 1 d=1 d=1时, m m m h 2 ( k ) h_2(k) h2(k)互素,查找操作可能要检查整个哈希表。
    更多相关内容
  • 开放寻址法VS链表法

    千次阅读 2020-03-25 21:18:36
    开放寻址法VS链表法 开放寻址法 只用数组一种数据结构存储,继承了数组的优点,对CPU缓冲友好,易于序列化。但是对内存的利⽤率并不如链表法,且冲突的代价更高。当数据量⽐较⼩、装载因⼦⼩的时候,适合采⽤...

                                    开放寻址法VS链表法

     

    开放寻址法


    只用数组一种数据结构存储,继承了数组的优点,对CPU缓冲友好,易于序列化。但是对内存的利⽤率并不如链表法,且冲突的代价更高。当数据量⽐较⼩、装载因⼦⼩的时候,适合采⽤开放寻址法。这也是Java中的ThreadLocalMap使⽤开放寻址法解决散列冲突的原因。

    链表法


    链表法对内存的利⽤率⽐开放寻址法要⾼。因为链表结点可以在需要的时候再创建,并不需要像开放寻址法那样事先申请好。链表法⽐起开放寻址法,对⼤装载因⼦的容忍度更⾼。基于链表的散列冲突处理⽅法⽐较适合存储⼤对象、⼤数据量的散列表,⽽且,⽐起开放寻址法,它更加灵活,⽀持更多的优化策略,⽐如⽤红⿊树代替链表。

    示例

     

    在实际应用中,无论如何构造哈希函数,冲突是无法完全避免的。

    1 开放地址法 


    这个方法的基本思想是:当发生地址冲突时,按照某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止。这个过程可用下式描述:
    H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… , k ( k ≤ m – 1)) 
    其中: H ( key ) 为关键字 key 的直接哈希地址, m 为哈希表的长度, di 为每次再探测时的地址增量。 
    采用这种方法时,首先计算出元素的直接哈希地址 H ( key ) ,如果该存储单元已被其他元素占用,则继续查看地址为 H ( key ) + d 2 的存储单元,如此重复直至找到某个存储单元为空时,将关键字为 key 的数据元素存放到该单元。 
    增量 d 可以有不同的取法,并根据其取法有不同的称呼:
    ( 1 ) d i = 1 , 2 , 3 , …… 线性探测再散列;
    ( 2 ) d i = 1^2 ,- 1^2 , 2^2 ,- 2^2 , k^2, -k^2…… 二次探测再散列;
    ( 3 ) d i = 伪随机序列 伪随机再散列; 

    例1设有哈希函数 H ( key ) = key mod 7 ,哈希表的地址空间为 0 ~ 6 ,对关键字序列( 32 , 13 , 49 , 55 , 22 , 38 , 21 )按线性探测再散列和二次探测再散列的方法分别构造哈希表。
    解:
    ( 1 )线性探测再散列:
    32 % 7 = 4 ; 13 % 7 = 6 ; 49 % 7 = 0 ;
    55 % 7 = 6 发生冲突,下一个存储地址( 6 + 1 )% 7 = 0 ,仍然发生冲突,再下一个存储地址:( 6 + 2 )% 7 = 1 未发生冲突,可以存入。
    22 % 7 = 1 发生冲突,下一个存储地址是:( 1 + 1 )% 7 = 2 未发生冲突;
    38 % 7 = 3 ;
    21 % 7 = 0 发生冲突,按照上面方法继续探测直至空间 5 ,不发生冲突,所得到的哈希表对应存储位置:
    下标: 0 1 2 3 4 5 6
    49 55 22 38 32 21 13
    ( 2 )二次探测再散列:
    下标: 0 1 2 3 4 5 6
    49 22 21 38 32 55 13
       注意:对于利用开放地址法处理冲突所产生的哈希表中删除一个元素时需要谨慎,不能直接地删除,因为这样将会截断其他具有相同哈希地址的元素的查找地址,所以,通常采用设定一个特殊的标志以示该元素已被删除。

     

    区别

    1     在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可而对开放地址法构造的散列表,删除结点不能简单地将被删结点的空间置为空,否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中,空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点。 

     

    由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;

     

    3 开放地址法:容易产生堆积问题;不适于大规模的数据存储;散列函数的设计对冲突会有很大的影响;插入时可能会出现多次冲突的现象,删除的元素是多个冲突元素中的一个,需要对后面的元素作处理,实现较复杂;结点规模很大时会浪费很多空间;

     

    4 .链地址法:处理冲突简单,且无堆积现象,平均查找长度短;链表中的结点是动态申请的,适合构造表不能确定长度的情况;相对而言,拉链法的指针域可以忽略不计,因此较开放地址法更加节省空间。插入结点应该在链首,删除结点比较方便,只需调整指针而不需要对其他冲突元素作调整。

     

    拉链法的优点

     

    与开放定址法相比,拉链法有如下几个优点:

    ①拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;

    ②由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;

    ③开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;

    ④在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

     

    拉链法的缺点

     

    指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。

    使用例子:

    HashMap

    二、开发地址法

    开放地址法有个非常关键的特征,就是所有输入的元素全部存放在哈希表里,也就是说,位桶的实现是不需要任何的链表来实现的,换句话说,也就是这个哈希表的装载因子不会超过1。它的实现是在插入一个元素的时候,先通过哈希函数进行判断,若是发生哈希冲突,就以当前地址为基准,根据再寻址的方法(探查序列),去寻找下一个地址,若发生冲突再去寻找,直至找到一个为空的地址为止。所以这种方法又称为再散列法。
     

    参考地址

    https://blog.csdn.net/qq_30091945/article/details/78044445?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task

     

    https://blog.csdn.net/cy_cai/article/details/53939174?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task

    在这里插入图片描述

    展开全文
  • 开放寻址法中,所有的元素都存放在散列表里。也就是说,每个表项或包含动态集合的一个元素,或包含NoneNoneNone。当查找某个元素时,要系统地检查所有的表项,直到找到所需的元素,或者最终查明该元素不在表中。不...

    分类目录:《算法设计与分析》总目录
    相关文章:
    ·散列表[哈希表](一):基础知识
    ·散列表[哈希表](二):直接寻址表
    ·散列表[哈希表](三):散列表原理
    ·散列表[哈希表](四):散列函数
    ·散列表[哈希表](五):开放寻址法
    ·散列表[哈希表](六):完全散列


    在开放寻址法中,所有的元素都存放在散列表里。也就是说,每个表项或包含动态集合的一个元素,或包含 N o n e None None。当查找某个元素时,要系统地检查所有的表项,直到找到所需的元素,或者最终查明该元素不在表中。不像链接法,这里既没有链表,也没有元素存放在散列表外。因此在开放寻址法中,散列表可能会被填满,以至于不能插入任何新的元素。该方法导致的一个结果便是装载因子 a a a绝对不会超过1。

    开放寻址法的核心思想是,如果出现了散列冲突,我们就重新探测一一个空闲位置,将其插入。比如,我们可以使用线性探测法。当我们往散列表中插入数据时,如果某个数据经过散列函数散列之后,存储位置已经被占用了,我们就从当前位置开始,依次往后查找,看是否有空闲位置,如果遍历到尾部都没有找到空闲的位置,那么我们就再从表头开始找,直到找到为止。

    当然,也可以将用作链接的链表存放在散列表未用的槽中,但开放寻址法的好处就在于它不用指针,而是计算出要存取的槽序列。于是,不用存储指针而节省的空间,使得可以用同样的空间来提供更多的槽,潜在地减少了冲突,提高了检索速度。

    为了使用开放寻址法插入一个元素,需要连续地检查散列表,或称为探查,直到找到一个空槽来放置待插入的关键字为止。检查的顺序不一定是 0 , 1 , ⋯   , m − 1 0, 1, \cdots, m-1 0,1,,m1,而是要依赖于待插入的关键字。为了确定要探查哪些槽,我们将散列函数加以扩充,使之包含探查号以作为其第二个输入参数。这样,散列函数就变为:
    h : U × { 0 , 1 , ⋯   , m − 1 } → { 0 , 1 , ⋯   , m − 1 } h:U×\{0, 1, \cdots, m-1\}\rightarrow \{0, 1, \cdots, m-1\} h:U×{0,1,,m1}{0,1,,m1}
    对每一个关键字 k k k,使用开放寻址法的探查序列是 < 0 , 1 , ⋯   , m − 1 > <0, 1, \cdots, m-1> <0,1,,m1>的一个排列,使得当散列表逐渐填满时,每一个表位最终都可以被考虑为用来插入新关键字的槽。

    查找关键字 k k k的算法的探查序列与将 k k k插入时的算法一样。因此,查找过程中碰到一个空槽时,查找算法就(非成功地)停止,因为如果 k k k在表中,它就应该在此处,而不会在探查序列随后的位置上(之所以这样说,是假定了关键字不会从散列表中删除)。

    从开放寻址法的散列表中删除操作元素比较困难。当我们从槽 i i i中删除关键字时,不能仅将 N o n e None None置于其中来标识它为空。如果这样做,就会有问题:在插入关键字 k k k时,发现槽 i i i被占用了,则就被插人到后面的位置上;此时将槽 i i i中的关键字删除后,就无法检索到关键字 k k k了。

    有一个解决办法,就是在槽 i i i中置一个特定的值 D E L E T E D DELETED DELETED替代 N o n e None None来标记该槽。这样就将这样的一个槽当做空槽,使得在此仍然可以插入新的关键字。

    线性探查

    给定一个普通的散列函数 h ′ : U → { 0 , 1 , ⋯   , m − 1 } h':U\rightarrow \{0, 1, \cdots, m-1\} h:U{0,1,,m1},称之为辅助,线性探查方法采用的散列函数为:
    h ( k , i ) = ( h ′ ( k ) + i ) m o d    m h(k ,i)=(h'(k)+i)\mod m\quad h(k,i)=(h(k)+i)modm
    给定一个关键字 k k k,首先探查槽 T [ h ′ ( k ) ] T[h'(k)] T[h(k)],即由辅助散列函数所给出的槽位。再探查槽T T [ h ′ ( k ) + 1 ] T[h'(k)+1] T[h(k)+1],依此类推,直至槽 T [ m − 1 ] T[m-1] T[m1]。然后,又绕到槽 T [ 0 ] , T [ 1 ] , ⋯ T[0], T[1], \cdots T[0],T[1],直到最后探查到槽 T [ h ′ ( k ) − 1 ] T[h'(k)-1] T[h(k)1]。在线性探查方法中,初始探查位置决定了整个序列,故只有 m m m种不同的探查序列。

    线性探査方法比较容易实现,但它存在着一个问题,称为一次群集。随着连续被占用的槽不断增加,平均査找时间也随之不断增加。群集现象很容易出现,这是因为当个空槽前有 i i i个满的槽时,该空槽为下一个将被占用的概率是 i + 1 m \frac{i+1}{m} mi+1。连续被占用的槽就会变得越来越长,因而平均查找时间也会越来越大。

    二次探查

    二次探查采用如下形式的散列函数:
    h ( k , i ) = ( h ′ ( k ) + c 1 i + c 2 i 2 ) m o d    m h(k ,i)=(h'(k)+c_1i+c_2i^2)\mod m\quad h(k,i)=(h(k)+c1i+c2i2)modm
    其中 h ′ h' h是一个辅助散列函数, c 1 c_1 c1 c 2 c_2 c2为正的辅助常数。初始的探查位置为 T [ h ′ ( k ) ] T[h'(k)] T[h(k)],后续的探查位置要加上一个偏移量,该偏移量以二次的方式依赖于探查序号 i i i。这种探查方法的效果要比线性探查好得多,但是,为了能够充分利用散列表, c 1 c_1 c1 c 2 c_2 c2 m m m的值要受到限制。此外,如果两个关键字的初始探查位置相同,那么它们的探查序列也是相同的,这是因为 h ( k 1 , 0 ) = h ( k 2 , 0 ) h(k_1,0)=h(k_2,0) h(k1,0)=h(k2,0)蕴涵着 h ( k 1 , i ) = h ( k 2 , i ) h(k_1,i)=h(k_2,i) h(k1,i)=h(k2,i)。这一性质可导致一种轻度的群集,称为二次群集。像在线性探查中一样,初始探查位置决定了整个序列,这样也仅有 m m m个不同的探查序列被用到。

    双重散列

    双重散列是用于开放寻址法的最好方法之一,因为它所产生的排列具有随机选择排列的许多特性。双重散列采用如下形式的散列函数:
    h ( k , i ) = ( h 1 ( k ) + i h 2 ( k ) ) m o d    m h(k ,i)=(h_1(k)+ih_2(k))\mod m\quad h(k,i)=(h1(k)+ih2(k))modm

    其中 h 1 h_1 h1 h 2 h_2 h2均为辅助散列函数。初始探查位置为 T [ h 1 ( k ) ] T[h_1(k)] T[h1(k)],后续的探查位置是前一个位置加上偏移量 h 2 ( k ) h_2(k) h2(k) m m m。因此,不像线性探查或二次探查,这里的探查序列以两种不同方式依赖于关键字 k k k,因为初始探查位置、偏移量或者二者都可能发生变化。下图给出了一个使用双重散列法进行插入的例子。
    双重探查

    为了能查找整个散列表,值 h 2 ( k ) h_2(k) h2(k)必须要与表的大小 m m m互质。当 m m m为素数或者2的幂时,双重散列法中用到了 Θ ( m 2 ) \Theta(m^2) Θ(m2)种探查序列,而线性探查或二次探查中用了 Θ ( m ) \Theta(m) Θ(m)种,故前者是后两种方法的种改进。因为每一对可能的 ( h 1 ( k ) , h 2 ( k ) (h_1(k), h_2(k) (h1(k),h2(k)都会产生一个不同的探查序列。因此,对于 m m m的每一种可能取值,双重散列的性能看起来就非常接近“理想的”均匀散列的性能。

    尽管除素数和2的幂以外的 m m m值在理论上也能用于双重散列中,但是在实际中,要高效地产生 h 2 ( k ) h_2(k) h2(k)确保使其与 m m m互质,将变得更加困难。部分原因是这些数的相对密度中可能较小。

    开放寻址散列的分析

    像在链接法中的分析一样,开放寻址法的分析也是以散列表的装载因子 a = n m a=\frac{n}{m} a=mn来表达的当然,使用开放寻址法,每个槽中至多只有一个元素,因而 n ≤ m n≤m nm,也就意味着 a ≤ 1 a≤1 a1

    假设采用的是均匀散列。在这种理想的方法中,用于插入或查找每一个关键字 k k k的探查序列等可能地为 < 0 , 1 , ⋯   , m − 1 > <0, 1, \cdots, m-1> <0,1,,m1>的任意一种排列。当然,每一个给定的关键字有其相应的唯一固定的探查序列。我们这里想说的是,考虑到关键字空间上的概率分布及散列函数施于这些关键字上的操作,每一种探查序列都是等可能的。

    现在就来分析在均匀散列的假设下,用开放寻址法来进行散列时探查的期望次数。则:

    1. 给定一个装载因子为 a = n m < 1 a=\frac{n}{m}<1 a=mn<1的开放寻址散列表,并假设是均匀散列的,则对于一次不成功的查找,其期望的探查次数至多为 1 1 − a \frac{1}{1-a} 1a1
    2. 假设采用的是均匀散列,平均情况下,向一个装载因子为 a a a的开放寻址散列表中插入一个元素至多需要做 1 1 − a \frac{1}{1-a} 1a1次探查。
    3. 对于一个装载因子为 a < 1 a<1 a<1的开放寻址散列表,一次成功查找中的探查期望数至多为 1 a ln ⁡ 1 1 − a \frac{1}{a}\ln\frac{1}{1-a} a1ln1a1
    展开全文
  • 思路 一个函数可以将一个范围内的数(本题为10-9~109)映射到...开放寻址法和拉链法为对冲突的两种处理方法。 离散化是一种特殊的哈希方式 开放寻址法: 处理冲突的基本思路是创建一个一维数组,数组长度经验来说一..

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

    思路

    一个函数可以将一个范围内的数(本题为10-9~109)映射到另一个范围内(本题为0 ~ 105)之间的一个数,被称为哈希函数。

    1. 哈希函数的写法: x mod 105
      x取余后必然会在 0 ~ 105之间。
    2. 冲突
      可能会将若干不一样的数,映射到同一个数,(x范围大,值域范围小)大概率会发生冲突,如假设对12取余h[2] = 2, h[14] = 2;

    开放寻址法和拉链法为对冲突的两种处理方法。

    离散化是一种特殊的哈希方式

    在这里插入图片描述

    开放寻址法:

    处理冲突的基本思路是创建一个一维数组,数组长度经验来说一般为题目操作数N的2~3倍,N表示总共需要存储的数的个数,本题而言,N最大为105,所以这里数组的容量至少开到为2*105

    在这里插入图片描述

    对哈希函数而言,一般来说模的这个数,要取成质数,且这个质数要离2的整次幂尽可能的远,数学上可证明这么取的话冲突的概率是最小的。

    以下算法来判断大于200000的第一个质数

    判断最大质数

    #include<iostream>
    #include<cstring>
    //判断100000以上第一个质数
    using namespace std;
    
    const int N = 200010;
    
    int main() {
        for (int i = 200000; ; i++) {
            bool flag = true;
            for (int j = 2; j * j <= i; j++) {
                if (i % j == 0) {
                    flag = false;
                    break;
                }
            }
            if (flag){
                cout << i << endl;
                break;
            }
        }
        return 0;
    }
    

    结果输出为 200003;
    故之后取数组长度为N = 200003。

    插入的方法均从第k个数开始询问该位置是否有元素,有则k++,最终停留在没有元素的位置。
    查找也一样,从第k个数开始询问这个位置存的数是否等于x。

    int find(int x) {
        int k = (x % N + N) % N; //若x是负数时,可用该方法避免下标k出现负值,
        while (h[k] != null && h[k] != x) {
            k ++;
            if (k == N) k = 0;
        }//最终k停留的地方为等于x或null处
        return k;
    }
    

    我们在初始化h[N]以后要对其进行赋空null,以示此时没有元素插入,一般链表用-1,在此处,我们使用0x3f3f3f3f,来填充h[N]。宏定义null = 0x3f3f3f3f可以减少考虑时间:

    引用一段他人博客中的介绍:

    0x3f3f3f3f是一个很有用的数值,它是满足以下两个条件的最大整数。
    1、整数的两倍不超过 0x7f7f7f7f,即int能表示的最大正整数。
    2、整数的每8位(每个字节)都是相同的。
    我们在程序设计中经常需要使用 memset(a, val, sizeof a) 初始化一个数组a,该语句把数值 val(0x00~0xFF)填充到数组a 的每个字节上,所以用memset只能赋值出“每8位都相同”的 int。
    当需要把一个数组中的数值初始化成正无穷时,为了避免加法算术上溢出或者繁琐的判断,我们经常用 memset(a, 0x3f, sizeof(a)) 给数组赋 0x3f3f3f3f的值来代替。

    (参考:https://blog.csdn.net/qq_31267769/article/details/88890612)

    代码

    #include<iostream>
    #include<cstring>
    
    using namespace std;
    
    const int N = 200003, null = 0x3f3f3f3f;
    int h[N];
    
    
    int find(int x) {
        int k = (x % N + N) % N;
        while (h[k] != null && h[k] != x) {
            k ++;
            if (k == N) k = 0;
        }
        return k;
    }
    
    int main() {
        int n;
        scanf ("%d", &n); 
        memset(h, 0x3f, sizeof h); //填充h[N]
        while (n--) {
            char op[2];
            int x;
            
            scanf("%s%d",op, &x);
            int k = find(x);
            if (op[0] == 'I') h[k] = x;
            else {
    
                if (h[k] != null) puts("Yes");
                else puts("No");
            }
        }
        
        return 0;
    }
    
    展开全文
  • 开放寻址法和拉链法十分类似,只是处理冲突的方式不一样。拉链法通过在冲突位置开链表解决,开放寻址法通过往后顺次找空位置解决。 拉链法: #include<iostream> #include<cstdio> #include<vector&...
  • 一、拉链法需要注意的是,拉链法中定义的几个数组分别为 h[N],e[N],ne[N],idx,...二、开放寻址法同样需要注意的是h[N]的含义以及它的原理。原理:同样以取模的形式进行哈希,但是由于会发生碰撞,在这里处理碰撞的方式
  • } 第二种方法(开放寻址法): #include #include //使用memset得使用这个头文件 using namespace std;//开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了 const int N = 2e5 + 3; //取大于数据范围的第...
  • 开放寻址法 插入:通过find函数查找一个数放置的位置,若不为空,则查看下一个位置,直到找到空的位置或查到该数已经存在。 查找:如果hash表中存在该数,则最终会返回该数的索引,否则返回的索引所在位置为空。 ...
  • //开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了 const int N = 200003;//大于数据范围的第一个质数 int null = 0x3f3f3f3f;//规定空指针为 null 0x3f3f3f3f int h[N]; int find(int x) { int k = (x...
  • 为什么threadlocalmap要用开放寻址法

    千次阅读 2020-08-20 23:07:06
    解决哈希冲突有两种方法,开放寻址法和链表法。 那么为什么hashmap用链表法,而threadlocalmap用的是开放寻址法呢? 在开放寻址法中,所有的数据都存储在一个数组中,比起链表法来说,冲突的代价更高。 所以,使用...
  • 哈希表(开放寻址法)

    2021-07-16 14:28:51
    #include<iostream> #include<cstring> using namespace std; const int N=200003; int h[N],null=0x3f3f3f3f; int find(int x) { int k=(x%N+N)%N; while(h[k]!=null&&...}...
  • =Max)cout一: 拉链法 把数教列到某 指定长度的数组 设数组长度为n 把大于几的数或小于一n的教取模 然后映射到对应的表格内 对于取模结果相同时采用链式结构 采用一个链连表来维护散列表 二:开放寻址法 开启辛一六...
  • 开放寻址法:又称开放定址法,当哈希冲突发生时,从发生冲突的那个单元起,按照一定的次序,从哈希表中寻找一个空闲的单元,然后把发生冲突的元素存入到该单元。这个空闲单元又称为开放单元或者空白单元。开放寻址法...
  • 开放寻址法   3.再HASH法   4.建立公共溢出池   等等 为什么不用3和4? 4方法浪费内存,3增加了算法的复杂度,不推荐。其实我也不清楚。 链式地址法和开放地址法的优缺点分别是什么? 链式地址法(HashMap...
  • 哈希冲突解决之开放寻址法

    千次阅读 2015-09-11 16:01:36
    使用开放寻址法是槽本身直接存放数据,在插入数据时如果key所映射到的索引已经有数据了,这说明发生了冲突,这时会寻找下一个槽,如果该槽也被占用了则继续寻找下一个槽,直到找到没有被占用的槽,在查找时也使用...
  • 当然,映射时不同点的地址可能会发生冲突(取模得到同一个结果),在此我们可以采取两种方式来解决hash冲突 -----------开放寻址法和链地址法。 我们先来介绍开放寻址法,其主要思想为若是当前地址已经被占用(发生了...
  • 模拟散列表(哈希表:拉链法 + 开放寻址法) 维护一个集合,支持如下几种操作: “I x”,插入一个数x; “Q x”,询问数x是否在集合中出现过; 现在要进行N次操作,对于每个询问操作输出对应的结果。 输入格式 第一...
  • 这是一道模拟哈希表开放定址解决冲突的问题,题目中要求使用二次探测(Quadratic probing )。先复习一下什么是二次探测—— h ( i ) = ( h ( k e y ) + i × i ) m o d ( M ) , 0 ≤ i ≤ M − 1 h(i)=(h(key...
  • 开放寻址法 当哈希函数计算出的元素插入位置已不可用时,按某种规律探测其他可用位置的方法,叫开放寻址法。使用开放寻址法时,负载系数一定不超过1。 探测方法有许多,开放寻址法 按探测方法的不同 又可以分为以下...
  • 算法竞赛模板,详细讲解哈希表模板(开放寻址法、拉链法、字符串哈希值代码)
  • Name:Hash表初学 (数组实现链表 开放寻址法 ) Actor:HT Time:2015年9月29日 Error Reporte: */ #include"stdio.h" #include"string.h" #include"stdlib.h" int hash[9000]; int value[9000]; int f1...
  • 开放寻址法解决散列冲突

    千次阅读 2016-05-10 14:51:13
    除了链表法,还有开放寻址法用来解决冲突。  简单地讲,也就是说,一间厕所,来了一个顾客就蹲其对应的位置,如果又来一个顾客,把厕所单间门拉开,一看里 面有位童鞋正在用劲,那么怎么办?很自然的,拉另一个...
  • 算法导论 开放寻址法

    千次阅读 2017-03-22 20:57:41
    散列表11.4 开放寻址法 开放寻址法中,所有的元素都存放在散列表里,每个表项或包含动态集合的一个元素或者NIL。当查找某个元素时,要系统的检查所有表项,直到找到所有的元素或者最终查明元素不在表中。 为了使用...
  • 开放寻址法记录

    2013-09-18 00:34:56
    #include #include using namespace std; class openAddressing{public: openAddressing():store(new int[m]), m(20), n(19){ for(int i = 0; i m; i++){ store[i] = -1; } } int insert(const int &val) {
  • hash table(开放寻址法-二次探查实现的哈希表) #ifndef C11LEARN_HASHQUADRATIC_H #define C11LEARN_HASHQUADRATIC_H #include "HashLiner.h" template<typename T> class HashQuadratic:public HashLiner&...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,747
精华内容 4,698
关键字:

开放寻址法