TreeMap or HashMap?

Question

When to use hashmaps or treemaps?

I know that I can use TreeMap to iterate over elements when I need to sort them. But is it? There is no optimization when I just want to consult maps or use some optimal specific applications?

Answer 1

Hashtables (usually) perform search operations (search), limited in complexity O(n)<=T(n)<=O(1) , with an average case complexity of O(1 + n/k) ; however, binary search trees (BST) perform search (search) operations limited in complexity O(n)<=T(n)<=O(log_2(n)) , with an average case complexity of O(log_2(n)) . The implementation for each (and each) data structure must be known (by you) in order to understand the advantages, disadvantages, complexity of the operation time, and code complexity.

For example, the number of entries in a hash table often has some fixed number of entries (some of which may not be populated at all) with collision lists. On the other hand, trees usually have two pointers (links) to a node, but it can be more if the implementation allows more than two child nodes on a node, and this allows the tree to grow as nodes are added, but may not allow duplicates. (By default, the Java TreeMap implementation does not allow duplicates)

There are also special cases, for example, what if the number of elements in a particular data structure increases unlimitedly or approaches the limit of the basic part of the data structure? What about amortized operations that perform some rebalancing or cleaning operation?

For example, in a hash table, when the number of elements in the table becomes large enough and an arbitrary number of collisions can occur. Trees, on the other hand, usually require a rebalancing procedure after insertion (or removal).

So, if you have something like a cache (for example, the number of restricted elements or the size is known), then a hash table is probably best; however, if you have something more like a dictionary (for example, once and many times searched many times), I would use a tree.

This is only in the general case, however (no information was given). You need to understand the process that happens the way they make the right choice when choosing a data structure.

When I need a multi-map (range search) or sorted anti-aliasing of a collection, then it cannot be a hash table.

Answer 2

TreeMap provides guaranteed O (log n) search time (and insert, etc.), while HashMap provides O (1) search time if the hash code appropriately distributes keys.

If you do not need entries for sorting, I stick with HashMap . Or there ConcurrentHashMap , of course. I don’t remember the details of the differences between them, but HashMap is a very reasonable default option :)

For completeness, I should note that about a month ago, "Stack Overflow" was discussed about the internal cards of various cards. See the comments in this question which I will copy in this answer if bestsss would be happy for me to do this.

Answer 3

The biggest difference between the two is the underlying structure used in the implementation.

HashMaps uses an array and a hash function to store items. When you try to insert or delete an element in an array, the hash function converts the key into an index in the array where the object should / should be stored (ignoring conflicts). Although hashmaps are usually very fast because they don’t need to sort through large amounts of data, they slow down when they are full because they need to copy all the keys / values ​​into a new array.

TreeMaps stores data in a sorted tree structure. Although this means that they will never have to allocate more space and copy to it, operations require that some of the already saved data be renamed. Sometimes a large amount of structure changes.

Of the two, hashmaps will usually work best when you don't need sorting.

Answer 4

Don't forget that there is also a LinkedHashMap , which is almost as fast as the HashMap for adding / containing / deleting operations, but also supports the insertion order.

Answer 5

Inserting new elements in HashMap will, on average, be much faster than inserting elements in TreeMap. If you don't need your items sorted, I would go with a HashMap.