5 ms·

What's your thought on TreeMap (ordered by key)? What problems can be best solved by TreeMap? Why do people use HashMap instead of TreeMap?

• shepik 5y ago
  Simple answer: Use tree if you need range access or to get elements ordered by key, and use hash otherwise. More nuance: - hashmap may be resized if it's over capacity, the resize may cause a latency spike. - hashmap is essentially a single random memory access, tree is a couple of accesses but they are not random - tree is a bit like a sorted array with fast inserts/deletes. Some trees, like leveldb, are in fact sorted arrays (plus some tricks, of course) - if you use b-tree, you are more memory-efficient (but less cpu efficient), and access to nearby elements is almost free. That's why b-trees are used to store data in a permanent memory - there are many other tree variants, each of them with different trade-off
• guiand 5y ago
  Hash tables are (usually) faster to do all sorts of operations than tree based maps, as most operations become a simple function to calculate a tree’s hash followed by a table lookup. Of course, they’re unordered, so if you need to iterate in order, or find all keys < a certain value, or things like that, tree maps can be better for your algorithm. Also, TreeMap uses a red-black tree to implement the map, which is a basic type of binary tree. Depending on the data you’d like to store, other kinds of tree-based maps can have better performance characteristics. A map based on a Splay Tree[1] speeds up repeated accesses, so it could perform well if you had keys that were cheap to compute an ordering but expensive to compute a hash, and your access pattern has good temporal locality. [1] https://en.wikipedia.org/wiki/Splay_tree https://en.wikipedia.org/wiki/Splay_tree