Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit fe575cc

Browse filesBrowse files
ciphermagicciphermagic
committed
redis算法java实现
1 parent 73874e2 commit fe575cc
Copy full SHA for fe575cc

File tree

Expand file treeCollapse file tree

11 files changed

+449
-72
lines changed
Open diff view settings
Filter options
Expand file treeCollapse file tree

11 files changed

+449
-72
lines changed
Open diff view settings
Collapse file

‎sandbox/src/main/java/com/cipher/javassist/Example.java‎

Copy file name to clipboardExpand all lines: sandbox/src/main/java/com/cipher/javassist/Example.java
+2-2Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -105,10 +105,10 @@ public static void test05() throws Exception {
105105
}
106106

107107
public static void main(String[] args) throws Exception {
108-
// test01();
108+
test01();
109109
// test02();
110110
// test03();
111-
test04();
111+
// test04();
112112
// test05();
113113
}
114114

Collapse file

‎sandbox/src/main/java/com/cipher/jvm/Hello.java‎

Copy file name to clipboard
+14Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
package com.cipher.jvm;
2+
3+
/**
4+
* 对比 class 字节码查看
5+
*/
6+
public class Hello {
7+
8+
private static String msg = "Goods morning";
9+
10+
public static void main(String[] args) {
11+
System.out.println("msg = " + msg);
12+
}
13+
14+
}
Collapse file

‎sandbox/src/main/java/com/cipher/redis_algorithm/readme.md‎

Copy file name to clipboard
+1Lines changed: 1 addition & 0 deletions
  • Display the source diff
  • Display the rich diff
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
## redis算法java实现
Collapse file

‎sandbox/src/main/java/com/cipher/redis_algorithm/skiplist/Constant.java‎

Copy file name to clipboard
+20Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
package com.cipher.redis_algorithm.skiplist;
2+
3+
/**
4+
* 跳跃表用到的各种常量
5+
*
6+
* @author cipher
7+
*/
8+
public class Constant {
9+
10+
/**
11+
* 节点层高最大值
12+
*/
13+
public static final int ZSKIPLIST_MAXLEVEL = 64;
14+
15+
/**
16+
* 控制节点层高的概率，当 p=0.25 时，跳跃表的期望层高是 1/(1-0.25)≈1.33
17+
*/
18+
public static final float ZSKIPLIST_P = 0.25f;
19+
20+
}
Collapse file

‎sandbox/src/main/java/com/cipher/redis_algorithm/skiplist/Test.java‎

Copy file name to clipboard
+14Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
package com.cipher.redis_algorithm.skiplist;
2+
3+
public class Test {
4+
5+
public static void main(String[] args) {
6+
Zskiplist zsl = Zskiplist.zslCreate();
7+
ZskiplistOp.zslInsert(zsl, 31, "C");
8+
ZskiplistOp.zslInsert(zsl, 41, "D");
9+
ZskiplistOp.zslInsert(zsl, 21, "B");
10+
ZskiplistOp.zslInsert(zsl, 1, "A");
11+
System.out.println();
12+
}
13+
14+
}
Collapse file

‎sandbox/src/main/java/com/cipher/redis_algorithm/skiplist/Zskiplist.java‎

Copy file name to clipboard
+95Lines changed: 95 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,95 @@
1+
package com.cipher.redis_algorithm.skiplist;
2+
3+
import static com.cipher.redis_algorithm.skiplist.Constant.ZSKIPLIST_MAXLEVEL;
4+
5+
/**
6+
* 跳跃表结构，用于管理节点
7+
*
8+
* @author cipher
9+
*/
10+
public class Zskiplist {
11+
12+
/**
13+
* 指向跳跃表头节点，
14+
* 头节点是一个特殊节点，它的 level 数组元素个数固定为 64。
15+
* 头节点的 ele 为空，score 为 0
16+
* 头节点不计入跳跃表的总长度
17+
*/
18+
private ZskiplistNode header;
19+
20+
/**
21+
* 指向跳跃表尾节点，用于从后向前遍历
22+
*/
23+
private ZskiplistNode tail;
24+
25+
/**
26+
* 跳跃表的长度，除头结点外，所有节点的个数
27+
*/
28+
private int length;
29+
30+
/**
31+
* 跳跃表的高度，即跳跃表所有节点中层高最高的那个节点的层高
32+
*/
33+
private int level;
34+
35+
/**
36+
* 创建跳跃表
37+
*
38+
* @return 跳跃表结构
39+
*/
40+
public static Zskiplist zslCreate() {
41+
Zskiplist zsl = new Zskiplist();
42+
43+
// 跳跃表层高初始化为 1，长度初始化为 0
44+
zsl.level = 1;
45+
zsl.length = 0;
46+
47+
// 创建头节点，头节点不存储有序集合的 member 信息
48+
zsl.header = ZskiplistNode.zslCreateNode(ZSKIPLIST_MAXLEVEL, 0, null);
49+
50+
// 头节点的 level 数组的每项 forward 都为 null，span 值都为 0
51+
for (int j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
52+
zsl.header.getLevel()[j].setForward(null);
53+
zsl.header.getLevel()[j].setSpan(0);
54+
}
55+
56+
// 头节点的后退指针为 null
57+
zsl.header.setBackward(null);
58+
59+
// 尾节点指向 null
60+
zsl.tail = null;
61+
return zsl;
62+
}
63+
64+
public ZskiplistNode getHeader() {
65+
return header;
66+
}
67+
68+
public void setHeader(ZskiplistNode header) {
69+
this.header = header;
70+
}
71+
72+
public ZskiplistNode getTail() {
73+
return tail;
74+
}
75+
76+
public void setTail(ZskiplistNode tail) {
77+
this.tail = tail;
78+
}
79+
80+
public int getLength() {
81+
return length;
82+
}
83+
84+
public void setLength(int length) {
85+
this.length = length;
86+
}
87+
88+
public int getLevel() {
89+
return level;
90+
}
91+
92+
public void setLevel(int level) {
93+
this.level = level;
94+
}
95+
}
Collapse file

