I recently wrote this HashMap, so let’s talk a little bit about TreeMap, LinkedHashMap,ConcurrentHashMap

Essential knowledge

oneComparable , Comparator What’s the difference between these two?

You can see one for the java.lang package and one for the util package.

Comparable is an internal Comparator and Comparator is an external Comparator.

The advantage of external comparators is that we can have many of them, and we can select them according to sorting requirements, which is easy to decouple.

The internal comparator is relatively simple, as long as the Comparable interface is implemented.

class B implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        returno1-o2; }}class C implements Comparable<Integer>{
    private final int num;
    public C(int num){
        this.num=num;
    }
    @Override
    public int compareTo(Integer o) {
        return this.num-o; }}Copy the code

Then let’s take a look at TreeMap~ 😝

Characteristics of the TreeMap

1. An orderly

2. The key cannot be null

Resolution:

TreeMap implements the SrotedMap interface. The SortMap interface defines the Comparator external Comparator.

We can pass ~ when creating TreeMap. Otherwise, there is no external Comparator.

So here’s the question! Why can’t key be null?

See the following figure for analysis ~😋

When you first put the compare method, it will enter the compare method.

/** * Compares two keys using the correct comparison method for this TreeMap. */
@SuppressWarnings("unchecked")
final int compare(Object k1, Object k2) {
    return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
}
Copy the code

You can see that if you don’t define the external comparator, it will be converted to the internal comparatorComparableCompare.

As you can see, when you pass in a null key, k1 is null, calling compareTo will throw a NullPointerException. Null.com pareTo(k2).

** When you customize an external comparator, you’ll have to look at the way the compare method is written

If there is a non-null judgment, it will not throw a null pointer exception.

class B implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        if (o1==null||o2==null) {return -1;
        }
        returno1-o2; }}Copy the code

At number 3, you can see that the null pointer exception is thrown directly

So, the real answer should be

When you customize the external Comparator’s Comparator, you can allow the key to be null, but ~ is generally not recommended. 😝

** TreeMap uses the internal Comparator Comparable for the key when you do not have a custom external Comparator. The key is not allowed to be null ** 😝

Conclusion:

TreeMap is ordered. By default, TreeMap naturally sorts by key. In this case, keys cannot be null

While the iron is hot, let’s move on to another one that has to do with orderMap–LinkedHashMap

LinkedHashMap

If you look at its droplet diagram, you can see that it inherits HashMap.

It maintains a bidirectional linked list on top of the HashMap, and keeps inserts in order

This section will not expand, mainly rewrite the newNode method to maintain the double-linked list ~

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}
Copy the code

conclusion

LinkedHashMapThe features of a bidirectional linked list are inserted in order

And traversal is also a direct traversal of the bidirectional linked list, the insertion time complexity is O(1), the search time complexity is O(n)

End ~ scatter flowersU, °:.☆(~ ▽ ~)/$:Painted. ° 。

👉 write about this last ConcurrentHashMap in the next article, and then the lock part! !!!!!

Welcome attention, make a friend!! (•̀ ω •́)y

Java4ye is a programmer who sends technical articles on weekdays and chats about emotions and other non-technical topics on rest days. Nice to meet you!!

Java4ye provides you with a series of learning resources, plug-ins and software

Welcome to leave a message! Thanks for your support! O (≧ ヾ del ≦ *)