package Ġchapter 3 . section 4 Ċ Ċ import Ġchapter 3 . section 1 . ST Ċ import Ġchapter 3 . section 1 . test ST Ċ import Ġedu . pr inc et on . cs . al gs 4 . Queue Ċ import Ġextensions . random Ċ Ċ /** Ċ Ġ* Ġ 3 . 4 . 2 Ġ éĩįæĸ° å®ŀçİ° Separ ate Ch aining Hash ST ï¼Į çĽ´æİ¥ ä½¿çĶ¨ Sequential Search ST ä¸Ń éĵ¾è¡¨ éĥ¨åĪĨ çļĦä»£çłģ Ċ Ġ* Ġ 3 . 4 . 3 Ġä¿®æĶ¹ ä½ł ä¸º ä¸Ĭ ä¸Ģ éģĵ ç»ĥ ä¹ł ç»Ļ åĩºçļĦ å®ŀçİ° ï¼Į ä¸º æ¯ıä¸ª éĶ® åĢ¼ å¯¹ æ·»åĬł ä¸Ģä¸ª æķ´ åŀĭ åıĺéĩı ï¼Į å°Ĩ åħ¶ åĢ¼ è®¾ ä¸º æıĴåħ¥ è¯¥ éĶ® åĢ¼ å¯¹ æĹ¶ æķ£ åĪĹè¡¨ ä¸Ń åħĥç´ł çļĦ æķ°éĩı Ċ Ġ* Ġ å®ŀçİ° ä¸Ģä¸ª æĸ¹æ³ķ ï¼Į å°Ĩ è¯¥ åıĺéĩı çļĦåĢ¼ å¤§äºİ ç»Ļ å®ļ æķ´æķ° k çļĦ éĶ® ï¼Ī åıĬ åħ¶ çĽ¸åºĶ çļĦåĢ¼ ï¼ī åħ¨éĥ¨ åĪłéĻ¤ Ċ Ġ* Ġ æ³¨æĦı ï¼ļ è¿Ļä¸ª é¢Ŀ å¤ĸ çļĦ åĬŁèĥ½ åľ¨ ä¸º ç¼ĸè¯ĳ åĻ¨ å®ŀçİ° ç¬¦ åı· è¡¨ æĹ¶ å¾Ī æľī çĶ¨ Ċ Ġ*/ Ċ class ĠRecord Num Hash ST < K Ġ: ĠAny , ĠV Ġ: ĠAny >( var Ġm : ĠInt Ġ= Ġ 4 ) Ġ: ĠST < K , ĠV > Ġ{ ĊĊĠĠĠ Ġ// num è¡¨ç¤º æıĴåħ¥ è¯¥ éĶ® åĢ¼ å¯¹ æĹ¶ æķ£ åĪĹè¡¨ ä¸Ń åħĥç´ł çļĦ æķ°éĩı ĊĠĠĠ Ġclass ĠNode < K Ġ: ĠAny , ĠV Ġ: ĠAny >( val Ġkey : ĠK , Ġvar Ġvalue : ĠV , Ġvar Ġnum : ĠInt , Ġvar Ġnext : ĠNode < K , ĠV >? Ġ= Ġnull ) ĊĊĠĠĠ Ġprivate Ġvar Ġn Ġ= Ġ 0 Ġ// n ä¸º éĶ® åĢ¼ å¯¹ æĢ» æķ° ï¼Į m ä¸º æķ£ åĪĹè¡¨ å¤§å°ı ĊĠĠĠ Ġprivate Ġvar Ġst Root Array Ġ= ĠarrayOf Null s < Node < K , ĠV >>( m ) ĊĊĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠ Ġrequire ( m Ġ> Ġ 0 ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġhash ( key : ĠK ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġ( key . hashCode () Ġand Ġ 0 x 7 fffffff ) Ġ% Ġm ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġresize ( size : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġnew Hash ST Ġ= ĠRecord Num Hash ST < K , ĠV >( size ) ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġst Root Array . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġnode Ġ= Ġst Root Array [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( node Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnew Hash ST . put ( node . key , Ġnode . value , Ġnode . num ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode Ġ= Ġnode . next ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġm Ġ= Ġnew Hash ST . m ĊĠĠĠĠĠĠĠ Ġst Root Array Ġ= Ġnew Hash ST . st Root Array ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġput ( key : ĠK , Ġvalue : ĠV ) Ġ{ ĊĠĠĠĠĠĠĠ Ġput ( key , Ġvalue , Ġn ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġput ( key : ĠK , Ġvalue : ĠV , Ġnum : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( n Ġ>= Ġ 8 Ġ* Ġm ) Ġresize ( 2 Ġ* Ġm ) ĊĊĠĠĠĠĠĠĠ Ġval Ġindex Ġ= Ġhash ( key ) ĊĠĠĠĠĠĠĠ Ġvar Ġnode Ġ= Ġst Root Array [ index ] ĊĠĠĠĠĠĠĠ Ġwhile Ġ( node Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . key Ġ== Ġkey ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . value Ġ= Ġvalue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . num Ġ= Ġnum ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode Ġ= Ġnode . next ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġst Root Array [ index ] Ġ= ĠNode ( key , Ġvalue , Ġnum , Ġst Root Array [ index ]) ĊĠĠĠĠĠĠĠ Ġn ++ ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġget ( key : ĠK ): ĠV ? Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġindex Ġ= Ġhash ( key ) ĊĠĠĠĠĠĠĠ Ġvar Ġnode Ġ= Ġst Root Array [ index ] ĊĠĠĠĠĠĠĠ Ġwhile Ġ( node Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . key Ġ== Ġkey ) Ġreturn Ġnode . value ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode Ġ= Ġnode . next ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġnull ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġdelete ( key : ĠK ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġindex Ġ= Ġhash ( key ) ĊĠĠĠĠĠĠĠ Ġvar Ġnode : ĠNode < K , ĠV > Ġ= Ġst Root Array [ index ] Ġ?: Ġthrow ĠNoSuch ElementException () ĊĠĠĠĠĠĠĠ Ġif Ġ( node . key Ġ== Ġkey ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġst Root Array [ index ] Ġ= Ġnode . next ĊĠĠĠĠĠĠĠĠĠĠĠ Ġn -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( m Ġ>= Ġ 4 Ġ&& Ġn Ġ<= Ġ 2 Ġ* Ġm ) Ġresize ( m Ġ/ Ġ 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġvar Ġnext Node Ġ= Ġnode . next ĊĠĠĠĠĠĠĠ Ġwhile Ġ( next Node Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( next Node . key Ġ== Ġkey ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . next Ġ= Ġnext Node . next ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġn -- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( m Ġ>= Ġ 4 Ġ&& Ġn Ġ<= Ġ 2 Ġ* Ġm ) Ġresize ( m Ġ/ Ġ 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode Ġ= Ġnext Node ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnext Node Ġ= Ġnext Node . next ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġthrow ĠNoSuch ElementException () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* Ġå°Ĩ æīĢæľī éĶ® åĢ¼ å¯¹ ä¸Ń ï¼Į num åıĺéĩı å¤§äºİ ç»Ļ å®ļ æķ´æķ° k çļĦ éĶ® åĢ¼ å¯¹ åħ¨éĥ¨ åĪłéĻ¤ ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġdelete Num GreaterThan ( k : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġst Root Array . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġroot Ġ= Ġst Root Array [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( root Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// å¦Ĥæŀľ æ¯ıä¸ª åŃĲ éĵ¾è¡¨ çļĦ æł¹ ç»ĵçĤ¹ num åıĺéĩı å¤§äºİ k ï¼Į å¯¹ æł¹ ç»ĵçĤ¹ éĩįæĸ° èµĭåĢ¼ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( root . num Ġ> Ġk ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġroot Ġ= Ġroot . next ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġst Root Array [ i ] Ġ= Ġroot ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġn -- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// éĿŀ æł¹ ç»ĵçĤ¹ çļĦ ç»ĵçĤ¹ num åıĺéĩı å¤§äºİ k ï¼Į éĩįæĸ° æĭ ¼ æİ¥ ç»ĵçĤ¹ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġnode : ĠNode < K , ĠV > Ġ= Ġroot ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġnext Node Ġ= Ġnode . next ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// å¯¹ root éĩįæĸ° èµĭåĢ¼ ï¼Į éĢĢåĩº ç¬¬äºĮ å±Ĥ å¾ªçİ¯ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġroot Ġ= Ġnull ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( next Node Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( next Node . num Ġ> Ġk ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnext Node Ġ= Ġnext Node . next ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . next Ġ= Ġnext Node ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġn -- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode Ġ= Ġnext Node ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnext Node Ġ= Ġnext Node . next ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// æīĢæľī åħĥç´ł éĥ½ åĪłéĻ¤ åĲİ åĨį éĩįæĸ° è®¡ç®Ĺ å¤§å°ı ĊĠĠĠĠĠĠĠ Ġif Ġ( m Ġ>= Ġ 4 Ġ&& Ġn Ġ<= Ġ 2 Ġ* Ġm ) Ġresize ( m Ġ/ Ġ 2 ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġcontains ( key : ĠK ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġget ( key ) Ġ!= Ġnull ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun ĠisEmpty (): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġsize () Ġ== Ġ 0 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġsize (): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġn ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġkeys (): ĠIterable < K > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġqueue Ġ= ĠQueue < K >() ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġst Root Array . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġnode Ġ= Ġst Root Array [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( node Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqueue . enqueue ( node . key ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode Ġ= Ġnode . next ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġqueue ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġjoin ToString (): ĠString Ġ{ ĊĠĠĠĠĠĠĠ Ġval ĠstringBuilder Ġ= ĠStringBuilder (" m =${ m } Ġn =${ n }") ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġst Root Array . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠstringBuilder . append ("\ n ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. append (" i =$ i Ġ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġnode Ġ= Ġst Root Array [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( node Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠstringBuilder . append ("[ key :${ node . key }, num =${ node . num }] Ġ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode Ġ= Ġnode . next ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn ĠstringBuilder . toString () ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun Ġmain () Ġ{ ĊĠĠĠ Ġtest ST ( Record Num Hash ST ()) ĊĠĠĠ Ġval Ġst Ġ= ĠRecord Num Hash ST < Int , ĠInt >() ĊĠĠĠ Ġval Ġarray 1 Ġ= ĠInt Array ( 2 0 ) Ġ{ Ġit Ġ} ĊĠĠĠ Ġarray 1 . forEach Ġ{ Ġst . put ( it , Ġ 0 ) Ġ} ĊĠĠĠ Ġprintln (" put Ġ[ 0 , 1 9 ]") ĊĠĠĠ Ġprintln ( st . join ToString ()) ĊĠĠĠ Ġprintln () ĊĊĠĠĠ Ġrepeat ( 1 0 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġvalue Ġ= Ġrandom ( 2 0 ) ĊĠĠĠĠĠĠĠ Ġif Ġ( st . contains ( value )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġst . delete ( value ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġprintln (" random Ġdelete Ġ 1 0 ") ĊĠĠĠ Ġprintln ( st . join ToString ()) ĊĠĠĠ Ġprintln () ĊĊĠĠĠ Ġval Ġarray 2 Ġ= ĠInt Array ( 1 0 ) Ġ{ Ġit Ġ+ Ġ 2 0 Ġ} ĊĠĠĠ Ġarray 2 . forEach Ġ{ Ġst . put ( it , Ġ 0 ) Ġ} ĊĠĠĠ Ġprintln (" put Ġ[ 2 0 , 2 9 ]") ĊĠĠĠ Ġprintln ( st . join ToString ()) ĊĠĠĠ Ġprintln () ĊĊĠĠĠ Ġst . delete Num GreaterThan ( 1 5 ) ĊĠĠĠ Ġprintln (" delete Num GreaterThan Ġ 1 5 ") ĊĠĠĠ Ġprintln ( st . join ToString ()) Ċ }