4个版本
0.1.4 | 2020年12月6日 |
---|---|
0.1.3 | 2020年12月6日 |
0.1.2 | 2020年8月28日 |
0.1.0 | 2020年8月25日 |
#1528 in 数据结构
18KB
352 行
序列树集合
一种用于快速读取和存储序列数据的集合
(作为哈希表的替代方案)
简介
序列树是一种新的集合类型,它允许使用序列(如字符串)作为键来存储数据,并在与键的长度和树中已存在的相似键的数量相关的时间段内检索与该键对应的值
这个集合旨在提供对哈希表的替代方案,哈希表依赖于哈希函数将序列转换为数组中的位置。
哈希表
哈希表的优势在于检索或存储键所需的时间通常取决于哈希该键所需的时间,这在大多数情况下是相当快的,但它们有一个缺点,因为哈希函数有冲突,这意味着传递给哈希函数的两个不同值可以生成相同的哈希。为了解决这个问题,已经开发并实施了许多解决方案,但它们都需要一些计算上昂贵的操作。此外,当哈希表存储越来越多的值时,哈希表后端的数组需要调整大小,这可以是一项昂贵的操作。
序列树
现在出现了序列树!序列树将给定的键分解成节点,每个节点包含序列的一个元素(在字符串的情况下是一个字符),并且每个节点与其相邻的节点(如链表)相连,最后一个值持有分配给键的实际值。现在要检索键的值,只需按照键的顺序在树中跟随每个节点,就可以轻松地找到值,无需哈希函数!这种方法的优点是键由于集合的性质而自然地压缩,但使树快速的原因在于找到正确的下一个节点的方式,因为一个节点(字符)可以链接到多个其他字符(多达你的字符编码的数量)。因为字符由数字支持,所以我能够简单地存储每个节点的下一个节点在二叉搜索树中,但也可以使用哈希表(这在内存使用上可能很昂贵,因为它们预留空间),甚至只是一个普通的数组(但这会相当慢)。
序列树比哈希表慢,因为它们需要通过找到每个节点可能持有的许多后续节点中的正确下一个节点来按顺序跟踪序列中的每个元素。因此,键的相似性也为速度提供了提升。
当前状态
树以通用方式实现,但对于这种实现,用于键的类型必须具有以下特性:PartialOrd + PartialEq + Copy + Default
,因为二叉树用于查找下一个节点。目前支持键的删除,但未经过彻底测试,因此请自行承担风险,并在发现任何问题后通知我。
未来的计划主要是性能测试和文档编写。
如何使用
let mut st: SequenceTree<char, u64> = SequenceTree::new(); // initialize tree
let key: Vec<char> = String::from("hello").chars().collect(); // create key
st.set(key.to_owned(), 55); // set key
println!("{:?}", st.get(key) ); //get value of key
待办事项
- 从树中删除键和值
实现- 进行更彻底的测试
进行通用实现- 扩展README以包括
- 图片说明,
- 效率计算
- 性能图表,以与当前解决方案进行比较
- 代码注释