跳跃表代码提交

XWxiaowei · XWxiaowei · commit a7e7cd7a49c3 · 2020-08-22T16:01:43.000+08:00
diff --git a/java-base-demo/src/main/java/com/jay/skiplist/SkipList.java b/java-base-demo/src/main/java/com/jay/skiplist/SkipList.java
@@ -0,0 +1,93 @@
+package com.jay.skiplist;
+
+import java.util.Random;
+
+/**
+ * @author xiang.wei
+ * @date 2020/8/2 3:51 PM
+ */
+public class SkipList<T> {
+    private SkipListNode<T> head, tail;
+    /**
+     * 节点总数
+     */
+    private int nodes;
+    /**
+     * 层高
+     */
+    private int listLevel;
+    /**
+     * 随机函数
+     */
+    private Random random;
+    /**
+     * 向上提升一个的概率
+     */
+    private static final double PROBABILITY = 0.5;
+
+    public SkipList() {
+        random = new Random();
+        clear();
+    }
+
+    public void clear() {
+        head = new SkipListNode<T>(SkipListNode.HEAD_KEY, null);
+        tail = new SkipListNode<T>(SkipListNode.TAIL_KEY, null);
+        // TODO: 2020/8/2
+
+        listLevel = 0;
+        nodes = 0;
+    }
+
+    public boolean isEmpty() {
+        return nodes == 0;
+    }
+
+    public int size() {
+        return nodes;
+    }
+
+    /**
+     * 在最下面一层，找到要插入的位置前面的那个key
+     * @param key
+     * @return
+     */
+    private SkipListNode<T> findNode(int key) {
+        SkipListNode<T> p = head;
+        while (true) {
+            while (p.right.getKey() != SkipListNode.TAIL_KEY
+                    && p.right.getKey() <= key) {
+                p = p.right;
+            }
+            if (p.down != null) {
+                p = p.down;
+            } else {
+                break;
+            }
+        }
+        return p;
+    }
+
+    /**
+     * 查询是否存储key,存在则返回该节点，否则返回null
+     * @param key
+     * @return
+     */
+    public SkipListNode<T> search(int key) {
+        SkipListNode<T> p = findNode(key);
+        if (key == p.getKey()) {
+            return p;
+        } else {
+            return null;
+        }
+    }
+
+    public void put(int k, T v) {
+        SkipListNode<T> p = findNode(k);
+        //如果key值相同，替换原来的value即可结束
+        if (k == p.getKey()) {
+            p.setValue(v);
+            return;
+        }
+    }
+}
diff --git a/java-base-demo/src/main/java/com/jay/skiplist/SkipListNode.java b/java-base-demo/src/main/java/com/jay/skiplist/SkipListNode.java
@@ -0,0 +1,70 @@
+package com.jay.skiplist;
+
+/**
+ * 跳跃表的节点，包括key-value和上下左右4个指针
+ * @author xiang.wei
+ * @date 2020/8/2 3:34 PM
+ */
+public class SkipListNode<T> {
+    private int key;
+    private T value;
+    /**
+     * 上下左右 四个指针
+     */
+    public SkipListNode<T> up,down,left, right;
+
+    /**
+     * 负无穷
+     */
+    public static final int HEAD_KEY = Integer.MIN_VALUE;
+    /**
+     * 正无穷
+     */
+    public static final int TAIL_KEY = Integer.MAX_VALUE;
+
+    public SkipListNode(int key, T value) {
+        this.key = key;
+        this.value = value;
+    }
+
+    public int getKey() {
+        return key;
+    }
+
+    public void setKey(int key) {
+        this.key = key;
+    }
+
+    public T getValue() {
+        return value;
+    }
+
+    public void setValue(T value) {
+        this.value = value;
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (this == obj) {
+            return true;
+        }
+        if (obj == null) {
+            return false;
+        }
+        if (!(obj instanceof SkipListNode<?>)) {
+            return false;
+        }
+        SkipListNode<T> ent;
+        try {
+            ent = (SkipListNode<T>) obj;
+        } catch (Exception e) {
+            return false;
+        }
+        return (ent.getKey() == key) && (ent.getValue() == value);
+    }
+
+    @Override
+    public String toString() {
+        return super.toString();
+    }
+}
diff --git a/java-base-demo/src/main/java/com/jay/skiplist/SkipListTest.java b/java-base-demo/src/main/java/com/jay/skiplist/SkipListTest.java
@@ -0,0 +1,8 @@
+package com.jay.skiplist;
+
+/**
+ * @author xiang.wei
+ * @date 2020/8/2 3:22 PM
+ */
+public class SkipListTest {
+}
