从put()分析HashMap

发表于 | 分类于 | 阅读次数

1、它是有序的集合

实现了 SotredMap 接口：

1
2
3
4
5
public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable{//...}
  
public interface NavigableMap<K,V> extends SortedMap<K,V> {//...}

2、在调用 TreeMap 的构造函数时：

1）若指定了 Comparator 比较器，按照比较器来进行 key 的排序。

1
2
3
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

2）若未指定 Comparator 比较器，则按照 key 进行自然排序，key 必须实现 Comparable 接口。

1
public TreeMap() { comparator = null; }

3）或者传入有排序的 Map，SortedMap

1
2
3
4
5
6
7
8
9
10
11
12
public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);//m中的键必须实现 Comparable 接口
}
public TreeMap(SortedMap<K, ? extends V> m) {
    comparator = m.comparator();
    try {
        buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    } catch (java.io.IOException cannotHappen) {
    } catch (ClassNotFoundException cannotHappen) {
    }
}

3、红黑树 Entry<K,V> root

每个 key-value 都作为一个红黑树的节点。

1
2
3
4
5
6
7
8
9
10
11
12
// 红黑树的根节点
private transient Entry<K,V> root;

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;
    //...
}

4、put方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public V put(K key, V value) {
    Entry<K,V> t = root;     //红黑树的根节点
    if (t == null) {        //红黑树是否为空
        compare(key, key); // type (and possibly null) check
        root = new Entry<>(key, value, null);  
        size = 1;
        modCount++;
        return null;    //返回null 
    }
    int cmp;
    Entry<K,V> parent;    
    // split comparator and comparable paths
    // 如果定义了比较器，采用自定义比较器进行比较
    Comparator<? super K> cpr = comparator;     
    if (cpr != null) {      
        do {
            parent = t; 
          // 比较key与根节点的大小，小于放左边，大于放右边，如果它们相等，替换key的值
            cmp = cpr.compare(key, t.key);    
            if (cmp < 0)      
                t = t.left;   
            else if (cmp > 0)
                t = t.right;  
            else
                return t.setValue(value);      
        } while (t != null);        //循环遍历
    }
    else {
    // 自然排序方式，没有指定比较器
        if (key == null)
            throw new NullPointerException();  // 抛出异常
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)     
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    Entry<K,V> e = new Entry<>(key, value, parent);   // 创建新节点
    // 根据比较结果，决定新节点为父节点的左孩子或者右孩子
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e);   // 新插入节点后重新调整红黑树 
    size++;
    modCount++;
    return null;// 返回null
}

5、TreeMap 的键值可以为null吗

1）键不建议为null，key为null 可能抛空指针

2）值可以为null。

  • 未指定 Comparator 时，按key自然排序，key为null时 会抛出 NullPointerException
1
2
3
4
5
6
    public static void main(String[] args) {
        TreeMap<String, Object> treeMap = new TreeMap<>();
//      treeMap.put(null,"m"); // throw new NullPointerException();
        treeMap.put("str1", null);
        System.out.println(treeMap.get("str1"));
    }

  • 若指定 Comparator，若实现的比较器未对 null 键进行判断，可能抛出 NullPointerException；

    若实现的比较器有对 null 键进行判断，可以存入，也能get。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static void main(String[] args) {
    User user1 = new User(1, 18);        
    TreeMap<User, Object> userTreeMap = new TreeMap<>(new UserComparator());// 传入比较器
    userTreeMap.put(null, "b");
    System.out.println(userTreeMap.get(null)); // 输出 b

    userTreeMap.put(user1, null);
    System.out.println(userTreeMap.get(user1));  // 输出 null
    System.out.println(userTreeMap.get(null)); // 此时不再输出b，而是null，因为存入时 user1 与 键null 比较时结果为0，value直接覆盖
}

// 自定义比较器
public static class UserComparator implements Comparator<User> {
    @Override
    public int compare(User o1, User o2) {
        // 这里有对 null 进行判断。如果其一为null，返回0
        // 但这样会导致一个问题，只要null与其他键比较，都会返回0，在TreeMap中就会发生值覆盖。
        if (o1 == null || o2 == null) { 
            return 0;
        }
        return o1.getId() > o2.getId();
    }
}

6、TreeMap 中的 put方法 需要注意什么，尤其是key？

  • 1）如果没有指定比较器，则键的类必须要实现Comparable接口。

  • 2）最好不要传入null键，要么抛错，要么容易引起问题。

  • 3）在定义比较方法，Comparator接口的compare方法和Comparable接口的compareTo方法时，要注意返回结果为 0 则表示在TreeMap的树上为同一节点，即表示相同节点，此时应考虑是否重写equals、hashCode方法。

  • 4）比较结果为0，会直接进行setValue值替换。

  • 5）put方法返回什么：如果map中已经有 key 的映射，返回旧值oldValue；如果没有 key 的映射，则返回null。

7、 TreeMap 的查找和新增时间复杂度

如果树节点数为 n，树的高度为 log (n)。

TreeMap 的查找和新增时间复杂度为 O (log (n))。

8、与LinkedHashMap有序的区别：

LinkedHashMap 使用一个额外双向链表，记录插入顺序，所以它是根据插入顺序排序。

9、TreeSet

TreeSet 是一种可有序存放元素的集合，HashSet 是 value 为固定值的 HashMap，TreeSet 是 value 为固定值的TreeMap。

1
2
3
4
5
6
7
8
9
10
// TreeSet 是 Value为固定值的 TreeMap
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }

    private transient NavigableMap<E,Object> m;
    private static final Object PRESENT = new Object();
    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }