# Should I use HashMap or RBTree? **URL:** \ **Category:** Motoko\ **Created:** [May 10, 2023, 7:14am UTC](https://forum.dfinity.org/t/should-i-use-hashmap-or-rbtree/19866 "2023-05-10T07:14:58Z")\ **Posts on this page:** 9\ **Page:** 1
**Author:** ![tokuryoo](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/tokuryoo/32/3369_2.png) [@tokuryoo](https://forum.dfinity.org/u/tokuryoo)\ **Post date:** [May 10, 2023, 7:14am UTC](https://forum.dfinity.org/t/should-i-use-hashmap-or-rbtree/19866/1 "2023-05-10T07:14:58Z")
Hi everyone, The Motoko language provides HashMap and RBTree. Is there a best practice on which one to use? I am just studying. I am not familiar with algorithms. [docs - HashMap](https://internetcomputer.org/docs/current/motoko/main/base/HashMap) > Runtime: O(1) > Space: O(1) [docs - RBTree](https://internetcomputer.org/docs/current/motoko/main/base/RBTree) > Runtime: O(log(n)) worst case cost per insertion, removal, and retrieval operation. > Space: O(n) for storing the entire tree. n denotes the number of key-value entries (i.e. nodes) stored in the tree. ---
**Author:** ![skilesare](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/skilesare/32/5609_2.png) [@skilesare](https://forum.dfinity.org/u/skilesare)\ **Post date:** [May 10, 2023, 3:43pm UTC](https://forum.dfinity.org/t/should-i-use-hashmap-or-rbtree/19866/2 "2023-05-10T15:43:10Z")
Probably this one: [GitHub - ZhenyaUsenko/motoko-hash-map: Stable hash maps for Motoko](https://github.com/ZhenyaUsenko/motoko-hash-map) ---
**Author:** ![chenyan](https://avatars.discourse-cdn.com/v4/letter/c/35a633/32.png) [@chenyan](https://forum.dfinity.org/u/chenyan)\ **Post date:** [May 10, 2023, 4:34pm UTC](https://forum.dfinity.org/t/should-i-use-hashmap-or-rbtree/19866/3 "2023-05-10T16:34:41Z")
In terms of performance, we have some benchmark numbers for different map structures: [Collection libraries | canister-profiling](https://dfinity.github.io/canister-profiling/collections/#map) ---
**Author:** ![icme](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/icme/32/4327_2.png) [@icme](https://forum.dfinity.org/u/icme)\ **Post date:** [May 10, 2023, 8:45pm UTC](https://forum.dfinity.org/t/should-i-use-hashmap-or-rbtree/19866/4 "2023-05-10T20:45:00Z")
HashMap: - provides most efficient O(1) insert, lookup, & deletion - space taken is O(n) - Depending on implementation every so often the hashtable underneath the map needs to double, which can result in an O(n) operation. RBTree/BTree: - provides O(log(n)) insert, lookup, & deletion. - space taken is O(n) - Sorts the data by key within the tree. This allows for operations like [scanning](https://canscale.github.io/StableHeapBTreeMap/BTree.html#scanLimit) between two bounds, which is powerful if one wants to paginate through entries in the data structure that depend on a sorted ordering. ---
**Author:** ![skilesare](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/skilesare/32/5609_2.png) [@skilesare](https://forum.dfinity.org/u/skilesare)\ **Post date:** [May 10, 2023, 10:34pm UTC](https://forum.dfinity.org/t/should-i-use-hashmap-or-rbtree/19866/5 "2023-05-10T22:34:52Z")
Byron is being a bit modest here…he also wrote [GitHub - canscale/StableHeapBTreeMap: A functional BTreeMap that can be used with a stable variable in heap memory](https://github.com/canscale/StableHeapBTreeMap) which I think is a pretty solid improvement on the BTree that maintains sort order. Byron…you need to pimp your ride. 🙂 @chenyan…what is the mechanism that makes the rust maps so much more performant? ---
**Author:** ![chenyan](https://avatars.discourse-cdn.com/v4/letter/c/35a633/32.png) [@chenyan](https://forum.dfinity.org/u/chenyan)\ **Post date:** [May 11, 2023, 12:57am UTC](https://forum.dfinity.org/t/should-i-use-hashmap-or-rbtree/19866/6 "2023-05-11T00:57:18Z")
Rust’s hash map uses the standard Swiss Table. Zhenya’s hash map uses V8’s hash map, which is better suited for storing large objects. Data structure-wise, there shouldn’t be much difference for normal use cases. The performance diff really comes from being written in different languages. Rust is much more low level than Motoko, so it can generate code that is much more efficient. ---
**Author:** ![skilesare](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/skilesare/32/5609_2.png) [@skilesare](https://forum.dfinity.org/u/skilesare)\ **Post date:** [May 11, 2023, 2:52am UTC](https://forum.dfinity.org/t/should-i-use-hashmap-or-rbtree/19866/7 "2023-05-11T02:52:51Z")
Would you expect that Motoko would get more performant? Is there a particular mechanism that makes it not as efficient? Would adding a map at a lower level as a ‘native’ structure bring more performance in motoko? ---
**Author:** ![chenyan](https://avatars.discourse-cdn.com/v4/letter/c/35a633/32.png) [@chenyan](https://forum.dfinity.org/u/chenyan)\ **Post date:** [May 11, 2023, 4:31am UTC](https://forum.dfinity.org/t/should-i-use-hashmap-or-rbtree/19866/8 "2023-05-11T04:31:14Z")
It’s always getting more performant. For example, see the perf improvements from 0.8.4 to 0.8.5: [bump to moc 0.8.5 by chenyan-dfinity · Pull Request #43 · dfinity/canister-profiling · GitHub](https://github.com/dfinity/canister-profiling/pull/43). Being a high level language means there is a performance overhead in exchange for a native and convenient experience. You cannot expect Python to be as efficient as C. But there are still many Python developers. FFI can be an option to bridge the perf gap, but it’s a long way to support FFI. ---
**Author:** ![tokuryoo](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/tokuryoo/32/3369_2.png) [@tokuryoo](https://forum.dfinity.org/u/tokuryoo)\ **Post date:** [May 11, 2023, 8:29am UTC](https://forum.dfinity.org/t/should-i-use-hashmap-or-rbtree/19866/9 "2023-05-11T08:29:26Z")
@skilesare @chenyan @icme Thanks for your reply! a. [Collection libraries | canister-profiling](https://dfinity.github.io/canister-profiling/collections/#map) The value of generate 50k in hashmap is 2\_387\_017\_574. Is the unit of measure Cycle? b. [Collection libraries | canister-profiling](https://dfinity.github.io/canister-profiling/collections/#map) > We have a limit on the maximal cycles per round. I understood that the less Cylce consumed by Map, the more processing can be done per round. Am I correct in understanding that faster Map processing does not mean faster response time? c. [docs - HashMap](https://internetcomputer.org/docs/current/motoko/main/base/HashMap) > Runtime: O(1) > Space: O(1) Maybe O(1) is wrong and O(n) is correct. I do not know. d. I had never heard of StableHeapBTreeMap before. Thanks. e. If I want to handle Huge data in a Map, I thought Rust should be adopted. For general systems that are not Internet Computer, efficiency is related to processing speed and response time, and inefficient efficiency can be solved by replacing CPUs or adding servers, so there is no problem with a slow language. However, I thought that efficiency is important when processing on an Internet Computer and on a single subnet.