How to decide whether to use HashMap or TreeMap?

Posted May 27, 20203 min read

Introduction

The key value of TreeMap <K, V> is required to implement java.lang.Comparable, so when iterating, TreeMap is sorted by key value in ascending order by default; TreeMap implementation is based on red-black tree structure. Suitable for traversing keys in natural order or custom order.

The key value of HashMap <K, V> implements hashing hashCode(), the distribution is hashed and uniform, and sorting is not supported; the data structure is mainly buckets(arrays), linked lists or red-black trees. It is suitable for inserting, deleting and locating elements in Map.

in conclusion

If you need to get an ordered result, you should use TreeMap(because the order of elements in HashMap is not fixed). In addition, since HashMap has better performance, we will use HashMap when most sorting is not needed.

Expand

1. Implementation of HashMap and TreeMap

HashMap: Based on a hash table. The key classes added by using HashMap clearly define hashCode() and equals() \ [can rewrite hashCode() and equals() ]. In order to optimize the use of HashMap space, you can adjust Optimal initial capacity and load factor.

  • HashMap():construct an empty hash map
  • HashMap(Map m):build a hash image, and add all the maps of image m
  • HashMap(int initialCapacity):construct an empty hash image with a specific capacity
  • HashMap(int initialCapacity, float loadFactor):construct an empty hash image with a specific capacity and load factor

TreeMap: Based on the red-black tree. TreeMap has no adjustment options because the tree is always in a balanced state.

  • TreeMap():build an empty image tree
  • TreeMap(Map m):build an image tree, and add all elements in image m
  • TreeMap(Comparator c):build an image tree, and use a specific comparator to sort the keywords
  • TreeMap(SortedMap s):build an image tree, add all the maps in the image tree s, and use the same sorter as the ordered image s

2, HashMap and TreeMap are both non-thread safe

HashMap inherits AbstractMap abstract class, TreeMap inherits from SortedMap interface.

AbstractMap abstract class: Overrides equals() and hashCode() methods to ensure that two equal maps return the same hash code. If two maps are equal in size, contain the same key, and each key corresponds to the same value in both maps, then the two maps are equal. The mapped hash code is the sum of the hash codes of the mapped elements, where each element is an implementation of the Map.Entry interface. Therefore, regardless of the internal order of the mappings, two equal mappings will report the same hash code.

SortedMap interface: It is used to maintain the order of keys. The SortedMap interface provides access methods for the view(subset) of the image, including two endpoints. Except that sorting is applied to the keys of the map, processing SortedMap is the same as processing SortedSet. Elements added to the SortedMap implementation class must implement the Comparable interface, otherwise you must provide an implementation of the Comparator interface to its constructor. The TreeMap class is its only implementation.

3. TreeMap is sorted in ascending order by default, how to make him descend

Through a custom comparator

Define a comparator class, implement the Comparator interface, rewrite the compare method, there are two parameters, these two parameters are compared by calling compareTo, and the default rule of compareTo is:

  • If the parameter string is equal to this string, then return a value of 0;
  • If this string is less than the string parameter, it returns a value less than 0;
  • If this string is greater than the string parameter, it returns a value greater than 0.

When customizing the comparator, a negative sign is added when returning, and the comparison result is returned in the opposite form. The code is as follows:

static class MyComparatorimplementsComparator {
 @Override
 public int compare(Object o1, Object o2) {
 //TODO Auto-generated method stub
 String param1 =(String) o1;
 String param2 =(String) o2;
 return -param1.compareTo(param2);
 }
}

After that, initialize a comparator instance through the MyComparator class and pass it as a parameter into the construction method of TreeMap:

MyComparatorcomparator = new MyComparator();
Map <String, String \> map = new TreeMap <String, String \>(comparator);

In this way, we can use a custom comparator to achieve descending order

public class MapTest {
 public static void main(String \ [\]args) {
 //Initialize custom comparator
 MyComparatorcomparator = new MyComparator();
 //Initialize a map collection
 Map <String, String \> map = new TreeMap <String, String \>(comparator);
 //Save data
 map.put("a", "a");
 map.put("b", "b");
 map.put("f", "f");
 map.put("d", "d");
 map.put("c", "c");
 map.put("g", "g");
 //Traverse output
 Iterator iterator = map.keySet(). Iterator();
 while(iterator.hasNext()) {
     String key =(String) iterator.next();
     System.out.println(map.get(key));
     }
 }
 static class MyComparatorimplementsComparator {
 @Override
 public int compare(Object o1, Object o2) {
     //TODO Auto-generated method stub
     String param1 =(String) o1;
     String param2 =(String) o2;
     return -param1.compareTo(param2);
     }
  }
}