数据结构与算法跳表之java实现

拼搏现实的明天。 2023-02-28 05:22 10阅读 0赞

# 跳表 #

一个有序链表的搜索、添加、删除的平均时间复杂度都为O(n)，那么能否利用二分搜索优化有序链表，将搜索、添加、删除的平均时间复杂度降低至O(logn)呢？

链表没有像数组那样的高效随机访问（O(1)时间复杂度），所以不能像有序数组那样直接进行二分搜索优化。

那有没有其他办法让有序链表的搜索、添加、删除的平均时间复杂度降低至O(logn)？答案是使用跳表。

## 跳表的介绍 ##

跳表（SkipList），又叫做跳跃表、跳跃列表，在有序链表的基础上增加了“跳跃”的功能，由William Pugh于1990年发布，设计的初衷是为了取代平衡树（比如红黑树）。

Redis中的SortedSet、LevelDB中的MemTable都用到了跳表。

与平衡二叉树的对比

*  跳表的实现和维护会更加简单
 *  跳表的搜索、删除、添加的平均时间复杂度是O(logn)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70]

## 跳表的数据结构 ##

public class SkipList<K, V> { 
    
        public static final int MAX_LEVEL = 32; // 跳表的最大层数
    
        public static final double P = 0.25;
    
        private Comparator<K> comparator;
    
        private int size; // 节点的个数
    
        private int level; // 跳表的层数
    
        private Node<K, V> first = new Node<>(null, null, MAX_LEVEL); // 头节点
    
        public SkipList() { 
            this(null);
        }
    
        public SkipList(Comparator<K> comparator) { 
            this.comparator = comparator;
        }
    
        public int size() { 
            return size;
        }
    
        public boolean isEmpty() { 
            return 0 == size;
        }
    ...
    ...
        private static class Node<K, V> { 
            K key;
            V value;
            Node<K, V>[] nexts;
            private int level;
    
            public Node(K key, V value, int level) { 
                this.key = key;
                this.value = value;
                this.level = level;
                this.nexts = new Node[level];
            }
    
            @Override
            public String toString() { 
                return key + ":" + value + "_" + nexts.length;
            }
        }
    
    }

## 跳表的搜索 ##

1.  从顶层链表的首元素开始，从左往右搜索，直至找到一个大于或等于目标的元素，或者到达当前层链表的尾部。
2.  如果该元素等于目标元素，则表明该元素已被找到。
3.  如果该元素大于目标元素或已到达链表的尾部，则退回到当前层的前一个元素，然后转入下一层进行搜索。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 1]

代码实现如下：

public V get(K key) { 
    
            keyCheck(key);
    
            Node<K, V> node = first;
    
            for (int i = level- 1; i >= 0; i--) { 
    
                int cmp = -1;
                while (null != node.nexts[i] && (cmp = compare(node.nexts[i].key, key)) < 0) { 
                    node = node.nexts[i];
                }
    
                if(cmp == 0) { 
                    // key相等
                    return node.nexts[i].value;
                }
            }
            return null;
        }
    
        private int compare(K k1, K k2) { 
            if(null != comparator) { 
                return comparator.compare(k1, k2);
            }
            return ((Comparable<K>) k1).compareTo(k2);
        }
    
        private void keyCheck(K key) { 
            if (key == null) { 
                throw new IllegalArgumentException("key must not be null.");
            }
        }

## 跳表的添加 ##

1.  创建一个新的节点，随机决定新添加节点的层数。
2.  找到新节点的所有前驱节点。
3.  将新节点插入到每一层的链表中。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 2]  
代码实现如下：

/** * key不存在则添加节点，key存在则将value替换为新值，返回旧值 * @param key * @param value * @return */
        public V put(K key, V value) { 
            keyCheck(key);
    
            Node<K, V> node = first;
    
            Node<K, V>[] previousNodes = new Node[level]; // 前驱节点
    
            for (int i = level - 1; i >= 0; i--) { 
    
                int cmp = -1;
    
                while (null != node.nexts[i] && (cmp = compare(node.nexts[i].key, key)) < 0) { 
                    node = node.nexts[i];
                }
    
                if(cmp == 0) { 
                    // key相等
                    V oldValue = node.nexts[i].value;
                    node.nexts[i].value = value;
                    return oldValue;
                }
    
                previousNodes[i] = node;
            }
    
            int newLevel = randomLevel();
    
            Node<K, V> newNode = new Node<>(key, value, newLevel);
    
            // 维护前驱和后继
            for (int i = 0; i < newLevel; i++) { 
                if(i < previousNodes.length) { 
                    newNode.nexts[i] = previousNodes[i].nexts[i];
                    previousNodes[i].nexts[i] = newNode;
                } else { 
                    first.nexts[i] = newNode;
                }
            }
            size++;
    
            this.level = Integer.max(newLevel, this.level); // 更新最大层数
            return null;
        }
    
        /** * 随机返回层数 * @return */
        private int randomLevel() { 
            int level = 1;
            while (Math.random() < P && level < MAX_LEVEL) { 
                level++;
            }
            return level;
        }

