TELKOM NIKA , Vol. 11, No. 6, June 20 13, pp. 3220  ~ 322 7   e-ISSN: 2087 -278X           3220      Re cei v ed  Jan uary 13, 201 3 ;  Revi sed Ap ril 6, 2013; Accepte d  April 2 2 , 2013   A Dynamic Hashing Algorithm Suitable for Embedded  System      Li Jian w e i * , Chen  Huijie  Schoo l of Com puter Scie nce  and T e chno log y , T a i y u an Un i v ersit y  of Sci e n c e and T e chno log y   T a iyua n, Chin a   *Corres p o ndi n g  author, e-ma i l : ghho ng 200 4 @ 16 3.com*, chen hui jie 66 6@ 163.com       A b st r a ct   With the incr ea sing  of the d a ta nu mbers, the  lin ear  h a sh ing  w ill be  a l o t of overflow  bl ock s  resu l t   from  Data sk e w  and th e i n d e x  si z e   of exte n d ibl e   has h  w ill  surge  so  as to  w a ste too  mu ch  me mory. T h is   lead to the above two Typic a l Dy nam i c  hashing algor ithm  don ’ t s u it able for embedded system  that  nee d  certain r eal-ti m e req u ire m ents  and  me mory r e sourc e s are   v e ry scarce. T o  solve th is pr o b le m, this  pa p e r  w a s propose d  a dyna mic  hash i ng a l g o ri thm suit abl e for emb e d d e d  system co mbini ng w i th the   character i stic of  exten d ib le hash i ng  an d l i near  has hin g .  It is no ov erflo w  buckets an d  the i ndex  si ze is   prop ortion al to  the adj ustment  number.      Ke y w ords : dy na mic h a shi ng,  emb e d d e d  system, overfl ow  bucket, index si z e       Copy right  ©  201 3 Un iver sitas Ah mad  Da h l an . All righ ts res e r ved .       1. Introduc tion  With the  rapi d develo p me nt of ele c tro n ic te chn o log y , the perfo rmance of e m bedd ed   hard w a r e is  contin uou s ri sing.   T h is m a ke s the em bedd ed syst e m  can p r oce ss mo re  com p lex  tas k  [1].   Dyn a mic  ha shing  has always  been  an in de xing algo rith m that wid e ly use d  in  gen eral - purp o se com puter  system. i t can u s e  ha shin g fun c ti o n  to cal c ul ate  the index a d d re ss of the  data   sho u ld in sert  into. Beside s, it can expan d the i ndex si ze to obtain  more d a ta an d less overflo w   block. But it is ne ce ssa r y to get a  right  a ddr e s s u s ing   the sa me h a shing fun c tion  after expa ndi ng  operation [2].  The typical  dynamic ha shing i s  exte ndible  ha shi ng a nd lin e a r h a shing.  For th e  extendible ha shin g, the numbers  of dire ctory entri es  will doubl e when the extendible ha shi n g  need s to exp and in dex [3]. This  will lea d  to the direct ory entri es  n u mbe r  surg e. Then it resul t  in   wa ste too mu ch mem o ry. The linea r ha shin g schem e is a dire ctory-less sche m e  whi c h allo ws a  smooth  g r o w th of th e h a sh  table.  Line ar ha shin g  split  only  one  bu cket ea ch  tim e . It ca n avoi d  the nu mbe r  o f  dire ctory  en tries surg e af ter  several  split like  exten d ible  ha shin g .  Ho weve r, th e   que stion is th at the split b u cket isn ' t the cu rre nt  spli t bucket and  this will lea d   to many buckets  have to maintain the overfl ow [4]. The re su lt is de crea sing of the qu ery efficien cy.    That is to sa y that both of them are  not  suitabl e for e m bedd ed e n vironm ents [5 -7]. The  dynamic h a shing mentio n ed in this p aper i s   com b ining with t he advantag es of extend ible  hashing  an d  linear ha shi n g of  co urse i t  can   avoid  t he  sho r tcomi ngs of th em  and  be come  a  better dynami c  ha sh.       2. Rese arch  Metho d   2.1. Basic Concep ts and  Nota tion De fine   (1) Ba sei c  co nce p ts   An illust ration of dynami c   hashing i s   shown  in Fi gure 1. In orde r to  understanding wel l   the followin g  algorith m , we  first introdu ce some b a si c con c ept s an d define their  symbol s.  Index:   the h a s hin g  tabl e.it is the  set of h a shi ng  ta ble  entry. If the i ndex  size i s   L, then it   contai ns L h a s hin g  table e n try. Hashing  table entrie s  are nu mbe r e d  from 0 to L-1.  Index entry: The basi c  unit of the directo r y. It  should h a ve two prop erties at lea s t .  One is   the index entries ad dre s s. Another  o ne i s  the pointe r  to a bucket.   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   e-ISSN:  2087 -278X       A Dynam ic  Hashi ng Algo rithm  Suitable for Em bedded  System  (Li Ji anwei)  3221 Bucket: the  set of data  of  reco rd. T he  d a ta or  record s in  same  bu cket have  so me  similar  cha r a c teri stics. Fo r exam p l e, all the  key  of dat a i n  on e bu cket mo dulo the  ind e x  size  L  equ als  the index entry. Data organ ization in the  bucket c an b e  varied. Such as BTree, L i nke d  list etc.           Figure 1. An Illustratio n  of Dynami c  ha shing       Id: the dee p of ind e x or gl obal  d eep, the  propertie s   of index. The  value is Ld 1 L ) 1 Ld ( 1   .  Bd: the dee p of bu cket  and it is th e  pro pertie s  o f  bucket.it mean s that th e left (   Bd WordLength 1 Key  ) or rig h t ( Bd 1 % Key ) Bd bit of data in the bucket  are eq ual [8].   SNext: SNext is the index entry that will be  split. The  cha nge s rul e s are a s  follo ws [9]:         1 Id 1 SNext SNext 1 Id 1 SNext     0 SNext                                                                                                                     (1)     Value=F (key): the hashi ng  function. It can put  Key scattere d into a certai n ran ge. Such   as:   1 n 1 value 0  .  (2) Notation  define  L: the index size in current  state. The big gest ind e x en try addre s s is L-1.   <<: Lo gical Shift Left  ==: eq ual s  !=: not equal   A ++:  A = A + 1   %: Modulo     2.2. Addre s s i ng Algorith m   Step 1: Key=Get (data ) .ge t  the key of data.  Step 2: Value=F (key).h a sh ing the key.   Step 3: Get the index entry addre ss E_i d  as the follo wing fun c tion  [10]:                           L Id) value%(1                   Id) value%(1 L Id) (1     value% 1 - Id 1 value% id _ E                                                    (2 )     Step 4: then  do the  se arch o p e r ation  in the bu ck et  of E_id poi n t er to. The  search  ope rati on   algorith m  is related to the data org ani za tion manne r.     2.3. Insert Al gorithm   Step 1: Key=Get (data ) .ge t  the key of data.  Step 2: Value=F (key).h a sh ing the key.   Step 3: Get the index entry addre ss E_i d  as the fun c tion (2 ).  Step 4: Sele ct the key  of in serte d  d a ta in  the bu ck et of  E_id pointer  to. If it has  been exis t,  return   failure. Othe rwise, inse rt the data into the bu cke t. At last, it needs to check wh ether o r  not the   bucket have  overflow bl ock. If exist ove r flow blo c k, need to do spli t operation.   SNe x t  I d   Bd  Bucket   Bd  Bucket   Bd  Bucket   B d   Bucket   0  1  2 L-1  …………   …………   In de x   Evaluation Warning : The document was created with Spire.PDF for Python.
                               e-ISSN: 2 087-278X   TELKOM NIKA   Vol. 11, No. 6, June 20 13 :  3220 – 3 227   3222 2.4. Adjustm e nt Algo rith m  Get the local deep of  split bucket Bd an d the  index e n try address  M pointer to i t.do the   followin g  ope ration a c cordi ng to the rel a tionshi p between the lo cal  deep of split bucket Bd a nd  the index dee p Id.  (1) If Bd== Id  Step 1: Id++; the global d e p th sho u ld pl us 1   Step 2:  get the dire cto r y entry numbe r that t he broth e r bu ckets of  M. B_M=M +  (1<< (Id-1));  Step 3: expand the dire cto r y entry numb e r to B_M 。   Step 4: Split the nod es of b u cket to M an d  B_M bucket  as the mann er of bu cket  split.    Step 5: The local d epth of bucket M and  brothe r bu cket B_M shoul d plus 1.   Step 6: The directo r y entry  from N to B_ M- 1 shoul d p o inter to their  brothe r bu cke t .  An illustratio n  of adjustmen t operation  when Bd==Id i s  sh own in Figure 2 ( a ) .        Figure 2(a ) . An Illustration  of Adjustment  Operatio n when Bd==Id       The ind e x wil l  expand 1 <<(Id-1 ) ent ry in the  wo rst situation. Ho wever, the ind e x only  expand 1 e n try in the best situation.    (2) If Id= = B d+ 1  In this  c a s e ,  there may be exis t two index  entry poin t ing to the sp lit bucket. Ho wever,  we  don’t  kno w   wheth e r  or not the  bigg er in dex e n try is al rea d y  exists i n  the   index. So it i s   necessa ry to  do op eratio n  as the   situati on whethe r o r  not the bi gge r ind e x entry i s  al rea d y exists   in the index.  Step1: get th e smalle r in d e x entry   num ber pointe r  to  bu cket M:   Bd m i ni_n um =M & 2 1 .get the bigge r index entry  numbe r:  Bd m a x_num = m ini _num | 2 .  Step2: if  ma x_num<L .it  mean s the in dex entry ma x_num have  alrea d y in th e index.   Split the nod es of bu cket  to  ma x_ num  and  min i_ num  bucket.The lo cal  deep of  ma x_ num   and  m i ni _n u m bu cket should pul s 1. The index do esn’ t nee d to expand the in dex.An illustration   of adjustme n t operatio n wh en Bd+1 ==Id  and max_n u m <L is  sho w n in Figure 2(b).           Figure 2(b ) . An Illustration  of Adjustment  Operatio n when Bd+1==I d  and max_n u m<L       3  0  Bucket  Bucket  Bucket  2  3 2  2  1  2  3  Snext  3  4  5  Bucket  Bucket  3  0  Bucket  Bucket  3  3  2  2  1  2  3  Snext  4  5  Bucket Bucket  3  3  Bucket  Bucket  sp lit  2  Bucket 0  Bucket   Bucket  Bucket  2  2  2 2  1 2  3  Sne x t 3  0  Bucket  Bucket  Bucket  2  3  2 2  1  2  3  Sne x t  3  4  5  Bucket Bucket  sp lit  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   e-ISSN:  2087 -278X       A Dynam ic  Hashi ng Algo rithm  Suitable for Em bedded  System  (Li Ji anwei)  3223 If m a x_num L  it means the index ent ry max _num  isn’t in the  index. Expand the  dire ctory ent ry number to  ma x_ num 。 Split the nodes of b u cket  to  ma x_ num  and  m i ni _n u m bucket a s  the manne r of bucket split.  The local de pth of bucket  ma x_ num  and  m i ni _n u m   sho u ld plu s  1.at  last,  th e dire ctory entry  from  L to  max_num -1  sho u ld  pointe r  to th eir brothe r  bucket. The i ndex ne ed e x pand 1 < <(Id -1)  entry in  t he worst situ ation.ho weve r,the index o n ly  expand  1 ent ry in the b e st  situati on.An i llustratio n  of  adju s tment o peratio n whe n  Bd+1==Id  and   max_num >=L  is sho w n in F i gure 2 ( c).         Figure 2(c). A n  illustratio n  of adjustme n t operatio n wh en Bd+1 ==Id  and max_n u m >=L        (3) If  Id > B d + 1   Step 1: get the sm allest ind e x ent ry nu mber p o int e r to M  bucket:  m i ni_M=M& 1 B d 1     Get the bro t her ind e x e n try numb e r  clo s e s t to the small e st in dex  entry:   B _ m i ni _M=m i n i _ M| 1 B d    Step 2: Split the nod es of b u cket to  mi ni_M  and  B _ mini_M  bucket as th e manne r of  bucket  split.  The lo cal  de pth of b u cket   mi ni_M  an d b r othe r bu cket  B _ mini_M  sho u ld pl us  1.the brothe r index e n try  of  mi ni_M  and   B _ mini_M shoul d ponte r  to t he respon de d bu cket.  The ind e x doesn’t need  to expand th e index.An illu stratio n  of  adju s tment o peratio n whe n   Bd+1 <Id is  sh own in Fig u re  2(d).           Figure 2(d ) . An Illustration  of Ad justment  Operatio n when Bd+1<Id       3. Experimental Re sults  and An aly s is  In this cha p ter, this pa pe r will compa r e the overflo w  bu cket nu mber b e twe e n  linear  hashing  and  the dyn a mic h a sh  propo se d  in thi s  p ape r. Then  we  wil l  test the  cost  time of in se rt  operation, Un it to adjustme n t time, addressing time  a nd sto r ag e uti lization. Be si des,  we will t e st  the relation  of  the in dex  size an d  split n u m ber.  A nd  an alyze th e  cau s e s  of  the  gro w th trend.  Th e  averag e time  (T)  use the  numbe r of  cl ock freq uen cy (N) to  ch aracteri ze,  com puter frequ en cy is  rep r e s ent by F. the conversion meth od  wi th the ac tual time is  as  f o llows :     3  0  Bucket  Bucket  1  3  3  1  2  2  Snext  3  4  5  Bucket Bucket  3  0  Bucket  Bucket  2  3  3  1 2  2  Snext  3  4  5  Bucket Bucket  2  Bucket  sp lit  3  0  Buck et  Bucket  Bucket  2  3  2 2  1  2  3  Snext  3  4  5  Bucket Bucket  3  0  Bucket  Bucket  Bucket  2  3  3  2  1  2  3  Snext  3  4  5  Bucket  Bucket  6 t 3  sp lit  Bucket  Evaluation Warning : The document was created with Spire.PDF for Python.
                               e-ISSN: 2 087-278X   TELKOM NIKA   Vol. 11, No. 6, June 20 13 :  3220 – 3 227   3224 nu m b e r ms Hz N( ) T( ) = F( )                                                                                                                                              (3 )       3.1. The Co mparison of  Ov erflo w   Bu cket  Number    No matte r usi ng what data  orga nization  method to m anag e the da ta in bucket.   the sum   of data number will have  an influence  on the search  efficiency. The character of real time in   embed ded  sy stem requi re t h is o perat ion  can fini sh i n  a  deadli ne tim e .so  we d e fin e  a bu cket si ze   to re spo nd th e de adline  va lue. As  so on  as th e  sum  d a ta in th e bu cket re ach to  this val ue, t he  overflow h a p pene d. The compa r tion of overfl ow b u cket numbe r is  sho w  in Figu re 3.          Figure 3. The  Compa r tion  of Overflow B u cket Num b e r       From the refence [11], we  can draw the conc l u tion that the bucket will be split isn’t the  overflow b u cket insert a reco rd, and it is de cide  by the next point er as  cycli c   manne r. Ho wever,  with the incre a sin g  of data  numbe r, the next point er  finish a cy clic need mo re ti me. That is to  say, more an d more  bu cket need to  split have ov e r flow bl ock. The tre nd of  overflow b u cket  numbe r of li n ear  ha shin g i s   sho w  figu re  3. Fro m  the  dynamic ha shing al go rithm pro p o s ed  i n  this  pape r, it is clear that a s  soon a s  a inse rt operat ion p r odu ce a ove r flow blo c k, the split op era t ion  will be executed immedi ately. So the r e is no ov erflow block exist in the dynamic hashi n g  prop osed in this pa per.     3.2. The Time of Add r es s i ng Cost  As the increa sing of data n u mbe r s,the trend of  add re ssing  co st time is sho w n in F i gure  4(a ) .        Figure 4(a ) . T he Averag e Addre s s Time  and, (b )  The  Storage  Utilization Accordi ng to the Dat a   Numb er       From the Fig u re 4 ( a), wit h  the gro w in g of data numbers ， the a v erage  co st time of  addressin g  tends to paralle l and ex sit so me perio dic fl uctuatio ns 。 T he rea s o n s is mainly depe nd  on the storage utilization of bucket 。 The  stora ge utilization trend i s   sho w n in Fig u re 4 ( b).a nd the   storage utilization is calcul ated by the following m anner ：   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   e-ISSN:  2087 -278X       A Dynam ic  Hashi ng Algo rithm  Suitable for Em bedded  System  (Li Ji anwei)  3225 the sum of da ta storage util iza tion= the n u m b er of b u ck e t b u ck e t  ca p a c ity                                                         (3)       From the  Fig u re 4 ( b ) , wh e n  the total a m ount  of dat a is 4 0000 0, the storage  u t ilization  rate of  bu cket is  nea rly 98 %. However,  whe n  th e  tota l amou nt of d a ta is 41 0000 . The utili zati on   rate of  bu cke t  is a bout 5 1 % . Then th e  former  ave r a ge d epth of t he b u cket i s   deep er th an t h e   later b u cket.  Therefore,the  avera ge  ad dre ssi ng  tim e  is  de crea se when th e  numbe rs of  data  increa se fro m  4000 00 to  4100 00.with  the amo unt   of data conti nue to in crea sing, the  ave r age  bucket utiliza t ion rate  will be growi ng; the aver age tree depth  of the bu cket wil l  be dee per,  so   this well le ad  the averag e a ddre s sing tim e  to periodi c fluctuatio ns.     3.4. The Time of Adjus t m e nt Op era t ion Cos t   The adju s tm ent operation  is relate d to index  table expan sion, b u cket split a nd index   entry poi nter to re sp ond  bu cket. Bucket split  is executed i n  every a d ju stment ope rat i on.  Ho wever, th e  othe r two o p e ration  may  b e  do n’t r un i n  adju s tment  o peratio n.be si des, th e time  o f   adju s tment  cost i s  d e ci de  by the  sum  d a ta num be r a nd the  data  o r gani zatio n  m anne r. the  in dex  table expa nsi on do n’t dou ble the in dex  size. So, it can  re duce t he ind e x si ze. At last, in  the   worst situatio n, there is up  to half of index si ze ent ry must pointe r  their con r e s po nd bu cket.  The total adj ustment time  trend is  sh own in Fi gure 5(a ) . The  gro w th tren d  of total  adju s tment n u mbe r s i s  sh own in Fig u re  5(b). The  u n i t  to adjustme n t is sho w n in  Figure 5 ( c). The  averag e adj u s tment time i s  sho w n in  Fi gure  5(d). Th e avera ge a d j usting time  i s  calu culate d  as   follows :    the  tot a l  ti m e  of  a d j u s t m e nt c o s t a v erag e  ad j u s t me n t  t i me= the  sum  of da ta                                                          (4)     Unit to adju s tment time ref e rs to the av erag e time o n ce a d ju stme nt. Both the total o f   adju s tment time and th e t o tal of adju s t m ents n u mb e r  are stati s tic  from the exp e rime nt. The  unit  to adjus tment time is  c a lc ulated as  follows :    the  tota l  tim e  of  a d justme nt c o st av er ag e  u n i t  t o  ad j u s t men t   t i m e= the  tota l  of  spl it num b e r                                          (5)           Figure 5(a ) . Sum Adjustme nt Time, (b) S u m Adjust ment Number, (c) Unit to Adjus t ment Time  and, (d ) Average Adju stme nt Time Acco rding to the Data Numb er    Evaluation Warning : The document was created with Spire.PDF for Python.
                               e-ISSN: 2 087-278X   TELKOM NIKA   Vol. 11, No. 6, June 20 13 :  3220 – 3 227   3226 3.4. The Rela tion of Index  Size and Split Numbers   From the  cha p ter 2, we  ca n dra w  the co nclu tio n  that the index exp antion may d on’t run  in adju s tmen t operatio n. In ord e r to in vesti gate the  spe ed of in dex expan sio n  wh en runi ng   adju s tment o peratio n. We  test the index  size a nd adj ustment nu m ber after in se rting many d a ta   that rangin g  from 10 000 to  64000 0.        Figure 6. The  Index Table Size Accordin g to the Data Numb er       Figure 6  de p i cts th e i nde x size  acco rding to  the  n u mbe r  of  inserted  data.  F i gure  7  depi cts the in dex size acco rding to the n u mbe r  of  adju s tment ope rat i on run.  We can se e that the  index si ze is  prop ortio nal to the adju s tment numbe r.       Figure 7. The  Index Table Size Accordin g to the Split  Numb er       4. Conclusio n   In this pa pe r, we a r e  pro p o s ed  a ne w eff i cient dyn a mi c ha shi ng al g o rithm fo r em bedd ed  system.  The bucket will  immediate sp lit  when bucket over flow  occurs. So there i s  no overflow in   this ne w efficient dynamic  hashing al gorithm co mp are d  with linea r  hashing. Besi des, the r e are  four a d ju stm ent op eratio n  strate gie s  a c cording   to th e differe nt rel a tionship of  b u cket d eep  a n d   index table  d eep. Not all o f  the adju s tm ent ope ratio n  need  to exp and the  ind e x table. Bed s id es,  in the adj ust m ent op eratio n that nee d t o  do a d ju stm ent ope ration,  The in dex wi ll expand  1<<(Id- 1) entry in the  worst situatio n. However, t he index only  expand 1 ent ry in the best  situation.   From the vari ous exp e rim e ntal results,  we sho w ed t hat the prop o s ed dyn a mic  hashing  doe sn’t have  overflow bl ocks a nd the in dex size  is p r oportio nal to  the adju s tme n t numbe r. That  is mea n  that it is outperfo rms traditio nal   dynamic h a shing alg o rith m on the em bedd ed sy ste m   that req u ire real-time  and   memory  re so urces a r e ve ry scarce. Fi n a lly, we pl an t o  imple m ent  and  analyze the  pra c tical  perf o rma n ce of the pro p o s e d  ha sh ind e  on the p r a c tical  real -time  embed ded  system in the fu ture.       Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   e-ISSN:  2087 -278X       A Dynam ic  Hashi ng Algo rithm  Suitable for Em bedded  System  (Li Ji anwei)  3227 Ackn o w l e dg ement  This  wo rk i s  un der th e su ppo rt of  the “Sha nxi Province  nature  Fo undatio n   (No.2 012 011 027-3)”; auth o rs  h e reby thank them fo r the finan cial suppo rts.       Referen ces   [1]  Mullally  A d rian, McKe lve y  N i gel, C u rran  Ke vin.   Perform a nce com paris o n  of e n terpris e  app licati ons   on m obi le  op e r ating  s y stems .   T E LKOMNIKA Indo nes ian  Jour nal  of E l ectrical  Eng i n e erin g.  20 11;   9(3): 503- 51 4.   [2]  Rammoh anr ao  K, Lio y d JK. Dyn a mic H a shi n g Schemes.  C o mputer Jo urn a l.  475- 48 5.  [3]  Ron a ld F a gin,  Jurg Ni everg e l t. Extendi bl e H a shi n g - A F a st  Access Metho d  for d y nam ic F iles.  ACM   T r ansactio n s o n  Datab a se Sy stems . 19 79; 4 ( 3): 315-3 44.   [4] Witold  Lit w in.  Lin ear  hash i n g :  a new  tool  fo r file a nd ta lb e  addr essin g . P r ocee din g s of t he 6r d Intl.  Confer ence  on  Ver y  L a rge D a ta Bases. Can ada. 19 80: 21 2 - 223.    [5]  W ang Xi bo, Li   Nan.  E m be d ded  Syste m   Memory Ma na ge me nt Mech anis m  B a se d  on u C .OS –II.  Procee din g s of the 2010 Inter natio nal C onfer ence o n  Com m unic a tions a n d  Mobil e  Comp uting. 20 10 ;   258- 262.   [6]  W oochu l Kan g , Sang H S on. Po w e r a n d  time a w ar e  buffer cache  manag ement  for real-time   embe dde d d a tabas es.  Journ a l of Syste m s  Architecture: t he EUROMIC R O Journ a l . 2 012; 5 8 (2-3) :   233- 246.   [7]  Yu Hu, Z h a ng  W e ihu a i. Res e arch o n  rea l -ti m e an d d y n a m i c urba n traffic: Information s e rvice s y stem.  T E LKOMNIKA Indon esi an Jou r nal of Electric al Eng i ne eri n g .  2012; 1 0 (4): 8 06-8 11.   [8]  Askok Rath i,  Huizh u  L u .  P e rformanc e co mp ariso n  of  extend i b le  hash i ng  an d  li ne a r  ha shi ng  techni qu es.  AC M Pre ss 15 15  Bro a d w ay ,  17 th  F l oor Ne w   York, NY.DOI:10.11 45/1 2 2 0 4 5 . 122 04 8.19- 26.   [9]  Larso n P. Performanc e Ana l ysis of a  Sing le- f ile Versi on of  Lin ear H a shi n g .  Computer Jo urna l.  319- 326.   [10]  Hul-W o o n g  YA NG, et al. A n  E fficient D y n a mi c Has h  Ind e x   Structrue for  N A ND F l as h M e mor y .  IEICE  T r ansactio n s o n  F unda menta l s of Electronic s , Commu n ic ations a nd C o mp uter Scienc es . 200 9; E92- A 7: 1716- 171 9.  [11]  Xi an g L i , et a l . A Ne w   D y n a m ic Has h  Ind e x  fo r  F l ash-B a sed Stor age.  Procee din g s of  the 9r d Intl .   Confer ence  on  W eb-Age Infor m ation  Ma nag ement. 200 8; (20-2 2 ): 93-9 8 .      Evaluation Warning : The document was created with Spire.PDF for Python.