蹇呭鐭ヨ瘑馃瀛楀吀锛屽張绉扮鍙疯〃鎴栨槧灏勶紝鍙互绠€鍗曠悊瑙ｄ负閿€煎銆傛瘮濡侸ava甯哥敤鐨勯泦鍚堢被HashMap灏辨槸鐢ㄦ潵瀛樺偍閿€煎鐨勩€傚瓧鍏镐腑鐨勯敭锛坘ey锛夋槸鍞竴鐨勩€傜敱浜庤繖涓壒鎬э紝鎴戜滑鍙互鏍规嵁閿紙key锛夋壘鍒板搴旂殑鍊硷紙value锛夛紝鎴栬€呰繘琛屾洿鏂板拰鍒犻櫎鎿嶄綔銆傚瓧鍏竏ict鐨勫疄鐜癛edis鐨勫瓧鍏告槸浣跨敤鍝堝笇琛ㄤ綔涓哄簳灞傚疄鐜扮殑銆備竴涓搱甯岃〃涓彲浠ユ湁澶氫釜鍝堝笇琛ㄨ妭鐐癸紝姣忎釜鑺傜偣涔熷瓨鍌ㄥ搴旂殑閿€煎銆俁edis鐨勫瓧鍏竏ict缁撴瀯濡備笅锛歵ypedefstructdict{//Type-specificfunction//鏄竴涓寚鍚慸ictType缁撴瀯鐨勬寚閽堬紝浣縟ict鐨刱ey鍜寁alue鍙互瀛樺偍浠绘剰绫诲瀷鐨勬暟鎹甦ictType*type;//privatedata//绉佹湁鏁版嵁鎸囬拡锛屼笉鏄璁虹殑閲嶇偣锛屾殏鏃跺拷鐣oid*privdata锛?/鍝堝笇琛╠icththt[2];//rehashindex//娌℃湁杩涜rehash鏃讹紝鍊间负-1intrehashidx;}鎴戜滑鍏虫敞涓や釜灞炴€у彲浠ユ槸锛歨t灞炴€э細鍙互鐪嬪埌ht灞炴€ф槸涓€涓猟ictht鍝堝笇琛ㄦ暟缁勶紝澶у皬涓?銆佷竴鑸儏鍐典笅锛屽瓧鍏稿彧鐢ㄥ埌ht[0]锛岃€宧t[1]鍙細鐢ㄤ簬ht[0]锛屽彧鏈夊湪鍝堝笇琛╮ehashed鐨勬椂鍊欐墠浼氱敤鍒般€俽ehashidx灞炴€э細璁板綍褰撳墠rehash鐨勮繘搴︺€傚鏋滅幇鍦ㄦ病鏈夎繘琛宺ehash锛岄偅涔堝畠鐨勫€间负-1锛屽彲浠ョ悊瑙ｄ负rehash鐘舵€佺殑鏍囪瘑銆備笅鍥炬槸姝ｅ父鐘舵€佷笅鐨勫瓧鍏革細瀹為檯鏁版嵁瀛樻斁鍦╤t[0]涓紱ht[1]璧疯緟鍔╀綔鐢紝鍙細鍦ㄦ墽琛宺ehash鏃剁敤鍒般€傚叿浣撶殑鍔熻兘鍖呮嫭rehash鐨勫唴瀹癸紝鍚庨潰浼氳缁嗕粙缁嶃€傚搱甯岀畻娉曞畾浣嶇储寮昉S锛氬鏋滀綘鏈塇ashMap鐨勭浉鍏崇煡璇嗭紝鐭ラ亾濡備綍璁＄畻绱㈠紩鍊硷紝閭ｄ箞杩欓儴鍒嗗彲浠ヨ烦杩囥€傚鏋滄垜浠幇鍦ㄦā鎷熷皢鍝堝笇鍊间粠0鍒?鐨勫搱甯岃〃鑺傜偣鏀惧叆涓€涓ぇ灏忎负4鐨勫搱甯岃〃鏁扮粍涓紝鍗虫妸鍖呭惈閿€煎鐨勫搱甯岃〃鑺傜偣鏀惧湪鍝堝笇琛ㄦ暟缁勭殑鎸囧畾绱㈠紩涓娿€俰ndex瀵瑰簲鐨勮绠楀叕寮忥細index=hash&ht[x].sizemask鐪嬩笉鎳備篃娌″叧绯伙紝鍙互绠€鍗曠悊瑙ｄ负hash鍊煎氨鏄痟ash鐨剆ize鍊肩殑浣欐暟琛ㄦ牸鏁扮粍;姣斿涓婇潰hash鍊间负0鐨勮妭鐐?0%4=0,鎵€浠ユ斁鍦╥ndex0鐨勪綅缃?hash鍊间负1鐨勮妭鐐?1%4=1,鎵€浠ユ斁鍦╥ndex鐨勪綅缃?銆乭ash鍊间负5鐨勮妭鐐癸紝5%4=1锛屼篃绛変簬1锛屼篃浼氬垎閰嶅埌绱㈠紩1鐨勪綅缃紝鑰屼笖鐢变簬dictEntry鑺傜偣缁勬垚鐨勯摼琛ㄦ病鏈夋寚鍚戝熬閮ㄧ殑鎸囬拡鍦ㄩ摼琛ㄤ腑锛屾柊鑺傜偣灏嗘坊鍔犲埌閾捐〃鐨勫ご閮紝鍦ㄧ幇鏈夎妭鐐逛箣鍓嶃€傛垜浠皢涓婅堪绱㈠紩鐩稿悓褰㈡垚閾捐〃鐨勬儏鍐电О涓洪敭鍐茬獊锛屽洜涓哄舰鎴愪簡閾捐〃锛侀偅涔堝氨鎰忓懗鐫€鎼滅储绛夋搷浣滅殑澶嶆潅搴﹀彉楂樹簡锛佹瘮濡傝鎵緃ash=1鐨勮妭鐐癸紝鍙兘鏍规嵁hash鍊兼壘鍒癷ndex涓?鐨勪綅缃紝鐒跺悗鎵惧埌hash=5鐨勮妭鐐癸紝鍐嶉€氳繃next鎸囬拡鎵惧埌鏈€鍚庣殑缁撴灉锛岃繖鎰忓懗鐫€鍙戠敓瀵嗛挜鍐茬獊鎷ユ湁鐨勮秺澶氾紝杩涜鏌ユ壘绛夋搷浣滄墍闇€鐨勬椂闂村氨瓒婂銆傚浣曡В鍐虫寜閿啿绐侊紵閲嶅锛佸叾瀹瀝ehash鎿嶄綔寰堝ソ鐞嗚В銆傚彲浠ョ畝鍗曠悊瑙ｄ负鍝堝笇琛ㄦ暟缁勭殑鎵╁鎴栫缉瀹规搷浣滐紝鍗冲皢鍘熸暟缁勭殑鍐呭閲嶆柊鏁ｅ垪鍒版柊鏁扮粍涓€傛瘮濡備笂闈㈢殑鏁版嵁锛岃繖娆℃垜浠妸瀹冧滑鏀惧湪澶у皬涓?鐨勫搱甯岃〃鏁扮粍涓€傚涓嬪浘锛屾鏃秙ize=8锛宧ash涓?鐨勯敭鍊煎锛岄噸鏂拌绠楃储寮曪細5%8=5锛屾墍浠ヨ繖娆′細鏀惧湪绱㈠紩5鐨勪綅缃€傞偅涔堝鏋滄垜浠繕鏄兂鎵惧埌hash=1鐨勭粨鐐癸紝鍥犱负娌℃湁key鍐茬獊锛岃嚜鐒朵篃灏辨病鏈夐摼琛ㄤ簡锛屾垜浠彲浠ョ洿鎺ラ€氳繃绱㈠紩鎵惧埌瀵瑰簲鐨勭粨鐐广€傚彲浠ョ湅鍑猴紝鐢变簬rehash鎿嶄綔鏁扮粍鐨勬墿灞曪紝key鍐茬獊鏇村皯锛屾垜浠彲浠ユ洿楂樻晥鐨勮繘琛屾煡鎵剧瓑鎿嶄綔銆傝Е鍙憆ehash鎿嶄綔鐨勬潯浠堕鍏堬紝鎴戜滑寮曞叆涓€涓弬鏁帮紝鍙仛鍔犺浇鍥犲瓙锛坙oad_factor锛夈€傞渶瑕佹敞鎰忕殑鏄紝瀹冨拰HashMap涓殑loadfactor鏈変笉鍚岀殑鍚箟锛涘湪HashMap涓紝鍔犺浇鍥犲瓙loadFactor鏄竴涓粯璁ゅ€?.75f鐨勫父閲忓瓨鍦紝浣嗘槸鍦╮edis鐨刣ict涓紝瀹冩槸涓€涓姩鎬佸彉鍖栫殑鍙傛暟锛岀瓑浜庡搱甯岃〃鐨剈sed灞炴€у€?size灞炴€у€硷紝鍗冲嵆锛屽疄闄呰妭鐐规暟/鍝堝笇琛ㄦ暟缁勭殑澶у皬銆傚鏋滀竴涓ぇ灏忎负4鐨勫搱甯岃〃鏈?涓搱甯岃妭鐐癸紝閭ｄ箞姝ゆ椂瀹冪殑璐熻浇鍥犲瓙涓?锛涗竴涓ぇ灏忎负8鐨勫搱甯岃〃鏈?涓搱甯岃妭鐐癸紝閭ｄ箞姝ゆ椂瀹冪殑璐熻浇鍥犲瓙灏辨槸0.5銆傚鏋滄弧瓒充互涓嬩换涓€鏉′欢锛岀▼搴忓皢閲嶆柊鏁ｅ垪鍝堝笇琛細鎵╁鎿嶄綔鏉′欢锛氭湇鍔″櫒褰撳墠鏈墽琛孊GSAVE鎴朆GREWRITEAOF鍛戒护锛岃礋杞藉洜瀛愬ぇ浜庣瓑浜?銆傛湇鍔″櫒褰撳墠姝ｅ湪鎵ц璐熻浇绯绘暟澶т簬鎴栫瓑浜?鐨凚GSAVE鎴朆GREWRITEAOF鍛戒护銆傛敹缂╂搷浣滄潯浠讹細褰撹礋杞界郴鏁板皬浜?.1鏃躲€侭GSAVE鍜孊GREWRITEAOF鍛戒护鍙互缁熺О涓烘搷浣渞edis瀹炵幇鎸佷箙鍖栥€侭GSAVE鐨勬剰鎬濇槸閫氳繃fork涓€涓瓙杩涚▼锛岃瀹冨垱寤轰竴涓猂DB鏂囦欢锛岀敱鐖惰繘绋嬬户缁鐞嗗懡浠よ姹傘€侭GREWRITEAOF绫讳技锛屼絾鏄噸鍐欎簡AOF鏂囦欢銆傛笎杩涘紡澶嶈堪锛熼噸鏂板搱甯岀殑杩囩▼鏄粈涔堬紵棣栧厛鎴戜滑鐭ラ亾redis鏄崟绾跨▼鐨勶紝瀵规€ц兘瑕佹眰寰堥珮銆備絾鏄鏋渞ehash鎿嶄綔閬囧埌澶ч噺鐨勬儏鍐碉紝姣斿闇€瑕佽縼绉诲嚑鐧句竾鎴栬€呭嚑鍗冧竾鐨刱ey-value瀵癸紝搴炲ぇ鐨勮绠楅噺鍙兘浼氬鑷存湇鍔″櫒鍦ㄤ竴瀹氭椂闂村唴鏃犳硶杩愯銆傚強鏃舵寕鏂紒涓轰簡閬垮厤rehash瀵规湇鍔″櫒鎬ц兘鐨勫奖鍝嶏紝redis浼氬垎澶氭閫愭杩涜rehash锛屽嵆progressiverehash銆傦紙鍙互杩欐牱鐞嗚В锛岀▼搴忓彲浠ュぇ鑷寸悊瑙ｄ负绋嬪簭绌洪棽鏃剁殑rehash鎿嶄綔锛屼笉褰卞搷鍏朵粬鍛戒护鐨勬甯告墽琛屻€傦級鍝堝笇琛ㄦ笎杩涘紡rehash鐨勬楠ゅ涓嬶細棣栧厛涓篽t[1]鍝堝笇琛紝size鐨勫ぇ灏忓彇鍐充簬瑕佽繘琛岀殑鎿嶄綔锛屼互鍙奾t[0]涓綋鍓嶈妭鐐圭殑涓暟锛堝嵆ht[0]浣跨敤鐨勫睘鎬у€硷級锛氭墿瀹规搷浣滐紝ht[1]鐨剆ize鍊兼槸澶т簬绛変簬ht[0]鐨勭涓€涓€備娇鐢ㄤ簡灞炴€у€间箻浠?鐨?^n鏀剁缉鎿嶄綔锛宧t[1]鐨剆ize鍊兼槸绗?^n涓皬浜巋t[0].used灞炴€у€硷紙澶у鐔熸倝鍚楋紝鍏跺疄鍜孞ava涓殑HashMap鍜孋oncurrentHashMap鐨勬搷浣滅被浼硷級璁剧疆鍝堝笇琛ㄧ殑rehashidx鍊间粠-1鍒?锛岃〃绀洪噸鏂板搱甯屽伐浣滃紑濮嬨€傝妭鐐硅浆绉伙紝閲嶆柊璁＄畻key鐨勫搱甯屽€煎拰绱㈠紩鍊硷紝鐒跺悗灏嗚妭鐐规斁鍒癶t[1]鍝堝笇琛ㄥ搴旂殑绱㈠紩浣嶇疆銆傛瘡娆ehash浣滀笟瀹屾垚鍚庯紝绋嬪簭閮戒細灏唕ehashidx鍊煎姞涓€銆傦紙杩欓噷鐨別veryrehash鎸囩殑鏄痯rogressiverehash锛夊綋ht[0]鐨勬墍鏈夎妭鐐归兘杞Щ鍒癶t[1]鍚庯紝閲婃斁ht[0]锛屽皢ht[1]缃负ht[0]锛孾1]鏂板缓涓€涓猙lank鍝堝笇琛ㄥ苟绛夊緟涓嬩竴娆￠噸鏂板搱甯屽啀娆′娇鐢ㄣ€傦紙瀹為檯涓婏紝鏁版嵁杞Щ鍒癶t[1]鍚庯紝鍙堟仮澶嶅埌ht[0]瀛樻斁瀹為檯鏁版嵁锛岃€宧t[1]鏄竴寮犵┖琛ㄣ€傦級鏈€鍚庯紝绋嬪簭浼氶噸鏂拌缃畆ehashidx鐨勫€间负-1锛岃〃绀簉ehash鎿嶄綔宸茬粡瀹屾垚銆傜粨鏉熴€俻rogressiverehash鏃朵細涓嶄細褰卞搷瀛楀吀鐨勫叾浠栨搷浣滐紵鍥犱负鍦╬rogressiverehash鐨勮繃绋嬩腑锛屽瓧鍏镐細鍚屾椂浣跨敤ht[0]鍜宧t[1]杩欎袱涓搱甯岃〃锛屾墍浠ュ湪杩欐湡闂达紝瀛楀吀鐨勫垹闄わ紙delete锛夈€佹煡鎵撅紙find锛夈€佹洿鏂帮紙update锛夛級骞跺杩欎袱涓搱甯岃〃杩涜鍏朵粬鎿嶄綔锛涜€屽姞娉曡繍绠椾細鐩存帴鎻掑叆鍒癶t[1]涓€備緥濡傛煡鎵炬煇涓猭ey鏃讹紝绋嬪簭浼氬厛鍦╤t[0]涓煡鎵撅紝鎵句笉鍒板啀鍦╤t[1]涓煡鎵俱€傛煡璧勬枡鐨勬椂鍊欑湅鍒板緢澶氳瘎璁猴紝閮芥槸瀵归€昏緫鏈夌枒鎯戯紝杩樹妇渚嬭鏈夐棶棰橈紝浣嗘槸浠旂粏鐪嬩簡涓嬶紝閮藉拷鐣ヤ簡浼氳繘琛屽垹闄ゅ拰鏇存柊鐨勫墠鎻愬湪涓や釜鍝堝笇琛ㄦ潯浠朵笅銆傛垜鏄枃鏈殑鑻忎害浜戙€備綘涔熷彲浠ュ彨鎴戜緷浜戙€傛垜鏄竴鍚岼ava寮€鍙戦鍩熺殑灏忓鐢熴€傛枃绔犺川閲忓彲鑳戒笉鏄緢楂橈紝浣嗘垜涓€瀹氫細闈炲父鐢ㄥ績銆傝嚜涓婃鏇存柊浠ユ潵宸茬粡鏈夊緢闀挎椂闂翠簡銆備竴鏄笂娴风柅鎯呮湁鐐逛弗閲嶏紝杩樻病闈欎笅蹇冩潵鏁寸悊鐭ヨ瘑銆傚彟涓€涓槸鎴戝繀椤绘妸鐭ヨ瘑娑堝寲濂芥墠鑳芥暣鐞嗗嚭鏉ャ€傚惁鍒欙紝鎴戝叾瀹炰細鍦ㄥ悇鏂归潰閮芥湁鎵€鏀惰幏銆傚畠涓嶅ぇ锛涙墍浠ュ悗闈㈡垜鍏堟秷鍖栦竴涓嬪啀鏁寸悊鍒嗕韩銆傛垜涓嶄細杩芥眰閫熷害锛屼絾浼氳鐪熸€荤粨鏁寸悊銆傚洜涓虹柅鎯呰鍒?鏈?鍙锋墠缁撴潫锛屾垜浠皬鍖鸿繕鏈?涓槼鎬х梾渚嬶紝涓嶇煡閬撲粈涔堟椂鍊欍€傛垜浠瘡澶╂棭涓婇兘瑕佸畾濂介椆閽熷幓鎶㈣彍锛屼絾鏄繕鏄姠涓嶅埌锛屽洜涓烘病鏈夌豢鍙惰敩鑿滀緵搴斻€傛垜鎰熻鎴戝緱浜嗗彛鑵旀簝鐤°€傝繕濂戒拱浜嗙淮鐢熺礌C娉¤吘鐗囷紝鑳界◢寰紦瑙ｄ竴涓嬬柤鐥涖€傚叧浜庣柅鎯呯殑浜嬫儏澶浜嗐€備簨瀹炰笂锛屾垜鍜屽叾浠栦汉涓€鏍枫€傛湁鎯冲悆鐨勯鐗╋紝鏈夋兂鍘荤殑鍦版柟锛屾湁鎯宠鐨勪汉锛屾墍浠ユ渶鍚庤繕鏄笇鏈涚柅鎯呭揩鐐瑰ソ璧锋潵~
