深圳画册设计网站,wordpress 语言切换,网站开发的目的意义,德惠市城乡建设局网站跳表#xff08;Skip List#xff09;是一种随机化的数据结构#xff0c;基于有序链表#xff0c;通过在链表上增加多级索引来提高数据的查找效率。它是由 William Pugh 在 1990 年提出的。 为什么 Redis 中的 Sorted Set 使用跳跃表
Redis 的有序集合#xff08;Sorted … 跳表Skip List是一种随机化的数据结构基于有序链表通过在链表上增加多级索引来提高数据的查找效率。它是由 William Pugh 在 1990 年提出的。 为什么 Redis 中的 Sorted Set 使用跳跃表
Redis 的有序集合Sorted Set使用跳跃表Skip List作为底层实现主要是因为跳跃表在性能、实现复杂度和灵活性等方面具有显著优势可以替代平衡树的数据结构。
跳跃表的原理
跳跃表是一种扩展的有序链表通过维护多个层级的索引来提高查找效率。每个节点包含一个数据元素和一组指向其他节点的指针这些指针分布在不同的层级。最底层的链表包含所有元素而每一层的节点数量逐渐减少。这样查找操作可以从高层开始快速跳过不需要的元素减少遍历的节点数从而提高查找效率。 查找过程从最高层的头节点开始沿着索引节点向右查找如果当前节点的下一个节点的值大于或等于查找的目标值则向下移动到下一层继续查找否则向右移动到下一个索引节点。这个过程一直持续到找到目标节点或到达最底层链表。 插入和删除操作跳跃表支持高效的动态插入和删除时间复杂度均为 O(log n)。插入时首先找到插入位置然后根据随机函数决定新节点的层数最后在相应的层中插入节点。
跳跃表的优势 简单性跳跃表的实现相对简单易于理解和维护而平衡树如红黑树的实现较为复杂容易出错。 高效的范围查询跳跃表在进行范围查询时效率更高因为它是有序的链表可以直接遍历后继节点而平衡树需要中序遍历复杂度更高。 灵活性跳跃表的层数可以根据需要动态调整适应不同的查询需求。 高并发性能跳跃表的节点可以支持多个线程同时插入或删除节点而平衡树和哈希表通常需要复杂的并发控制。 空间效率跳跃表的空间复杂度为 O(n)并且通过调整节点的抽取间隔可以灵活平衡空间和时间复杂度。
正是因为有这些优势Redis 选择使用跳跃表来实现有序集合而不是红黑树或其他数据结构。这使得 Redis 在处理有序集合时能够高效地支持插入、删除和查找操作同时保持元素的有序性非常适合实现如排行榜、范围查询等功能。
为了讲明白跳表的原理现在我们来模拟一个简单的跳表实现。
在 Java 中模拟实现 Redis 的 Sorted Set 跳表我们需要定义跳表的数据结构包括节点和跳表本身。以下是一个简单的实现
import java.util.Random;public class SkipList {private static final double P 0.5; // 节点晋升的概率private static final int MAX_LEVEL 16; // 最大层数private int levelCount; // 当前跳表的层数private Node head; // 头节点private int size; // 跳表中元素的数量private Random random; // 随机数生成器public SkipList() {this.levelCount 0;this.size 0;this.head new Node(-1, Integer.MIN_VALUE, MAX_LEVEL);this.random new Random();}// 节点定义private class Node {int value;int key;Node[] forward; // 向前指针数组Node(int value, int key, int level) {this.value value;this.key key;this.forward new Node[level 1];}}// 随机生成节点的层数private int randomLevel() {int level 0;while (random.nextFloat() P level MAX_LEVEL) {level;}return level;}// 搜索指定值的节点public Node search(int key) {Node current head;for (int i levelCount - 1; i 0; i--) {while (current.forward[i] ! null current.forward[i].key key) {current current.forward[i]; // 沿着当前层的指针移动}}current current.forward[0]; // 移动到第0层return current;}// 插入节点public void insert(int key, int value) {Node[] update new Node[MAX_LEVEL 1];Node current head;// 查找插入位置for (int i levelCount - 1; i 0; i--) {while (current.forward[i] ! null current.forward[i].key key) {current current.forward[i];}update[i] current;}int level randomLevel(); // 随机生成层数if (level levelCount) {levelCount level;for (int i levelCount - 1; i 0; i--) {update[i] head;}}current new Node(value, key, level);for (int i 0; i level; i) {current.forward[i] update[i].forward[i];update[i].forward[i] current;}size;}// 删除节点public void delete(int key) {Node[] update new Node[MAX_LEVEL 1];Node current head;// 查找要删除的节点for (int i levelCount - 1; i 0; i--) {while (current.forward[i] ! null current.forward[i].key key) {current current.forward[i];}update[i] current;}current current.forward[0];if (current ! null current.key key) {for (int i 0; i levelCount; i) {if (update[i].forward[i] ! current) {break;}update[i].forward[i] current.forward[i];}size--;while (levelCount 0 head.forward[levelCount - 1] null) {levelCount--;}}}// 打印跳表public void printList() {Node current head.forward[0];while (current ! null) {System.out.println(current.key : current.value);current current.forward[0];}}// 主函数测试跳表public static void main(String[] args) {SkipList list new SkipList();list.insert(3, 100);list.insert(6, 300);list.insert(4, 400);list.insert(7, 700);list.insert(5, 500);list.printList();list.delete(3);list.printList();}
}下面V 哥来解释一下 跳表节点每个节点包含一个值、一个键和一个向前指针数组。向前指针数组存储了指向同一层下一个节点的引用。 随机层数每个节点的层数是根据预设的概率 P 随机生成的这样可以模拟出不同高度的索引层。 搜索操作从最高层开始沿着当前层的指针移动直到找到插入点或到达底层。 插入操作首先找到插入位置然后根据随机生成的层数创建新节点并更新每一层的指针。 删除操作找到要删除的节点然后逐层更新指针最后减少跳表的层数。 打印跳表从底层的头节点开始遍历打印每个节点的键和值。
从这个简化版的跳表实现可以看到跳表的基本操作。可以帮助我们理解跳表实现的原理。
如何在 Java 中实现跳表的并发操作
在 Java 中实现跳表的并发操作需要考虑线程安全问题。可以通过以下方法来实现 使用同步块在每个公共方法中使用 synchronized 关键字来确保同一时间只有一个线程可以执行方法。 使用锁使用 ReentrantLock 或其他并发锁来控制对跳表的并发访问。 使用原子引用使用 AtomicReference 或 AtomicReferenceArray 来确保节点的原子更新。 使用并发集合使用 ConcurrentHashMap 等并发集合作为辅助工具来实现线程安全的跳表。
以下是一个使用 synchronized 关键字实现线程安全的跳表的示例
import java.util.Random;public class ConcurrentSkipList {private static final double P 0.5; // 节点晋升的概率private static final int MAX_LEVEL 16; // 最大层数private int levelCount; // 当前跳表的层数private Node head; // 头节点private int size; // 跳表中元素的数量private Random random; // 随机数生成器public ConcurrentSkipList() {this.levelCount 0;this.size 0;this.head new Node(-1, Integer.MIN_VALUE, MAX_LEVEL);this.random new Random();}private class Node {int value;int key;Node[] forward; // 向前指针数组Node(int value, int key, int level) {this.value value;this.key key;this.forward new Node[level 1];}}private int randomLevel() {int level 0;while (random.nextFloat() P level MAX_LEVEL) {level;}return level;}public synchronized Node search(int key) {Node current head;for (int i levelCount - 1; i 0; i--) {while (current.forward[i] ! null current.forward[i].key key) {current current.forward[i];}}current current.forward[0];return current;}public synchronized void insert(int key, int value) {Node[] update new Node[MAX_LEVEL 1];Node current head;for (int i levelCount - 1; i 0; i--) {while (current.forward[i] ! null current.forward[i].key key) {current current.forward[i];}update[i] current;}int level randomLevel();if (level levelCount) {for (int i levelCount; i level; i) {update[i] head;}levelCount level;}current new Node(value, key, level);for (int i 0; i level; i) {current.forward[i] update[i].forward[i];update[i].forward[i] current;}size;}public synchronized void delete(int key) {Node[] update new Node[MAX_LEVEL 1];Node current head;for (int i levelCount - 1; i 0; i--) {while (current.forward[i] ! null current.forward[i].key key) {current current.forward[i];}update[i] current;}current current.forward[0];if (current ! null current.key key) {for (int i 0; i levelCount; i) {if (update[i].forward[i] ! current) {break;}update[i].forward[i] current.forward[i];}size--;while (levelCount 0 head.forward[levelCount - 1] null) {levelCount--;}}}public synchronized void printList() {Node current head.forward[0];while (current ! null) {System.out.println(current.key : current.value);current current.forward[0];}}public static void main(String[] args) {ConcurrentSkipList list new ConcurrentSkipList();list.insert(3, 100);list.insert(6, 300);list.insert(4, 400);list.insert(7, 700);list.insert(5, 500);list.printList();list.delete(3);list.printList();}
}在这个示例中我们使用了 synchronized 关键字来确保 search、insert 和 delete 方法是线程安全的。这会锁定当前对象确保同一时间只有一个线程可以执行这些方法。
请注意虽然 synchronized 可以提供线程安全但它也可能导致性能瓶颈特别是在高并发环境下。在实际应用中可以考虑使用更细粒度的锁如 ReentrantLock或者使用原子引用和其他并发工具来提高性能。
使用 ReentrantLock 的实现方式
使用 ReentrantLock 实现跳表的并发操作可以提供比 synchronized 更细粒度的锁定从而提高并发性能。ReentrantLock 允许您在不同的方法中锁定和解锁甚至可以在不同的类中使用同一个锁对象。
以下是使用 ReentrantLock 实现线程安全的跳表的示例
import java.util.Random;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;public class ConcurrentSkipList {private static final double P 0.5; // 节点晋升的概率private static final int MAX_LEVEL 16; // 最大层数private final Lock lock new ReentrantLock(); // 创建一个 ReentrantLock 对象private int levelCount; // 当前跳表的层数private Node head; // 头节点private int size; // 跳表中元素的数量private Random random; // 随机数生成器public ConcurrentSkipList() {this.levelCount 0;this.size 0;this.head new Node(Integer.MIN_VALUE, MAX_LEVEL);this.random new Random();}private class Node {int value;int key;Node[] forward; // 向前指针数组Node(int key, int level) {this.key key;this.forward new Node[level 1];}}private int randomLevel() {int level 0;while (random.nextFloat() P level MAX_LEVEL) {level;}return level;}public void search(int key) {lock.lock(); // 加锁try {Node current head;for (int i levelCount - 1; i 0; i--) {while (current.forward[i] ! null current.forward[i].key key) {current current.forward[i];}}current current.forward[0];// ... 处理找到的节点} finally {lock.unlock(); // 释放锁}}public void insert(int key, int value) {lock.lock(); // 加锁try {Node[] update new Node[MAX_LEVEL 1];Node current head;for (int i levelCount - 1; i 0; i--) {while (current.forward[i] ! null current.forward[i].key key) {current current.forward[i];}update[i] current;}int level randomLevel();if (level levelCount) {levelCount level;}current new Node(value, key, level);for (int i 0; i level; i) {current.forward[i] update[i].forward[i];update[i].forward[i] current;}size;} finally {lock.unlock(); // 释放锁}}public void delete(int key) {lock.lock(); // 加锁try {Node[] update new Node[MAX_LEVEL 1];Node current head;for (int i levelCount - 1; i 1; i--) {while (current.forward[i] ! null current.forward[i].key key) {current current.forward[i];}update[i] current;}current current.forward[0];if (current ! null current.key key) {for (int i 0; i levelCount; i) {if (update[i].forward[i] ! current) {break;}update[i].forward[i] current.forward[i];}size--;while (levelCount 0 head.forward[levelCount - 1] null) {levelCount--;}}} finally {lock.unlock(); // 释放锁}}public void printList() {lock.lock(); // 加锁try {Node current head.forward[0];while (current ! null) {System.out.println(current.key : current.value);current current.forward[0];}} finally {lock.unlock(); // 释放锁}}public static void main(String[] args) {ConcurrentSkipList list new ConcurrentSkipList();list.insert(3, 100);list.insert(6, 300);list.insert(4, 400);list.insert(7, 700);list.insert(5, 500);list.printList();list.delete(3);list.printList();}
}在这个示例中我们使用了 ReentrantLock 对象来控制对跳表的并发访问。每个公共方法在执行之前都会调用 lock.lock() 加锁并在执行完毕后包括正常执行和异常退出调用 lock.unlock() 释放锁。
使用 ReentrantLock 的好处是它提供了比 synchronized 更灵活的锁定机制例如 可中断的锁定ReentrantLock 允许线程在尝试获取锁时被中断。 尝试非阻塞锁定ReentrantLock 提供了 tryLock() 方法允许线程尝试获取锁而不无限等待。 超时获取锁ReentrantLock 还提供了 tryLock(long timeout, TimeUnit unit) 方法允许线程在指定时间内等待锁。 公平锁ReentrantLock 可以选择是否使用公平锁公平锁会按照线程请求锁的顺序来分配锁。 多个条件变量ReentrantLock 可以与多个 Condition 对象配合使用而 synchronized 只能与一个条件变量配合使用。
理解了以上代码实现原理后我们再来理解 Redis Sorted Set 就不难了。
Redis 的 Sorted Set 是一种包含元素和关联分数的数据结构它能够根据分数对元素进行排序。Sorted Set 在 Redis 中的内部实现可以是跳跃表Skip List和字典Hash Table的组合或者是压缩列表Zip List具体使用哪种实现取决于 Sorted Set 的大小和元素的长度。
跳跃表 字典实现
当 Sorted Set 的元素数量较多或者元素长度较长时Redis 使用跳跃表和字典来实现 Sorted Set。跳跃表是一种概率平衡的数据结构它通过多级索引来提高搜索效率类似于二分查找。字典则用于快速查找和更新操作。
跳跃表的每个节点包含以下信息
元素member分数score后退指针backward多层前进指针forward每一层都是一个有序链表
字典则存储了元素到分数的映射以便快速访问。
压缩列表实现
当 Sorted Set 的元素数量较少默认小于128个并且所有元素的长度都小于64字节时Redis 使用压缩列表来存储 Sorted Set。压缩列表是一种连续内存块的顺序存储结构它将所有的元素和分数紧凑地存储在一起以节省内存空间。
应用场景
Sorted Set 常用于以下场景
排行榜例如游戏中的玩家分数排名。范围查询例如获取一定分数范围内的用户。任务调度例如按照任务的优先级执行。实时排名例如股票价格的实时排名。
代码分析
在 Redis 源码中Sorted Set 的实现主要在 t_zset.c 文件中。插入操作zaddCommand会根据 Sorted Set 的编码类型跳跃表或压缩列表来执行不同的逻辑。如果是跳跃表编码那么插入操作会涉及到字典的更新和跳跃表节点的添加。如果是压缩列表编码则会检查是否需要转换为跳跃表编码。
总结
Sorted Set 是 Redis 提供的一种强大的有序数据结构它结合了跳跃表和字典的优点提供了高效的插入、删除、更新和范围查询操作。通过合理的使用 Sorted Set可以有效地解决许多实际问题。如何以上内容对你有帮助恳请点赞转发V 哥在此感谢各位兄弟的支持。88洗洗睡了。 文章转载自： http://www.morning.xllrf.cn.gov.cn.xllrf.cn http://www.morning.mkkcr.cn.gov.cn.mkkcr.cn http://www.morning.rtqyy.cn.gov.cn.rtqyy.cn http://www.morning.hkysq.cn.gov.cn.hkysq.cn http://www.morning.wjndl.cn.gov.cn.wjndl.cn http://www.morning.hjbrd.cn.gov.cn.hjbrd.cn http://www.morning.fpbj.cn.gov.cn.fpbj.cn http://www.morning.rydhq.cn.gov.cn.rydhq.cn http://www.morning.btnmj.cn.gov.cn.btnmj.cn http://www.morning.fpqq.cn.gov.cn.fpqq.cn http://www.morning.tslfz.cn.gov.cn.tslfz.cn http://www.morning.ljcf.cn.gov.cn.ljcf.cn http://www.morning.fqyqm.cn.gov.cn.fqyqm.cn http://www.morning.gbjxj.cn.gov.cn.gbjxj.cn http://www.morning.mqldj.cn.gov.cn.mqldj.cn http://www.morning.yggwn.cn.gov.cn.yggwn.cn http://www.morning.drywd.cn.gov.cn.drywd.cn http://www.morning.ycgrl.cn.gov.cn.ycgrl.cn http://www.morning.pclgj.cn.gov.cn.pclgj.cn http://www.morning.saletj.com.gov.cn.saletj.com http://www.morning.tktyh.cn.gov.cn.tktyh.cn http://www.morning.llgpk.cn.gov.cn.llgpk.cn http://www.morning.kbdrq.cn.gov.cn.kbdrq.cn http://www.morning.wnnlr.cn.gov.cn.wnnlr.cn http://www.morning.clyhq.cn.gov.cn.clyhq.cn http://www.morning.xhlht.cn.gov.cn.xhlht.cn http://www.morning.dzyxr.cn.gov.cn.dzyxr.cn http://www.morning.ykmg.cn.gov.cn.ykmg.cn http://www.morning.rykmz.cn.gov.cn.rykmz.cn http://www.morning.dmtld.cn.gov.cn.dmtld.cn http://www.morning.neletea.com.gov.cn.neletea.com http://www.morning.nwrzf.cn.gov.cn.nwrzf.cn http://www.morning.nlnmy.cn.gov.cn.nlnmy.cn http://www.morning.jwefry.cn.gov.cn.jwefry.cn http://www.morning.ggnfy.cn.gov.cn.ggnfy.cn http://www.morning.qyglt.cn.gov.cn.qyglt.cn http://www.morning.nzkkh.cn.gov.cn.nzkkh.cn http://www.morning.fhkr.cn.gov.cn.fhkr.cn http://www.morning.c7630.cn.gov.cn.c7630.cn http://www.morning.xphls.cn.gov.cn.xphls.cn http://www.morning.ndtmz.cn.gov.cn.ndtmz.cn http://www.morning.pmdnx.cn.gov.cn.pmdnx.cn http://www.morning.pbmkh.cn.gov.cn.pbmkh.cn http://www.morning.hclplus.com.gov.cn.hclplus.com http://www.morning.hnrpk.cn.gov.cn.hnrpk.cn http://www.morning.wnmdt.cn.gov.cn.wnmdt.cn http://www.morning.qtqjx.cn.gov.cn.qtqjx.cn http://www.morning.bpzw.cn.gov.cn.bpzw.cn http://www.morning.mlcwl.cn.gov.cn.mlcwl.cn http://www.morning.thpzn.cn.gov.cn.thpzn.cn http://www.morning.lsxabc.com.gov.cn.lsxabc.com http://www.morning.zgdnz.cn.gov.cn.zgdnz.cn http://www.morning.xtqr.cn.gov.cn.xtqr.cn http://www.morning.sxbgc.cn.gov.cn.sxbgc.cn http://www.morning.twhgn.cn.gov.cn.twhgn.cn http://www.morning.lkwyr.cn.gov.cn.lkwyr.cn http://www.morning.gcjhh.cn.gov.cn.gcjhh.cn http://www.morning.mmjqk.cn.gov.cn.mmjqk.cn http://www.morning.gqjqf.cn.gov.cn.gqjqf.cn http://www.morning.wknbc.cn.gov.cn.wknbc.cn http://www.morning.ycwym.cn.gov.cn.ycwym.cn http://www.morning.zkqsc.cn.gov.cn.zkqsc.cn http://www.morning.pkrb.cn.gov.cn.pkrb.cn http://www.morning.ykrck.cn.gov.cn.ykrck.cn http://www.morning.hxmqb.cn.gov.cn.hxmqb.cn http://www.morning.gsjfn.cn.gov.cn.gsjfn.cn http://www.morning.mmxnb.cn.gov.cn.mmxnb.cn http://www.morning.nxzsd.cn.gov.cn.nxzsd.cn http://www.morning.kqkmx.cn.gov.cn.kqkmx.cn http://www.morning.gwtbn.cn.gov.cn.gwtbn.cn http://www.morning.cxtbh.cn.gov.cn.cxtbh.cn http://www.morning.ggnjq.cn.gov.cn.ggnjq.cn http://www.morning.fydsr.cn.gov.cn.fydsr.cn http://www.morning.wrlxt.cn.gov.cn.wrlxt.cn http://www.morning.mywmb.cn.gov.cn.mywmb.cn http://www.morning.rkqkb.cn.gov.cn.rkqkb.cn http://www.morning.rsdm.cn.gov.cn.rsdm.cn http://www.morning.pxmyw.cn.gov.cn.pxmyw.cn http://www.morning.bwrbm.cn.gov.cn.bwrbm.cn http://www.morning.haolipu.com.gov.cn.haolipu.com
