README

Yaambo 是一个包含并发跳表实现的库。

并发跳表是多线程的跳表数据结构实现。它是一种概率数据结构，允许快速插入、删除和查找元素。它在空间使用方面也很高效。

跳表是一种具有多个层的链表。每一层是一个包含键和值的节点的链表。键按升序排序。跳表的较高层跳过了大量的节点，这使得查找操作非常高效。

并发跳表使用手牵手锁来保护跳表中的节点。这意味着一次只能有一个线程修改一个节点。然而，多个线程可以同时读取节点。

并发跳表是处理大量并发操作的应用程序的好选择。它也是需要能够执行快速查找操作的应用程序的好选择。

以下是使用并发跳表的一些好处

• 快速插入、删除和查找元素
• 在空间使用方面高效
• 可扩展以处理大量并发操作
• 适用于需要执行快速查找操作的应用程序

以下是使用并发跳表的一些局限性

可能比其他数据结构更复杂实现

• 对于某些操作，如范围查询，可能不如其他数据结构高效
• 对于某些应用程序，可能不如其他数据结构可扩展

此实现基于 William Pugh 1989 年论文中描述的 "Concurrent Maintenance of Skip Lists"。

示例

以下示例是从 Rust 标准库文档中的示例改编而来，针对 HashMap。

use yaambo::ConcurrentSkipList;

let mut movie_reviews: ConcurrentSkipList<String, String> = ConcurrentSkipList::new();

// Review some movies.
movie_reviews.set(
    "The Matrix".to_string(),
    "My favorite movie.".to_string(),
);
movie_reviews.set(
    "Liquorice Pizza".to_string(),
    "Not for me.".to_string(),
);
movie_reviews.set(
    "Moulin Rouge".to_string(),
    "A guilty pleasure.".to_string(),
);
movie_reviews.set(
    "The Power of the Dog".to_string(),
    "Underroted.".to_string(),
);

// Check for a specific one.
// When collections store owned values (String), they can still be
// queried using references (&str).
if !movie_reviews.contains("Les Misérables") {
    println!("We've got {} reviews, but Les Misérables ain't one.",
             movie_reviews.iter().count());
}

// oops, this review has a lot of spelling mistakes, let's delete it.
movie_reviews.remove("The Power of the Dog");

// Look up the values associated with some keys.
let to_find = ["Moulin Rouge", "Alice's Adventure in Wonderland"];
for &movie in &to_find {
    match movie_reviews.get(movie) {
        Some(review) => println!("{movie}: {review}"),
        None => println!("{movie} is un-reviewed.")
    }
}

// Iterate over everything.
for (movie, review) in &movie_reviews {
    println!("{movie}: \"{review}\"");
}

具有已知项目列表的 ConcurrentSkipList 可以从数组初始化

use yaambo::ConcurrentSkipList;

let solar_distance: ConcurrentSkipList<String, f32> = ConcurrentSkipList::from([
    ("Mercury", 0.4),
    ("Venus", 0.7),
    ("Earth", 1.0),
    ("Mars", 1.5),
]);

使用自定义键类型的 ConcurrentSkipList 的最简单方法是派生 [Ord]. 这需要键能够派生 PartialEq、Eq 以及 PartialOrd。

use yaambo::ConcurrentSkipList;

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct StreetFighter {
    name: String,
    country: String,
}

impl StreetFighter {
    Creates a new Street Fighter.
    fn new(name: &str, country: &str) -> StreetFighter {
        StreetFighter { name: name.to_string(), country: country.to_string() }
    }
}

// Use a ConcurrentSkipList to store the fighters' health points.
let fighters: ConcurrentSkipList<StreetFighter, usize> = ConcurrentSkipList::from([
    (StreetFighter::new("Akuma", "Japan"), 900_usize),
    (StreetFighter::new("Zangief", "Russia"), 1075_usize),
    (StreetFighter::new("Chun Li", "China"), 975_usize),
]);

// Use derived implementation to print the status of the fighters.
for (fighter, health) in &fighters {
    println!("{fighter:?} has {health} hp");
}

许可协议

此库使用 MIT 许可协议。如果您觉得它有帮助，我很乐意听到您的意见！