【原】[高效數(shù)據(jù)結(jié)構(gòu)漫談]：HashMap與Vec的性能（1）

godxiasad 2024-11-26 發(fā)布于北京

展開全文

我都快忘記我還是碼農(nóng)了

遇上了一個問題，所以寫個文章記錄一下……

HashMap與Vec的性能

注意，因?yàn)檫@里主要用Rust來論述這個問題，如果對應(yīng)到Python，就是dict與list，效果是一樣的。

看到這個問題，可能很多同學(xué)都會說，這個還要你說？HashMap的是基于kv結(jié)構(gòu)的，查詢復(fù)雜度是O(1)，而Vec的查詢復(fù)雜度是O(n)，是個人都知道HashMap的復(fù)雜度高啊。

呵呵……圖樣圖森破，拿衣服……

看下面這個場景：

let size = 1000000;
    let mut rng = rand::thread_rng();
    let mut vec_info:Vec<(String,i32)> = Vec::with_capacity(size);
    let mut hashmap_info:HashMap<usize,(String,i32)> = HashMap::with_capacity(size);

    for i in 0..size{
        //生成一個abc.abcde這樣格式的模擬名字
        let name = format!("{}.{}",generate_random_string(rng.to_owned(),3),generate_random_string(rng.to_owned(),5));
        //生成一個隨機(jī)年齡
        let age = rng.gen_range(22..=60);
        vec_info.push((name.to_owned(), age));
        hashmap_info.insert(i, (name.to_owned(), age));
    }

我分別定義了一個hashmap和一個vec，默認(rèn)容量都是100萬

小貼士：在Rust、CPP一類編譯型語言中，預(yù)先對集合進(jìn)行內(nèi)存分配，可以有效的提高內(nèi)存使用率和程序效率。

然后定義了一個數(shù)據(jù)結(jié)構(gòu)，分別存儲了模擬的人員信息，例如一個姓名一個年齡，并且把這個數(shù)據(jù)存入到我們的hashmap和vec中，存進(jìn)去的信息類似下面這種：

vec:

vec里面直接按照數(shù)值序列進(jìn)行存儲，我們可以把序列號認(rèn)為的ID

[
    ("iYP.NHqtJ", 24),
    ("Tr1.YITPi", 34),
    ("cMx.gkNIA", 58),
    ……
]

hashmap:

hashmap里面用kv模式存儲，序列號（ID）就是他們的key

{
    0: ("iYP.NHqtJ", 24),
    1: ("Tr1.YITPi", 34),
    2: ("cMx.gkNIA", 58),
    ……
}

然后隨機(jī)讀取其中的1000個信息：

//隨機(jī)訪問vec中的1000個記錄
let start = Utc::now();
for i in 0..1000{
    let idx = rng.gen_range(0..size);
    println!("name= {} age = {}",vec_info[idx].0,vec_info[idx].1);
}
let end = Utc::now();
let vec_o = end.timestamp_subsec_micros()-start.timestamp_subsec_micros();

//隨機(jī)訪問hashmap中的1000個記錄
let start = Utc::now();
let start = Utc::now();
    for i in 0..1000{
        let idx = rng.gen_range(0..size);
        println!("{:?}",hashmap_info[&idx]);
    }
let end = Utc::now();