## 跳表的删除 ##

1.  找到要删除的节点和所有的前驱节点。
2.  将要删除的节点从每一层的链表中删除。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 3]

public V remove(K key) { 
            keyCheck(key);
            
            Node<K, V> node = first;
    
            Node<K, V>[] previousNodes = new Node[level]; // 前驱节点
    
            boolean isExist = false;
    
            for (int i = level - 1; i >= 0; i--) { 
    
                int cmp = -1;
                while (null != node.nexts[i] && (cmp = compare(node.nexts[i].key, key)) < 0) { 
                    node = node.nexts[i];
                }
    
                if(cmp == 0) { 
                    isExist = true;
                }
    
                previousNodes[i] = node;
            }
    
            if(!isExist) { 
                // key不存在返回null
                return null;
            }
    
            Node<K, V> removeNode = node.nexts[0];
    
            for (int i = 0; i < removeNode.level; i++) { 
                previousNodes[i].nexts[i] = removeNode.nexts[i];
            }
    
            size--;
    
            // 更新跳表的层数
            int newLevel = level;
            while (--newLevel >= 0 && first.nexts[newLevel] == null) { 
                level = newLevel;
            }
            return removeNode.value;
        }

## 跳表的层数 ##

跳表是按层构造的，底层是一个普通的有序链表，高层相当于是低层的“快速通道”也可以称之为多层索引。

在第i层中的元素按某个固定的概率 p（通常为 1 / 2 1/2 1/2或 1 / 4 1/4 1/4）出现在第i+1层中，产生越高的层数，概率越低

*  元素层数恰好等于1的概率为  1 – p 1–p 1–p
 *  元素层数大于等于2的概率为  p p p，而元素层数恰好等于2的概率为  p ∗ ( 1 – p ) p\*(1–p) p∗(1–p)
 *  元素层数大于等于3的概率为  p 2 p^2 p2，而元素层数恰好等于3的概率为  p 2 ∗ ( 1 – p ) p^2\*(1–p) p2∗(1–p)
 *  元素层数大于等于4的概率为  p 3 p^3 p3，而元素层数恰好等于4的概率为  p 3 ∗ ( 1 – p ) p^3\*(1–p) p3∗(1–p)
 *  …
 *  一个元素的平均层数是 1 / ( 1 – p ) 1/(1 – p) 1/(1–p)

![在这里插入图片描述][20200720111528404.png]  
当p=1/2时，每个元素所包含的平均指针数量是2。

当p=1/4时，每个元素所包含的平均指针数量是1.33（优于平衡二叉树的固定指针数量2）。

## 跳表的复杂度分析 ##

每一层的元素数量，其中n为数据规模：

*  第1层链表固定有 n n n个元素
 *  第2层链表平均有 n ∗ p n\*p n∗p个元素
 *  第3层链表平均有 n ∗ p 2 n\*p^2 n∗p2个元素
 *  第k层链表平均有 n ∗ p k n\*p^k n∗pk个元素

最高层的层数是 log ⁡ 1 p n \\log\_\\frac\{1\}\{p\}n logp1n ，平均有个 1 / p 1/p 1/p元素。

在搜索时，每一层链表的预期查找步数最多是 1 / p 1/p 1/p，所以总的查找步数是 – ( log ⁡ p n p ) –(\\frac\{\\log\_pn\}\{p\}) –(plogpn)，时间复杂度是O(logn)。

更多精彩内容关注本人公众号：架构师升级之路  
![在这里插入图片描述][20200627175030665.jpg]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70]: /images/20230209/5a239febdb414215ad0f35b2bba54634.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 1]: /images/20230209/0eec98ce68df4c6f83c0be95745bfa36.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 2]: /images/20230209/d66d3e24cebd4faba3d4e08e4cbb84ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 3]: /images/20230209/c043c71b5ad349b3a1773e0c03d7d4a5.png
[20200720111528404.png]: /images/20230209/2cf6fd8a97444b7e9c766cfd2eac0cca.png
[20200627175030665.jpg]: /images/20230209/488aa9e363d94c4ab21070e159d10380.png