‎sandbox/src/main/java/com/cipher/redis_algorithm/skiplist/ZskiplistNode.java‎

Copy file name to clipboard
+121Lines changed: 121 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,121 @@
1+
package com.cipher.redis_algorithm.skiplist;
2+
3+
/**
4+
* 跳跃表节点
5+
* 跳跃表由多个节点构成，每个节点由多个层 {@link ZskiplistLevel} 构成
6+
*
7+
* @author cipher
8+
*/
9+
public class ZskiplistNode {
10+
11+
/**
12+
* 用于存储字符串类型的数据，
13+
* 即有序集合的 member 信息
14+
*/
15+
private String ele;
16+
17+
/**
18+
* 用于存储排序的分值，
19+
* 所有节点的分值是按从小到大排序的，
20+
* 分值相同时，按 {@link ZskiplistNode#ele} 的字典序进行排序
21+
*/
22+
private double score;
23+
24+
/**
25+
* 后退指针，只能指向当前节点最底层的前一个节点，
26+
* 头节点和第一个节点的 backward 指向 null，
27+
* 从后向前遍历跳跃表时使用
28+
*/
29+
private ZskiplistNode backward;
30+
31+
/**
32+
* 用于存储当前节点的层，数组长度为 1~64 的随机值，
33+
* 值越大概率越低
34+
*/
35+
private ZskiplistLevel[] level;
36+
37+
/**
38+
* 创建跳跃表节点时，待创建节点的层高，分值，member 等都已确定
39+
*
40+
* @param level 节点层高
41+
* @param score 分值
42+
* @param ele 元素值
43+
* @return 跳跃表节点
44+
*/
45+
public static ZskiplistNode zslCreateNode(int level, double score, String ele) {
46+
ZskiplistNode node = new ZskiplistNode();
47+
node.ele = ele;
48+
node.score = score;
49+
node.level = new ZskiplistLevel[level];
50+
for (int i = 0; i < node.level.length; i++) {
51+
node.level[i] = new ZskiplistLevel();
52+
}
53+
return node;
54+
}
55+
56+
public String getEle() {
57+
return ele;
58+
}
59+
60+
public void setEle(String ele) {
61+
this.ele = ele;
62+
}
63+
64+
public double getScore() {
65+
return score;
66+
}
67+
68+
public void setScore(double score) {
69+
this.score = score;
70+
}
71+
72+
public ZskiplistLevel[] getLevel() {
73+
return level;
74+
}
75+
76+
public void setLevel(ZskiplistLevel[] level) {
77+
this.level = level;
78+
}
79+
80+
public ZskiplistNode getBackward() {
81+
return backward;
82+
}
83+
84+
public void setBackward(ZskiplistNode backward) {
85+
this.backward = backward;
86+
}
87+
88+
/**
89+
* 节点中的层
90+
*/
91+
public static class ZskiplistLevel {
92+
93+
/**
94+
* 指向本层下一个节点，尾节点指向 null
95+
*/
96+
private ZskiplistNode forward;
97+
98+
/**
99+
* forward 指向节点与本节点之间的元素个数。
100+
* span 值越大，跳过的节点个数越多
101+
*/
102+
private int span;
103+
104+
public ZskiplistNode getForward() {
105+
return forward;
106+
}
107+
108+
public void setForward(ZskiplistNode forward) {
109+
this.forward = forward;
110+
}
111+
112+
public int getSpan() {
113+
return span;
114+
}
115+
116+
public void setSpan(int span) {
117+
this.span = span;
118+
}
119+
}
120+
121+
}

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.