Rust 跳表

原创 Eagle1949 技术源泉

前面几个章节我们讲过了链表，可以发现它有一个特点，查找某个元素时，我们需要迭代进行查询，如果链表长度很小，那么查询也是很快的，如果链表很大，那么查询就得靠运气了，查找的节点在链表的前部，还是很快，在链表的尾部，那么就几乎迭代整个链表了。为了改进查找的效率，及不依赖运气，计算机先驱们，设计了跳表算法，跳表的核心就是能够跳过一些节点查找，😄。

在实际实现中，我们按照下面图示进行实现，

它有一个前提，就是节点需要排序。

我们先看布局

use std::{cell::RefCell, rc::Rc};
type Link = Option<Rc<RefCell<Node>>>;
struct Node {    next: Vec<Link>,    pub value: u64,}
impl Node {    fn new(next: Vec<Link>, value: u64) -> Rc<RefCell<Node>> {        Rc::new(RefCell::new(Node { next, value }))    }}
pub(crate) struct SkipList {    head: Link,    tails: Vec<Link>,    max_level: usize,    pub length: u64,}

我们实现新增，查找。新增的关键点是循环每个层，当每个层的尾部节点有值时，将它的下一个节点指向这个新节点，然后再将尾部节点指向这个节点。

tail-->old node ，old node --> new node ,tail --> new node

impl SkipList {   pub  fn new(level: usize) -> Self {        Self {            head: None,            tails: vec![None; level],            max_level: level-1, // 需要，否则报溢出            length: 0,        }    }// 随机抛硬币，获得层数    fn get_level(&self) -> usize {        let mut n = 0;        while rand::random::<bool>() && n < self.max_level {            n += 1;        }        n    }// 添加，第一个节点，有最大层数    pub fn append(&mut self, value: u64) {        let level = 1+if self.head.is_none() {            self.max_level-1        } else {            self.get_level()        };// 创建新的节点        let new = Node::new(vec![None; level], value);        for i in 0..level {            if let Some(old) = self.tails[i].take() {                let next = &mut old.borrow_mut().next;                next[i] = Some(new.clone());            }            self.tails[i] = Some(new.clone());        }
        if self.head.is_none() {            self.head = Some(new.clone());        }
        self.length += 1;    }// 查找    pub fn find(&self, value: u64) -> Option<u64> {        match self.head {            Some(ref head) => {            // 先从最大层，最高层查找                let mut start_level = self.max_level;                let node = head.clone();                let mut result = None;                // 获取到某层有节点，退出取出层数。                loop {                    if node.borrow().next[start_level].is_some() {                        break;                    }                    start_level -= 1;                }// 得到这个节点                let mut n = node;// 从这个高层开始迭代                for level in (0..=start_level).rev() {                // 找到它的值，如果获取的值大于要找的值，                // 它退出循环，可以得到当前的节点                // 否则，获取它额下一个节点继续比较                    loop {                        let next = n.clone();                        match next.borrow().next[level] {                            Some(ref next) if next.borrow().value <= value => n = next.clone(),                            _ => break                                                   };                    }                    // 确认当前的节点值是否相同                    if n.borrow().value == value {                        let tmp = n.borrow();                        result = Some(tmp.value);                        break;                    }                }                result            }            None => None,        }    }}

我们测试


fn main(){    let now = Instant::now();    let mut list = skip_list::SkipList::new(10);     // 从小到大的排序    for i in 1..1000{        list.append(i);    }
   let result= list.find(200);   match result {    Some(_) => println!("find"),    None => println!("not found"),}
    println!("the cost is {:?}",now.elapsed());}

删除节点我没有实现，还有一些其他的功能，欢迎你来实现。

你有好的想法和建议，欢迎留言！

继续滑动看下一个