精华内容
下载资源
问答
  • 关于散列表的题目

    2019-07-31 14:19:36
    关于散列表的题目 在牛客网上刷到的一个关于散列表的题目,因为当时做的时候看和我之前做的题目一样,没有思考直接做选了结果,最后对答案的时候却发现答案错了。仔细看了一下,发现题目与之前做的题目基本大致相当...

    关于散列表的题目

    在牛客网上刷到的一个关于散列表的题目,因为当时做的时候看和我之前做的题目一样,没有思考直接做选了结果,最后对答案的时候却发现答案错了。仔细看了一下,发现题目与之前做的题目基本大致相当,却是不一样的知识点,在我之前做此题之前我还从未注意过,是一个新的知识点。

    (单选题)
    设哈希表长为14,哈希函数为h(key)=key%11。表中现有数据15、38、61和84,其余位置为空,
    如果用二次探测再散列处理冲突,则49的位置是()
    
    A.8                          B.3
    C.5                          D.9
                                                                           答案:D
    

    分析:

    二次探测再散列:di=1^2, -1^2, 2^2, -22,…,k2, -k^2 ( k<=m/2 )
    开放定址法:Hi=(H(key)+di)MOD m,其中H(key)为哈希函数;m为哈希表长;di为增量序列

    经计算得:
    H(15)=4,H(38)=5
    H(61)=6,H(84)=7
    H(49) = 49%11 = 5与H(38)冲突,根据:Hi=(H(key)+di)MOD m,以及二次探测散列求得:
    di = 1, H1(H(49)+1) MOD 14 = 6 ;因H(61)=6,所以冲突
    di = -1, H2(H(49)-1) MOD 14 = 4 ;因H(15)=4,所以冲突
    di = 4, H3(H(49)+4) MOD 14 = 9;不冲突

    (单选题)
     设哈希表长为14,哈希函数为h(key)=key%11。表中仅有H(15)=4,H(38)=5,H(61)=6,H(84)=7四个结点,其余位置为空,
     如果用线性探测法处理冲突,则49的结点地址是()
    A.8                          B.3
    C.5                          D.9 
                                                                          答案:A
    

    分析:

    di=1,2,3,…m-1,称为线性探测再散列;
    开放定址法:Hi=(H(key)+di)MOD m,其中H(key)为哈希函数;m为哈希表长;di为增量序列

    过程:
    H(49) = 49%11 = 5,发生冲突;
    H1(H(49)+1) MOD 14 = 6,冲突;
    H2(H(49)+2) MOD 14 = 7,冲突;
    H2(H(49)+3) MOD 14 = 8,不冲突;

    展开全文
  • 关于散列表

    2015-03-24 20:35:26
    我一直只知道散列表,才知道散列表其实就是哈希表===怂~~~ 下面给出散列表的教程吧 散列表的概念 注意:  ①由同一个散列函数、不同的解决冲突方法构造的散列表,其平均查找长度是不相同的。  ②散列表的平均查找...

    我一直只知道散列表,才知道散列表其实就是哈希表===怂~~~

    下面给出散列表的教程吧

    散列表的概念
    注意:
          ①由同一个散列函数、不同的解决冲突方法构造的散列表,其平均查找长度是不相同的。
          ②散列表的平均查找长度不是结点个数n的函数,而是装填因子α的函数。因此在设计散列表时可选择α以控制散列表的平均查找长度。

    通过链接法解决冲突:成功查找的期望查找长度O(1+a), 不成功查找的平均查找长度也为O(1+a)。

    开放寻址解决冲突:引入探查序列,对于a<1的开放寻址,成功查找的平均查找长度1/a(1+ln(1/(1-a)); 不成功的查找长度为1/(1-a)

          ③ α的取值
          α越小,产生冲突的机会就小,但α过小,空间的浪费就过多。只要α选择合适,散列表上的平均查找长度就是一个常数,即散列表上查找的平均时间为O(1)。
          ④ 散列法与其他查找方法的区别
    除散列法外,其他查找方法有共同特征为:均是建立在比较关键字的基础上。
    其中顺序查找平均时间为O(n);
    其余的查找均是对有序集合的查找,每次关键字的比较有"="、"<"和">"三种可能,且每次比较后均能缩小下次的查找范围,故查找速度更快,其平均时间为O(lgn)。
    而散列法是根据关键字直接求出地址的查找方法,其查找的期望时间为O(1)。

     
    1、散列表
          设所有可能出现的关键字集合记为U(简称全集)。实际发生(即实际存储)的关键字集合记为K(|K|比|U|小得多)。
          散列方法是使用函数h将U映射到表T[0..m-1]的下标上(m=O(|U|))。这样以U中关键字为自变量,以h为函数的运算结果就是相应结点的存储地址。从而达到在O(1)时间内就可完成查找。
       其中:
          ① h:U→{0,1,2,…,m-1} ,通常称h为散列函数(Hash Function)。散列函数h的作用是压缩待处理的下标范围,使待处理的|U|个值减少到m个值,从而降低空间开销。
          ② T为散列表(Hash Table)。
          ③ h(Ki)(Ki∈U)是关键字为Ki结点存储地址(亦称散列值或散列地址)。
          ④ 将结点按其关键字的散列地址存储到散列表中的过程称为散列(Hashing)
      
     
     


    3、散列表的冲突现象
    (1)冲突
          两个不同的关键字,由于散列函数值相同,因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(Synonym)。
        【例】上图中的k2≠k5,但h(k2)=h(k5),故k2和K5所在的结点的存储地址相同。

    (2)安全避免冲突的条件
          最理想的解决冲突的方法是安全避免冲突。要做到这一点必须满足两个条件:
    ①其一是|U|≤m
    ②其二是选择合适的散列函数。
          这只适用于|U|较小,且关键字均事先已知的情况,此时经过精心设计散列函数h有可能完全避免冲突。

    (3)冲突不可能完全避免
          通常情况下,h是一个压缩映像。虽然|K|≤m,但|U|>m,故无论怎样设计h,也不可能完全避免冲突。因此,只能在设计h时尽可能使冲突最少。同时还需要确定解决冲突的方法,使发生冲突的同义词能够存储到表中。

    (4)影响冲突的因素
          冲突的频繁程度除了与h相关外,还与表的填满程度相关。
          设m和n分别表示表长和表中填人的结点数,则将α=n/m定义为散列表的装填因子(Load Factor)。α越大,表越满,冲突的机会也越大。通常取α≤1。

    散列函数的构造方法

    1、散列函数的选择有两条标准:简单和均匀。

          简单指散列函数的计算简单快速;
          均匀指对于关键字集合中的任一关键字,散列函数能以等概率将其映射到表空间的任何一个位置上。也就是说,散列函数能将子集K随机均匀地分布在表的地址集{0,1,…,m-1}上,以使冲突最小化。

    2、常用散列函数
          为简单起见,假定关键字是定义在自然数集合上。

    (1)平方取中法
          具体方法:先通过求关键字的平方值扩大相近数的差别,然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的每一位都相关,所以由此产生的散列地址较为均匀。
        【例】将一组关键字(0100,0110,1010,1001,0111)平方后得
         (0010000,0012100,1020100,1002001,0012321)
        若取表长为1000,则可取中间的三位数作为散列地址集:
         (100,121,201,020,123)。
    相应的散列函数用C实现很简单:
    int Hash(int key){ //假设key是4位整数
       key*=key; key/=100; //先求平方值,后去掉末尾的两位数
       return key%1000; //取中间三位数作为散列地址返回
    }

    (2)除余法

          该方法是最为简单常用的一种方法。它是以表长m来除关键字,取其余数作为散列地址,即 h(key)=key%m
          该方法的关键是选取m。选取的m应使得散列函数值尽可能与关键字的各位相关。m最好为素数。
        【例】若选m是关键字的基数的幂次,则就等于是选择关键字的最后若干位数字作为地址,而与高位无关。于是高位不同而低位相同的关键字均互为同义词。
        【例】若关键字是十进制整数,其基为10,则当m=100时,159,259,359,…,等均互为同义词。

    (3)相乘取整法
          该方法包括两个步骤:首先用关键字key乘上某个常数A(0<A<1),并抽取出key.A的小数部分;然后用m乘以该小数后取整。即:
              
          该方法最大的优点是选取m不再像除余法那样关键。比如,完全可选择它是2的整数次幂。虽然该方法对任何A的值都适用,但对某些值效果会更好。Knuth建议选取
                  
          该函数的C代码为:
    int Hash(int key){
       double d=key *A; //不妨设A和m已有定义
       return (int)(m*(d-(int)d));//(int)表示强制转换后面的表达式为整数
    }

    (4)随机数法
          选择一个随机函数,取关键字的随机函数值为它的散列地址,即
              h(key)=random(key)
        其中random为伪随机函数,但要保证函数值是在0到m-1之间。

    处理冲突的方法

          通常有两类方法处理冲突:开放定址(Open Addressing)法和拉链(Chaining)法。前者是将所有结点均存放在散列表T[0..m-1]中;后者通常是将互为同义词的结点链成一个单链表,而将此链表的头指针放在散列表T[0..m-1]中。

    1、开放定址法
    (1)开放地址法解决冲突的方法
          用开放定址法解决冲突的做法是:当冲突发生时,使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找,直到找到给定的关键字,或者碰到一个开放的地址(即该地址单元为空)为止(若要插入,在探查到开放的地址,则可将待插入的新结点存人该地址单元)。查找时探查到开放的地址则表明表中无待查的关键字,即查找失败。
      注意:
    ①用开放定址法建立散列表时,建表前须将表中所有单元(更严格地说,是指单元中存储的关键字)置空。
    ②空单元的表示与具体的应用相关。
    【例】关键字均为非负数时,可用"-1"来表示空单元,而关键字为字符串时,空单元应是空串。
          总之:应该用一个不会出现的关键字来表示空单元。

    (2)开放地址法的一般形式
          开放定址法的一般形式为: hi=(h(key)+di)%m 1≤i≤m-1
    其中:
          ①h(key)为散列函数,di为增量序列,m为表长。
          ②h(key)是初始的探查位置,后续的探查位置依次是hl,h2,…,hm-1,即h(key),hl,h2,…,hm-1形成了一个探查序列。
          ③若令开放地址一般形式的i从0开始,并令d0=0,则h0=h(key),则有:
               hi=(h(key)+di)%m 0≤i≤m-1
            探查序列可简记为hi(0≤i≤m-1)。

    (3)开放地址法堆装填因子的要求
          开放定址法要求散列表的装填因子α≤l,实用中取α为0.5到0.9之间的某个值为宜。

    (4)形成探测序列的方法
          按照形成探查序列的方法不同,可将开放定址法区分为线性探查法、二次探查法、双重散列法等。
    ①线性探查法(Linear Probing)
    该方法的基本思想是:

          将散列表T[0..m-1]看成是一个循环向量,若初始探查的地址为d(即h(key)=d),则最长的探查序列为:
             d,d+l,d+2,…,m-1,0,1,…,d-1
          即:探查时从地址d开始,首先探查T[d],然后依次探查T[d+1],…,直到T[m-1],此后又循环到T[0],T[1],…,直到探查到T[d-1]为止。

    探查过程终止于三种情况:
          (1)若当前探查的单元为空,则表示查找失败(若是插入则将key写入其中);
          (2)若当前探查的单元中含有key,则查找成功,但对于插入意味着失败;
          (3)若探查到T[d-1]时仍未发现空单元也未找到key,则无论是查找还是插入均意味着失败(此时表满)。

    利用开放地址法的一般形式,线性探查法的探查序列为:
             hi=(h(key)+i)%m 0≤i≤m-1 //即di=i

    利用线性探测法构造散列表
        【例9.1】已知一组关键字为(26,36,41,38,44,15,68,12,06,51),用除余法构造散列函数,用线性探查法解决冲突构造这组关键字的散列表。
      解答:为了减少冲突,通常令装填因子α<l。这里关键字个数n=10,不妨取m=13,此时α≈0.77,散列表为T[0..12],散列函数为:h(key)=key%13。
          由除余法的散列函数计算出的上述关键字序列的散列地址为(0,10,2,12,5,2,3,12,6,12)。
          前5个关键字插入时,其相应的地址均为开放地址,故将它们直接插入T[0],T[10),T[2],T[12]和T[5]中。
          当插入第6个关键字15时,其散列地址2(即h(15)=15%13=2)已被关键字41(15和41互为同义词)占用。故探查h1=(2+1)%13=3,此地址开放,所以将15放入T[3]中。
          当插入第7个关键字68时,其散列地址3已被非同义词15先占用,故将其插入到T[4]中。
          当插入第8个关键字12时,散列地址12已被同义词38占用,故探查hl=(12+1)%13=0,而T[0]亦被26占用,再探查h2=(12+2)%13=1,此地址开放,可将12插入其中。
          类似地,第9个关键字06直接插入T[6]中;而最后一个关键字51插人时,因探查的地址12,0,1,…,6均非空,故51插入T[7]中。
          构造散列表的具体过程【动画演示


    聚集或堆积现象
          用线性探查法解决冲突时,当表中i,i+1,…,i+k的位置上已有结点时,一个散列地址为i,i+1,…,i+k+1的结点都将插入在位置i+k+1上。把这种散列地址不同的结点争夺同一个后继散列地址的现象称为聚集或堆积(Clustering)。这将造成不是同义词的结点也处在同一个探查序列之中,从而增加了探查序列的长度,即增加了查找时间。若散列函数不好或装填因子过大,都会使堆积现象加剧。

    这也佐证了 上文中提出的在 开放寻址中装载因子尤其不能大于1(而 链接法时允许大于1的)。装载因子小于1,就是要求可用的槽(slot)的数目应该大于key的数目。但是他不像连接法那样需要存储指针,所以在规模较小时优先选用 开放寻址法。
      
    【例】上例中,h(15)=2,h(68)=3,即15和68不是同义词。但由于处理15和同义词41的冲突时,15抢先占用了T[3],这就使得插入68时,这两个本来不应该发生冲突的非同义词之间也会发生冲突。
          为了减少堆积的发生,不能像线性探查法那样探查一个顺序的地址序列(相当于顺序查找),而应使探查序列跳跃式地散列在整个散列表中。

    ②二次探查法(Quadratic Probing)
         二次探查法的探查序列是:
              hi=(h(key)+i*i)%m 0≤i≤m-1 //即di=i2
       即探查序列为d=h(key),d+12,d+22,…,等。
          该方法的缺陷是不易探查到整个散列空间。

    ③双重散列法(Double Hashing)
          该方法是开放定址法中最好的方法之一,它的探查序列是:
            hi=(h(key)+i*h1(key))%m 0≤i≤m-1 //即di=i*h1(key)
          即探查序列为:
            d=h(key),(d+h1(key))%m,(d+2h1(key))%m,…,等。
        该方法使用了两个散列函数h(key)和h1(key),故也称为双散列函数探查法。
    注意:
          定义h1(key)的方法较多,但无论采用什么方法定义,都必须使h1(key)的值和m互素,才能使发生冲突的同义词地址均匀地分布在整个表中,否则可能造成同义词地址的循环计算。
      【例】 若m为素数,则h1(key)取1到m-1之间的任何数均与m互素,因此,我们可以简单地将它定义为:
                    h1(key)=key%(m-2)+1
      【例】对例9.1,我们可取h(key)=key%13,而h1(key)=key%11+1。
      【例】若m是2的方幂,则h1(key)可取1到m-1之间的任何奇数。

    2、拉链法
    (1)拉链法解决冲突的方法
          拉链法解决冲突的做法是:将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m,则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点,均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中,装填因子α可以大于1,但一般均取α≤1。

    【例9.2】已知一组关键字和选定的散列函数和例9.1相同,用拉链法解决冲突构造这组关键字的散列表。
      解答:不妨和例9.1类似,取表长为13,故散列函数为h(key)=key%13,散列表为T[0..12]。
    注意:
          当把h(key)=i的关键字插入第i个单链表时,既可插入在链表的头上,也可以插在链表的尾上。这是因为必须确定key不在第i个链表时,才能将它插入表中,所以也就知道链尾结点的地址。若采用将新关键字插入链尾的方式,依次把给定的这组关键字插入表中,则所得到的散列表如下图所示。

    (2)拉链法的优点
          与开放定址法相比,拉链法有如下几个优点:
      (1)拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;
      (2)由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;
      (3)开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;
      (4)在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表,删除结点不能简单地将被删结点的空间置为空,否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中,空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点。

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


    散列表上的运算

          散列表上的运算有查找、插入和删除。其中主要是查找,这是因为散列表的目的主要是用于快速查找,且插入和删除均要用到查找操作。

    1、散列表类型说明:
    #define NIL -1 //空结点标记依赖于关键字类型,本节假定关键字均为非负整数
    #define M 997 //表长度依赖于应用,但一般应根据。确定m为一素数
    typedef struct{ //散列表结点类型
       KeyType key;
       InfoType otherinfo; //此类依赖于应用
    }NodeType;
    typedef NodeType HashTable[m]; //散列表类型

    2、基于开放地址法的查找算法
          散列表的查找过程和建表过程相似。假设给定的值为K,根据建表时设定的散列函数h,计算出散列地址h(K),若表中该地址单元为空,则查找失败;否则将该地址中的结点与给定值K比较。若相等则查找成功,否则按建表时设定的处理冲突的方法找下一个地址。如此反复下去,直到某个地址单元为空(查找失败)或者关键字比较相等(查找成功)为止。

    (1)开放地址法一般形式的函数表示
       int Hash(KeyType k,int i)
        { //求在散列表T[0..m-1]中第i次探查的散列地址hi,0≤i≤m-1
         //下面的h是散列函数。Increment是求增量序列的函数,它依赖于解决冲突的方法
          return(h(K)+Increment(i))%m; //Increment(i)相当于是di
        }
         若散列函数用除余法构造,并假设使用线性探查的开放定址法处理冲突,则上述函数中的h(K)和Increment(i)可定义为:
       int h(KeyType K){ //用除余法求K的散列地址
         return K%m;
       }

       int Increment(int i){//用线性探查法求第i个增量di
         return i; //若用二次探查法,则返回i*i
        }

    (2)通用的开放定址法的散列表查找算法:
    int HashSearch(HashTable T,KeyType K,int *pos)
       { //在散列表T[0..m-1]中查找K,成功时返回1。失败有两种情况:找到一个开放地址
         //时返回0,表满未找到时返回-1。 *pos记录找到K或找到空结点时表中的位置
         int i=0; //记录探查次数
         do{
          *pos=Hash(K,i); //求探查地址hi
          if(T[*pos].key==K) return l; //查找成功返回
          if(T[*pos].key==NIL) return 0;//查找到空结点返回
         }while(++i<m) //最多做m次探查
         return -1; //表满且未找到时,查找失败
       } //HashSearch

    注意:
          上述算法适用于任何开放定址法,只要给出函数Hash中的散列函数h(K)和增量函数Increment(i)即可。但要提高查找效率时,可将确定的散列函数和求增量的方法直接写入算法HashSearch中,相应的算法【参见习题】。

    3、基于开放地址法的插入及建表
          建表时首先要将表中各结点的关键字清空,使其地址为开放的;然后调用插入算法将给定的关键字序列依次插入表中。
          插入算法首先调用查找算法,若在表中找到待插入的关键字或表已满,则插入失败;若在表中找到一个开放地址,则将待插入的结点插入其中,即插入成功。
       void Hashlnsert(HashTable T,NodeTypene w)
        { //将新结点new插入散列表T[0..m-1]中
         int pos,sign;
         sign=HashSearch(T,new.key,&pos); //在表T中查找new的插入位置
         if(!sign) //找到一个开放的地址pos
           T[pos]=new; //插入新结点new,插入成功
         else //插人失败
          if(sign>0)
            printf("duplicate key!"); //重复的关键字
          else //sign<0
            Error("hashtableoverflow!"); //表满错误,终止程序执行
        } //Hashlnsert

       void CreateHashTable(HashTable T,NodeType A[],int n)
        { //根据A[0..n-1]中结点建立散列表T[0..m-1]
         int i
         if(n>m) //用开放定址法处理冲突时,装填因子α须不大于1
           Error("Load factor>1");
         for(i=0;i<m;i++)
           T[i].key=NIL; //将各关键字清空,使地址i为开放地址
         for(i=0;i<n;i++) //依次将A[0..n-1]插入到散列表T[0..m-1]中
           Hashlnsert(T,A[i]);
        } //CreateHashTable

    4、删除
          基于开放定址法的散列表不宜执行散列表的删除操作。若必须在散列表中删除结点,则不能将被删结点的关键字置为NIL,而应该将其置为特定的标记DELETED。
          因此须对查找操作做相应的修改,使之探查到此标记时继续探查下去。同时也要修改插人操作,使其探查到DELETED标记时,将相应的表单元视为一个空单元,将新结点插入其中。这样做无疑增加了时间开销,并且查找时间不再依赖于装填因子。
          因此,当必须对散列表做删除结点的操作时,一般是用拉链法来解决冲突。
    注意:
          用拉链法处理冲突时的有关散列表上的算法【参见练习】。

    5、性能分析
          插入和删除的时间均取决于查找,故下面只分析查找操作的时间性能。
          虽然散列表在关键字和存储位置之间建立了对应关系,理想情况是无须关键字的比较就可找到待查关键字。但是由于冲突的存在,散列表的查找过程仍是一个和关键字比较的过程,不过散列表的平均查找长度比顺序查找、二分查找等完全依赖于关键字比较的查找要小得多。

    (1)查找成功的ASL
          散列表上的查找优于顺序查找和二分查找。
      【例】在例9.1和例9.2的散列表中,在结点的查找概率相等的假设下,线性探查法和拉链法查找成功的平均查找长度分别为:
            ASL=(1×6+2×2+3×l+9×1)/10=2.2 //线性探查法
            ASL=(1×7+2×2+3×1)/10=1.4 //拉链法
      而当n=10时,顺序查找和二分查找的平均查找长度(成功时)分别为:
            ASL=(10+1)/2=5.5 //顺序查找
            ASL=(1×l+2×2+3×4+4×3)/10=2.9 //二分查找,可由判定树求出该值

    (2) 查找不成功的ASL
          对于不成功的查找,顺序查找和二分查找所需进行的关键字比较次数仅取决于表长,而散列查找所需进行的关键字比较次数和待查结点有关。因此,在等概率情况下,也可将散列表在查找不成功时的平均查找长度,定义为查找不成功时对关键字需要执行的平均比较次数。
      【例】例9.1和例9.2的散列表中,在等概率情况下,查找不成功时的线性探查法和拉链法的平均查找长度分别为:
           ASLunsucc=(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=59/13≈4.54
           ASLunsucc=(1+0+2+1+0+1+1+0+0+0+1+0+3)/13≈10/13≈0.77

     原文地址:http://blog.chinaunix.net/uid-20791902-id-291979.html

    展开全文
  • 关于散列表的大小设定

    千次阅读 2018-11-28 18:55:07
    数据库课上老师提出的问题,大意是给一个集合S,给一个散列函数和相应的散列表,长为m,从S映射到表,问 使得给一个x,通过散列表判断其不在S中的概率小于0.05,这个m该是多少? 老师说这个问题是美国大学生都会证的...

    数据库课上老师提出的问题,大意是给一个集合S,给一个散列函数和相应的散列表,长为m,从S映射到表,问 使得给一个x,通过散列表判断其不在S中的概率小于0.05,这个m该是多少?
    老师说这个问题是美国大学生都会证的问题,这也是中国大学生研究生缺乏的思考能力。
    我完全没头绪。。只是在想这跟m有什么关系,下课后也没找到合适的资料。这里整理一下我查到的一些关于哈希表的长度设定问题的英文资料和机翻。
    想看知识点的直接翻到最后即可。

    USCD_EDU

    http://cseweb.ucsd.edu/~kube/cls/100/Lectures/lec16/lec16-8.html
    Hash table size

    • By “size” of the hash table we mean how many slots or buckets it has [ 哈希表的“大小”是指它有多少个槽或桶]

    • Choice of hash table size depends in part on choice of hash function, and collision resolution strategy [ 散列表大小的选择部分取决于散列函数的选择和冲突解决策略]

    • But a good general “rule of thumb” is: [ 但一个好的一般“经验法则”是:]
      The hash table should be an array with length about 1.3 times the maximum number of keys that will actually be in the table, and [ 哈希表应该是一个数组,其长度约为表中实际存在的最大键数的1.3倍]

    • Size of hash table array should be a prime number [ 哈希表数组的大小应该是素数]

    • So, let M = the next prime larger than 1.3 times the number of keys you will want to store in the table, and create the table as an array of length M [ 因此,让M =下一个素数大于您想要存储在表中的键数的1.3倍,并将表创建为长度为M的数组]

    • (If you underestimate the number of keys, you may have to create a larger table and rehash the entries when it gets too full; if you overestimate the number of keys, you will be wasting some space) [ (如果你低估了键的数量,你可能需要创建一个更大的表,并在条目太满时重新输入条目;如果你高估了键的数量,你将浪费一些空间)]

    How is the size of a hash table determined How should optimization be done for it to be fast?

    https://www.quora.com/How-is-the-size-of-a-hash-table-determined-How-should-optimization-be-done-for-it-to-be-fast

    • HOW

    It’s a tuning parameter - it depends what you’re trying to optimize and what resources you have or are willing to commit but thinking performance will be proportional to average collision chain length is the right thing to be managing. [ 这是一个调整参数 - 它取决于您要优化的内容以及您拥有或愿意承诺的资源,但思考性能与平均冲突链长度成正比是正确的管理方式。]

    I don’t know what your application is but assuming you optimize collision handling 3-4 chains will be blisteringly fast on any modern laptop (up). [ 我不知道您的应用程序是什么,但假设您优化了碰撞处理3-4链条在任何现代笔记本电脑上都会非常快(上)。] If you’re on a phone or smaller device you might find this is more of a size/speed trade-off. [ 如果您使用的是手机或小型设备,您可能会发现这更多的是尺寸/速度权衡。]

    It’s a common myth for this kind of hash-table that you should pick a prime number but because your hash value has a tendency to have a fixed remainder modulo 33 you should pick something co-prime with 33. [ 对于这种哈希表来说,你应该选择素数是一个常见的神话,但是因为你的哈希值有一个固定余数模33的倾向,你应该选择一个33的共同素数。]

    A smart choice is a power of 2. [ 聪明的选择是2的力量。] That’s because you can obtain the remainder by masking bits with & and avoid a (relatively) costly / implicit in your %. [ 那是因为你可以通过用&屏蔽位来获得余数,并避免在你的%中(相对)代价高昂/隐含。]

    NB: A side-effect of using powers of 2 is that it’s easy to divide or combine collision chains if you resize the table dynamically. [ 注意:使用2的幂的副作用是,如果动态调整表的大小,则很容易划分或组合碰撞链。] However I get the impression you have a static dictionary and won’t be re-sizing. [ 但是我得到的印象是你有一个静态字典,不会重新调整大小。]

    • Optimized? [ 优化?]

    First, make sure you retain the full hash (an unsigned 32-bit int will be likely suitable). [ 首先,确保保留完整的哈希值(无符号的32位int可能是合适的)。]
    Second when traversing a collision chain compare hash before value. [ 第二,当遍历碰撞链时比较值之前的散列。] If the hashes don’t match you don’t need a (relatively) expensive string comparison. [ 如果散列不匹配,则不需要(相对)昂贵的字符串比较。]
    The hash you’ve chosen is known to have good performance with English text you should find few if any collisions at full 32-bit hash comparison and make next to zero failed string comparisons. [ 您已选择的哈希已知具有良好的英文文本性能,如果在完全32位哈希比较中发生任何冲突,则应该找到很少,并且接下来的零字符串比较失败。]

    Third consider ordering the collision chain. [ 第三,考虑订购碰撞链。] If access is random order it by hash value. [ 如果访问是随机的,则按哈希值排序。]
    That way you can dive out of a chain when you realize the look-up value can’t be held. [ 这样,当您意识到无法保持查找值时,您可以跳出链条。]

    Alternatively if access isn’t random consider ordering the collision chains by a static or dynamic frequency. [ 或者,如果访问不是随机的,则考虑通过静态或动态频率对碰撞链进行排序。] Static frequency would be based on occurrence of a word in some text “corpus”. [ 静态频率将基于某些文本“语料库”中单词的出现。] That is you’d want ‘the’ to appear at the front of its collision chain and ‘wayzgoose’ likely towards the end! [ 那就是你希望’the’出现在它碰撞链的前面,并且’wayzgoose’可能会到达终点!]
    Dynamic frequency would involve moving words that are ‘hit’ to the front of their collision chain knowing words recur in a given text. [ 动态频率将涉及将“击中”的单词移动到其碰撞链的前面,知道单词在给定文本中重复出现。]

    If you are writing a spell checker (and I’ve somewhat assumed that’s the application) I really do recommend finding a corpus. [ 如果你正在写一个拼写检查器(我有点认为这是应用程序)我真的建议找一个语料库。] It doesn’t even have to be very big because (of course) the common words are common and will sort to the front very quickly and even if the ‘uncommon’ words aren’t optimized - they have less impact because they’re uncommon! [ 它甚至不必非常大,因为(当然)常见的词很常见并且会很快排在前面,即使“不常见”的词语没有被优化 - 它们的影响也很小,因为它们并不常见!]

    PS: I also know a practically perfect (in the formal sense) hash for English words however I think you’ll find your hash is pretty good. [ PS:我也知道一个几乎完美的(在正式意义上)英语单词的哈希,但我想你会发现你的哈希非常好。]

    总结

    1. 散列表的大小的选择部分取决于散列函数的选择和冲突解决的策略

    2. 其实讨论的是平衡性能与平均冲突长度平衡性能与平均冲突长度
      一般情况下,越短搜的越快越省空间,但相应冲突机会就越大(散列函数影响力更大)

    3. 处理碰撞是非常重要的一环,比散列表的大小重要多了。

    4. 经验:

    • 约为表中实际存在的最大的键值的1.3倍
    • 素数
    • 使用2的幂也是个方法,好处是可以通过直接位操作降低代价;坏处是:如果需要动态调整表的大小,很容对碰撞链进行划分或者合并。
    1. 其实最后也没解决关于概率,证明这些的原问题,不过总感觉老师说的是散列、碰撞那些的概率。。可能我没听清,当然不排除老师口误了哈哈哈。
    展开全文
  • 1.采用散列表技术需要考虑的两个主要问题 (1)散列函数的设计。如何设计一个简单、均匀 、存储利用率高的散列函数。 (2)冲突的处理。如何采取合适的处理冲突方法来解决冲突。 2.散列函数的设计 (1)基本原则: a...

    1.采用散列表技术需要考虑的两个主要问题

    (1)散列函数的设计。如何设计一个简单、均匀 、存储利用率高的散列函数。
    (2)冲突的处理。如何采取合适的处理冲突方法来解决冲突。

    2.散列函数的设计

    (1)基本原则:
    a.计算简单。散列函数不应该有很大的计算量,否则会降低查找效率。
    b.函数值即散列地址分布均匀。函数值要尽量均匀散步在地址空间,这样才能保证存储空间的有效利用,并减少冲突。

    (2)集中常见的散列函数:

    a.直接定址法
    直接定址法 f(key) = a * key + b(a、b为常数)。
     取关键字的某个线性函数值为散列地址。(这样的散列函数简单、均匀、不会产生冲突;需要事先知道关键字的分布情况,适合查找表较小且连续的情况,较少使用)
    b.除留余数法
    此方法为最常用的构造散列函数的方法。对于散列表长为m的散列函数公式为:f(key) = key mod p(p≤m)
    这种方法不仅可以对关键字直接取模,也可在折叠、平方取中后再取模。散列表长为m,通常p为小于或等于表长(最好接近m)的最小质数或不包含小于20质因子的合数。
    c.数字分析法
      抽取关键字的一部分来计算散列函数位置的方法。适合处理关键字位数比较大的情况,(如果事先知道关键字的分布且关键字的若干位分布比较均匀,就可以考虑用这个方法。)
    d.平方取中法
      计算关键字的平方,再取中间几位做为关键字。eg:1234,平方1522756,取中间3为227为关键字。(平方取中法比较适合不知道关键字的分布,而位数又不是很大的情况。)
    e.折叠法
      将关键字从左到右分割成位数相等的几部分,然后将这几部分叠加求和,并按散列表表长,取后几位作为散列表地址。(折叠法事先不需要知道关键字的分布,适合关键字位数较多的情况。)

    3.处理冲突的方法

    (1)开放定址法
      一旦发生了冲突,就去寻找下一个空的散列地址,知道散列表足够大,空的散列表地址总能找到,并将记录存入。这种解决冲突的开放定址发称为线性探测法。
      fi(key) = (f(key) + di) MOD m (di = 1,2,3,…,m-1)
    在发生冲突进行重新定址的过程中会导致后面不是同义词的关键字( f(keyi) ≠ f(key2) )争夺一个地址的情况,这种现象为堆积。

    线性探测都是发生冲突后加上一个di然后取余数来寻找下一个空间地址,如果发生冲突的位置之前就有一个空位置,要找到这个空位置要循环效率就很低
      fi(key) = (f(key) + di) MOD m (di = 12,-12,22,…,q2,-q^2,q≤m/2)
    增加平方运算的目的是为了不让关键字都聚集在某一块区域,这种方法叫做二次探测法。

    在冲突时,对于位移量di采用随机函数计算得到。
      fi(key) = (f(key) + di) MOD m (di 是一个伪随机数列) 。 伪随机,只要随机种子相同,每次得到的数列都会是相同的。这就是随机探测法 。

    (2)拉链法(链地址法)

    为了解决线性探测实现哈希表时出现哈希冲突后导致数据堆聚的现象,我们采取了另一种结构来处理哈希冲突,哈希桶(拉链法),拉链法解决冲突的做法是将所有通过哈希函数计算出来的哈希地址相同的结点存放在一个单链表之中。
    实现原理就是将哈希表定义为一个由N个头指针组成的指针数组,经过哈希函数计算得到的哈希地址相同的数据全部连在对于的头指针下面。它继承了数组的易于查找和链表便于删除插入的特点。哈希桶的实现(拉链法)

    参考

    https://blog.csdn.net/MBuger/article/details/62418754
    https://www.cnblogs.com/meihao1203/p/9277399.html

    展开全文
  • 散列表

    千次阅读 2019-08-11 13:00:11
    文章目录散列表概念散列表主要两个问题散列函数的构造处理冲突的方法散列表的查找完整代码:运行结果: 散列表概念 散列函数和散列地址:类似于函数y=f(x),给定一个x,能得到一个y。散列函数,给定一个关键字,可以...
  • 散列表解释

    2017-02-12 10:16:20
    散列表(也叫哈希表)是一种查找算法,与链表、树等算法不同的是,散列表算法在查找时不需要进行一系列和关键字(关键字是数据元素中某个数据项的值,用以标识一个数据元素)的比较操作。 散列表算法希望能尽量...
  • 不用链表的散列表分离链接法的缺点使用了一些链表。给新单元分配地址需要时间,导致算法的速度会有些慢,同时算法还要求对第二种数据结构的实现。 而,不用链表解决冲突的方法是:尝试另外的单元,直到找到空的单元...
  • 散列表 基本概念

    千次阅读 2016-06-17 09:27:50
    散列表 散列表 又叫 哈希表 (hash table)。通过访问key而直接访问存储的value值。它的key - value之间存在一个映射函数,我们可以通过key值和“看不到”的映射函数(散列函数)访问对应的value值。这加快...
  • 哈希表(散列表)原理详解

    万次阅读 多人点赞 2016-06-03 15:23:19
    哈希表(散列表)原理详解
  • 散列表查找实现

    2019-06-12 09:47:43
    1.散列表查找算法实现 首先是需要定义一个散列表的结构和一些相关的函数。其中HashTable就是散列表结构,结构当中的elem为一个动态数组。 #define SUCCESS 1 #define UNSUCCESS 0 #define HASHSIZE 12 //定义...
  • 散列表类的C++实现(探测散列表)...
  • 散列表用链表数组实现。每个列表被称为桶。将元素放入散列表中,首先要计算该元素的散列码(hashcode),然后与桶的数目取余,所得到的结果就是保存这个元素的索引,具有相同索引(散列值)的元素放入一个桶内,串联...
  • 散列表类的C++实现(分离链接散列表)
  • 散列表和链表,经常会被放在一起使用,在链表那一节,我们讲到,LRU淘汰算法的时间复杂度是O(n),当时我也提到,通过散列表可以将这个时间复杂度降低到O(1)。 跳表那一节,我提到Redis的有序集合是使用跳表来实现了...
  • 散列表习题

    2020-06-15 12:20:16
    1、 考虑key的集合S = {0, 8, 16,...2、散列表的规模是素数,用开放定址+平方试探法排解冲突,若要保证新的词条能够顺利插入,散列表的装填因子不能超过(请填十进制小数) 0.5 3、对[0, 11)中的整数{ 10, 4, 2, 9, 3,
  • golang--算法--散列表&字符串

    千次阅读 2020-01-12 21:51:16
    关于散列表和字符串的 4 个必知必会的代码实现 散列表 实现一个基于链表法解决冲突问题的散列表 实现一个 LRU 缓存淘汰算法 字符串 实现一个字符集,只包含 a~z 这 26 个英文字母的 Trie 树 实现朴素的字符串...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 77,748
精华内容 31,099
关键字:

关于散列表