O(n) time complexity for most operations

[gwy15]

Describe the bug
The LruCache is implemented with a BTreeMap and a VecDeque, which means that by accessing keys and calling the
update_key method, it will invoke a VecDeque::remove operation, which will cost O(n) time.

Expected behavior
Should be O(1).

Additional context
Some other libs that do the complexity right:

• lru-cache & linked-hash-map: used a linked hash map, O(1).
• hashlink: used a linked hash map, O(1).

sample

#![feature(test)]

extern crate test;
use test::Bencher;

use std::cell::RefCell;
use std::collections::HashMap;
use lru_cache::LruCache as LruCacheLruCache;
use lru_time_cache::LruCache;
use hashlink::LruCache as HashLinkLruCache;
use rand::prelude::*;

fn main() { }

const RANGE: usize = 32 * 1024;
const FIND_TIMES: usize = 10;

#[bench]
fn lru_time_cache_sum(b: &mut Bencher) {
    let mut lru = LruCache::with_capacity(RANGE);
    for i in 0..RANGE {
        lru.insert(i, i);
    }
    let lru = RefCell::new(lru);
    b.iter(|| {
        let res: usize = (0..FIND_TIMES)
            .map(|_| *lru
                .borrow_mut()
                .get(&thread_rng().gen_range(0, RANGE))
                .unwrap_or(&0))
            .sum();
        test::black_box(res);
    });
}

#[bench]
fn lru_cache_sum(b: &mut Bencher) {
    let mut lru = LruCacheLruCache::new(RANGE);
    for i in 0..RANGE {
        lru.insert(i, i);
    }
    let lru = RefCell::new(lru);
    b.iter(|| {
        let res: usize = (0..FIND_TIMES)
            .map(|_| *lru
                .borrow_mut()
                .get_mut(&thread_rng().gen_range(0, RANGE))
                .unwrap_or(&mut 0))
            .sum();
        test::black_box(res);
    });
}

#[bench]
fn hashlink_lru_cache_sum(b: &mut Bencher) {
    let mut lru = HashLinkLruCache::new(RANGE);
    for i in 0..RANGE {
        lru.insert(i, i);
    }
    let lru = RefCell::new(lru);
    b.iter(|| {
        let res: usize = (0..FIND_TIMES)
            .map(|_| *lru
                .borrow_mut()
                .get(&thread_rng().gen_range(0, RANGE))
                .unwrap_or(&0))
            .sum();
        test::black_box(res);
    });
}

#[bench]
fn hashmap_sum(b: &mut Bencher) {
    let mut map = HashMap::new();
    for i in 0..RANGE {
        map.insert(i, i);
    }
    b.iter(|| {
        let res: usize = (0..FIND_TIMES)
            .map(|_| *map
                .get(&thread_rng().gen_range(0, RANGE))
                .unwrap_or(&0))
            .sum();
        test::black_box(res);
    });
}