哈希表】 哈希表的表长怎么算

2022-01-14 18:27发布

3条回答
上来打杂的
2楼 · 2022-01-21 15:52

哈希表的长度一般是定长的,在存储数据之前我们应该知道我们存储的数据规模是多大,应该尽可能地避免频繁地让哈希表扩容。但是如果设计的太大,那么就会浪费空间,因为我们跟不用不到那么大的空间来存储我们当前的数据规模;如果设计的太小,那么就会很容易发生哈希冲突,体现不出哈希表的效率。所以,我们设计的哈希表的大小,必须要做到尽可能地减小哈希冲突,并且也要尽可能地不浪费空间,选择合适的哈希表的大小是提升哈希表性能的关键。


当我们选择哈希函数的时候,经常会选择除留余数法,即用存储数据的key值除以哈希表的总长度,得到的余数就是它的哈希值。常识告诉我们,当一个数除以一个素数的时候,会产生最分散的余数。由于我们通常使用表的大小对哈希函数的结果进行模运算,如果表的大小是一个素数,那么这样我们就会尽可能地产生分散的哈希值。




我是大脸猫
3楼 · 2022-01-17 11:06

哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。


哈希表的做法其实很简单,就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里。


散列方法不同于顺序查找、二分查找、二叉排序树及B-树上的查找。它不以关键字的比较为基本操作,采用直接寻址技术。在理想情况下,无须任何比较就可以找到待查关键字,查找的期望时间为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

           

      该方法最大的优点是选取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之间。


(5)直接定址法

     这需要事先知道关键字的分布情况,适合查找表较小且连续的情况!



处理冲突的方法 



      通常有两类方法处理冲突:开放定址(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),用除余法构造散列函数,用线性探查法解决冲突构造这组关键字的散列表。

  解答:为了减少冲突,通常令装填因子α

      由除余法的散列函数计算出的上述关键字序列的散列地址为(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)。这将造成不是同义词的结点也处在同一个探查序列之中,从而增加了探查序列的长度,即增加了查找时间。若散列函数不好或装填因子过大,都会使堆积现象加剧。

  【例】上例中,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)拉链法的缺点

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


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

     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

       T[i].key=NIL; //将各关键字清空,使地址i为开放地址

     for(i=0;i

       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

注意:

      ①由同一个散列函数、不同的解决冲突方法构造的散列表,其平均查找长度是不相同的。

      ②散列表的平均查找长度不是结点个数n的函数,而是装填因子α的函数。因此在设计散列表时可选择α以控制散列表的平均查找长度。

      ③ α的取值

      α越小,产生冲突的机会就小,但α过小,空间的浪费就过多。只要α选择合适,散列表上的平均查找长度就是一个常数,即散列表上查找的平均时间为O(1)。

      ④ 散列法与其他查找方法的区别

除散列法外,其他查找方法有共同特征为:均是建立在比较关键字的基础上。其中顺序查找是对无序集合的查找,每次关键字的比较结果为"="或"!="两种可能,其平均时间为O(n);其余的查找均是对有序集合的查找,每次关键字的比较有"="、"<"和">"三种可能,且每次比较后均能缩小下次的查找范围,故查找速度更快,其平均时间为O(lgn)。而散列法是根据关键字直接求出地址的查找方法,其查找的期望时间为O(1)。 



确保哈希表长度是一个素数,这样会产生最分散的余数,尽可能减少哈希冲突 设计好哈希表装填因子,一般控制在0.7-0.8 确认我们的数据规模,如果确认了数据规模,可以将数据规模除以装填因子,根据这个结果来寻找一个可行的哈希表大小 当数据规模可能会动态变化,不确定的时候,这个时候我们也需要能够根据数据规模的变化来动态给我们的哈希表扩容,所以一开始需要自己确定一个哈希表的大小作为基数,然后在此基础上达到装填因子规模时对哈希表进行扩容

相关问题推荐

  • 回答 4

    这个主要是看你数组的长度是多少, 比如之前写过的一个程序有个数组存的是各个客户端的ip地址:string clientIp[4]={XXX, xxx, xxx, xxx};这个时候如果想把hash值对应到上面四个地址的话,就应该对4取余,这个时候p就应该为4...

  • 回答 6

     哈希表的大小 · 关键字的分布情况 · 记录的查找频率 1.直接寻址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b,其中a和b为常数(这种散列函数叫做自身函数)。...

  • 回答 6

    哈希表的大小取决于一组质数,原因是在hash函数中,你要用这些质数来做模运算(%)。而分析发现,如果不是用质数来做模运算的话,很多生活中的数据分布,会集中在某些点上。所以这里最后采用了质数做模的除数。 因为用质数做了模的除数,自然存储空间的大小也用质数了...

  • 回答 2

    是啊,哈希函数的设计至关重要,好的哈希函数会尽可能地保证计算简单和散列地址分布均匀,但是,我们需要清楚的是,数组是一块连续的固定长度的内存空间

  • 回答 3

     解码查表优化算法,seo优化

  • 回答 5

    1.对对象元素中的关键字(对象中的特有数据),进行哈希算法的运算,并得出一个具体的算法值,这个值 称为哈希值。2.哈希值就是这个元素的位置。3.如果哈希值出现冲突,再次判断这个关键字对应的对象是否相同。如果对象相同,就不存储,因为元素重复。如果对象不同,就...

  • 回答 2

    一般情况确实不应该用地址来作为删除的参数,但如果你已经事先搜索到了一个元素但之后不用了不就可以

  • 回答 2

    哈希表是散列的一种。散列是一种用以常数平均时间执行插入、删除和查找的技术。 为了得到更快的执行速度,当查询某个元素多于遍历时可使用。但是数组无法确定准确的位置

  • 回答 3

    跟加载因子设置的大小有关

  • 回答 2

    虽然哈希表和数组在 lua 里都表示为一个 table,但是其底层实现还是有所区别的,理想情况下哈希表的内存占用是数组的两倍,主要区别在于哈希节点比数组节点多了一个 TKey 的内存占用。在数据量大的情况下考虑使用数组可以有效减少内存...

  • 回答 5

    我们知道,数据结构的物理存储结构只有两种:顺序存储结构和链式存储结构(像栈,队列,树,图等是从逻辑结构去抽象的,映射到内存中,也这两种物理组织形式),在数组中根据下标查找某个元素,一次定位就可以达到,哈希表利用了这种特性,哈希表的主干就是数...

  • 回答 4

    哈希表可以理解为一维数组。因为只是单一的坐标。当然如果考虑到哈希碰撞,理解为二维数组也无不可。至于下标1跟10001,这个问题很好。你观察到了,这样的数组会有大量的空洞。这是一种常见的现象。一维的这种数组叫做稀疏数组,二维的这种数组叫做稀疏矩阵。...

  • 回答 3

    在数据结构哈希表中不成功平均查找长度和成功平均查找长度之间并没有什么直接的关系。他们都是对于特定的哈希表和特定的查找序列,才有意义的。

  • 回答 3

    查找不成功的次数表如下表所示 Key 7 8 30 11 18 9 14 Count 3 2 1 2 1 5  所以ASLunsuccess= (3+2+1+2+1+5+4)/ 7 = 18/7。 下面看下2010年2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题中一个考...

  • 回答 9

    A--->function()---> B源数据A经过function()的运算得到B.这里的function()就是哈希函数,它是某一种hash算法的实现。得到的数据B就是hashCode,它是源数据A的哈希体现。如果我们将A->B这样的的关系保存下来,存储这个对应关系的我们称为哈希表。补充:还是正...

没有解决我的问题,去提问