#[derive(Clone)]
pub struct RandomState {
    k0: u64,
    k1: u64,
}
// hashmap 的实现不再library std中
use hashbrown::hash_map as base;
pub struct HashMap<K, V, S = RandomState> {
    base: base::HashMap<K, V, S>,
}


pub struct HashMap<K, V, S = DefaultHashBuilder, A: Allocator + Clone = Global> {
    pub(crate) hash_builder: S,
    pub(crate) table: RawTable<(K, V), A>,
}

pub struct RawTable<T, A: Allocator + Clone = Global> {
    table: RawTableInner<A>,
    // Tell dropck that we own instances of T.
    marker: PhantomData<T>,
}
struct RawTableInner<A> {
    bucket_mask: usize,
    ctrl: NonNull<u8>,
    growth_left: usize,
    items: usize,
    alloc: A,
}

    #[test]
    fn test_hashmap() {
        use std::collections::HashMap;
        let mut map = HashMap::new();
        println!("len={}, cap={}", map.len(), map.capacity());
        map.insert('a', 1);
        println!("len={}, cap={}", map.len(), map.capacity());
        // get(&T) -> Option<&T>
        assert_eq!(map.get(&'a'), Some(&1));
    }

// alloc::collections::btree::map.rs
pub struct BTreeMap { 
    root: Option>, 
    length: usize,
}
pub type Root<K, V> = NodeRef<marker::Owned, K, V, marker::LeafOrInternal>;
pub struct NodeRef { height: usize, node: NonNull>, _marker: PhantomData<(BorrowType, Type)>,}