哈希运算什么规模比直接便利快？

林深好材发表于 2024-11-06 15:32

对N条数据进行索引，如果N<10, 请问使用哪种结构会更快些？


pub struct Key(String, usize);

pub struct Keys1(Vec<Key>);

pub struct Keys2(HashMap<String, usize>)

pub trait Indexer {
   fn get_index(&self, key_name: &String) -> usize;
}

impl Indexer for Keys1 {
   fn get_index(&self, key_name: &String) -> usize{
     todo!()
   }
}

impl Indexer for Keys2 {
   fn get_index(&self, key_name: &String) -> usize{
     todo!()
   }
}

评论区

写评论

SleepyBoy 2024-11-08 16:11

我按你写的简单实现了一下


impl Indexer for Keys1 {
    fn get_index(&self, key_name: &String) -> usize {
        self.0.iter().find(|v| v.0 == *key_name).map_or(0, |e| e.1)
    }
}

impl Indexer for Keys2 {
    fn get_index(&self, key_name: &String) -> usize {
        self.0.get(key_name).map_or(0, |e| *e)
    }
}

写了个简单的bench测试，变量是一个input = Vec数据，对input构造Key1和Key2，再用bench测试对input遍历查询性能。通过改变input可以对比二者差距。

我直接在工作电脑windows上cargo bench的，实测是input.len() <= 11的时候，Key1优于Key2。在长度11的时候，差距只有不到5%，在长度12的时候，Key2开始优于Key1，差距也在5%左右，之后就是Key2碾压领先了。专门试了在len = 1的时候，Key1:Key2≈1:4.5。

实测的在十几个字符长度范围内改变input内String的长度，对上面的结论几乎不产生决定性影响，原因有下面解释。

最后查看标准库的String的Eq和Hash实现，二者都是对字符串O(n)的时间复杂度,区别只在于常数项和系数：Eq是比较底层[u8]，Hash也是会对每一位u8做相关运算；而在自己实现的get_index中，遍历的时间复杂度是O(n^2)，hash是O(n)。

综上所述，低规模下String::eq会比String:hash较快，这里我当时测得的临界规模大小是在11~12之间，仅供参考

GUO 2024-11-08 09:13

取决key的哈希计算速度与compare速度哪个快？快多少？

如果一样快，肯定选 HashMap 更快一些

wangbyby 2024-11-08 00:18

还有，如果key类型很复杂，hashmap更好一点。

wangbyby 2024-11-07 23:50

如果N比较小，直接遍历很快，如果用smallvec这种，控制好元素个数连分配内存都免了。

作者林深好材 2024-11-07 09:08

随机的，一条数据就是一KV对。

--
👇
Bai-Jinlin: N条数据的特征是什么，是否连续，还是纯随机的？

作者林深好材 2024-11-07 09:08

大抵是想了解，在entry较少的情况下，HashMap 的效率与直接数组便利谁更快。

--
👇
gcalgoz: 你是想讨论cpu缓存的问题

Bai-Jinlin 2024-11-06 18:29

N条数据的特征是什么，是否连续，还是纯随机的？

gcalgoz 2024-11-06 18:03

你是想讨论cpu缓存的问题

1 共 8 条评论, 1 页