寮ヨˉ閾捐〃鐨勭己闄 鍗囩淮 绌洪棿鎹㈡椂闂
– 濡備綍缁欓摼琛ㄥ姞閫
-娣诲姞绗竴绾х储寮曪紝绗簩绾х储寮 (log2n涓骇绱㈠紩)
– 鏃堕棿澶嶆潅搴﹀垎鏋
– n/2,n/4,n/8绗琸绾х储寮曡妭鐐圭殑涓暟灏辨槸n/(2^k),鍋囪绱㈠紩鏈塰绾э紝鏈楂樼骇鐨勭储寮曟湁2涓俷/(2^h)=2,浠庤屾眰寰梙=log2(n)-1
– 澧炲姞鍜屽垹闄ょ殑鏃跺欙紝瑕佹洿鏂扮储寮曪紝鎵浠ュ鍔犲拰鍒犻櫎鐨勬椂闂村鏉傚害灏变細缂栫▼logn浜
– 璺宠〃鐨勭┖闂村鏉傚害鍒嗘瀽
– 姣2涓妭鐐规娊1涓紝姣忓眰绱㈠紩鑺傜偣 n/2,n/4n/8…8,4,2 绌洪棿澶嶆潅搴︽槸O(n)
鍙傝冧簬 https://redisbook.readthedocs.io/en/latest/internal-datastruct/skiplist.html(redis璁捐涓庡疄鐜)
– redis涓轰簡婊¤冻鑷韩鐨勫姛鑳介渶瑕侊紝淇敼浜
– 鍏佽閲嶅鐨剆core鍊硷紝澶氫釜涓嶅悓鐨刴ember鐨剆core鍊煎彲浠ョ浉鍚屻
– 杩涜瀵规瘮鎿嶄綔鏃讹紝涓嶄粎瑕佹鏌core鍊硷紝杩樿妫鏌ember;褰搒core鍊煎彲浠ラ噸澶嶆椂锛屽崟闈爏core鍊兼棤娉曞垽鏂竴涓厓绱犵殑韬唤锛屾墍浠ラ渶瑕佽繛member鍩熼兘涓骞舵鏌ユ墠琛屻
– 姣忎釜鑺傜偣閮藉甫鏈変竴涓珮搴︿负1灞傜殑鍚庨鎸囬拡锛岀敤浜庝粠琛ㄥ熬鏂瑰悜琛ㄥご鏂瑰悜杩唬锛涘綋鎵цzrevrange鎴杬revrangebyscore绫讳互閫嗗簭澶勭悊鏈夊簭闆嗙殑鍛戒护鏃讹紝灏变細鐢ㄥ埌杩欎釜灞炴с
杩欎釜淇敼鐗堢殑璺宠穬琛ㄧ敱 redis.h/zskiplist 缁撴瀯瀹氫箟锛
typedef struct zskiplist {
// 澶磋妭鐐癸紝灏捐妭鐐
struct zskiplistNode *header, *tail;
// 鑺傜偣鏁伴噺
unsigned long length;
// 鐩墠琛ㄥ唴鑺傜偣鐨勬渶澶у眰鏁
int level;
} zskiplist;
璺宠穬琛ㄧ殑鑺傜偣鐢 redis.h/zskiplistNode 瀹氫箟锛
typedef struct zskiplistNode {
// member 瀵硅薄
robj *obj;
// 鍒嗗
double score;
// 鍚庨鎸囬拡
struct zskiplistNode *backward;
// 灞
struct zskiplistLevel {
// 鍓嶈繘鎸囬拡
struct zskiplistNode *forward;
// 杩欎釜灞傝法瓒婄殑鑺傜偣鏁伴噺
unsigned int span;
} level[];
} zskiplistNode;
redis> ZADD s 6 x 10 y 15 z
(integer) 3
redis> ZRANGE s 0 -1 WITHSCORES
1) "x"
2) "6"
3) "y"
4) "10"
5) "z"
6) "15"
鍦ㄥ簳灞傚疄鐜颁腑锛 Redis 涓 x 銆 y 鍜 z 涓変釜 member 鍒嗗埆鍒涘缓浜嗕笁涓瓧绗︿覆锛 鍊煎垎鍒负 double 绫诲瀷鐨 6 銆 10 鍜 15 锛 鐒跺悗鐢ㄨ烦璺冭〃灏嗚繖浜涙寚閽堟湁搴忓湴淇濆瓨璧锋潵锛 褰㈡垚杩欐牱涓涓烦璺冭〃
http://leetcode-cn.com/problems/lru-cache (LRU缂撳瓨鏈哄埗)杩愮敤浣犳墍鎺屾彙鐨勬暟鎹粨鏋勶紝璁捐鍜屽疄鐜颁竴涓 LRU (鏈杩戞渶灏戜娇鐢) 缂撳瓨鏈哄埗銆傚畠搴旇鏀寔浠ヤ笅鎿嶄綔锛 鑾峰彇鏁版嵁 get 鍜 鍐欏叆鏁版嵁 put 銆傝幏鍙栨暟鎹 get(key) 濡傛灉瀵嗛挜 (key) 瀛樺湪浜庣紦瀛樹腑锛屽垯鑾峰彇瀵嗛挜鐨勫硷紙鎬绘槸姝ｆ暟锛夛紝鍚﹀垯杩斿洖 -1銆傚啓鍏ユ暟鎹 put(key, value) – 濡傛灉瀵嗛挜宸茬粡瀛樺湪锛屽垯鍙樻洿鍏舵暟鎹硷紱濡傛灉瀵嗛挜涓嶅瓨鍦紝鍒欐彃鍏ヨ缁勩屽瘑閽/鏁版嵁鍊笺嶃傚綋缂撳瓨瀹归噺杈惧埌涓婇檺鏃讹紝瀹冨簲璇ュ湪鍐欏叆鏂版暟鎹箣鍓嶅垹闄ゆ渶涔呮湭浣跨敤鐨勬暟鎹硷紝浠庤屼负鏂扮殑鏁版嵁鍊肩暀鍑虹┖闂淬傝繘闃:
浣犳槸鍚﹀彲浠ュ湪聽O(1) 鏃堕棿澶嶆潅搴﹀唴瀹屾垚杩欎袱绉嶆搷浣滐紵
绀轰緥:
LRUCache cache = new LRUCache( 2 /* 缂撳瓨瀹归噺 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 杩斿洖 1
cache.put(3, 3); // 璇ユ搷浣滀細浣垮緱瀵嗛挜 2 浣滃簾
cache.get(2); // 杩斿洖 -1 (鏈壘鍒)
cache.put(4, 4); // 璇ユ搷浣滀細浣垮緱瀵嗛挜 1 浣滃簾
cache.get(1); // 杩斿洖 -1 (鏈壘鍒)
cache.get(3); // 杩斿洖 3
cache.get(4); // 杩斿洖 4
鍙戣〃鍥炲