第12章. 映射(Map)

映射(Map)

• Map在有些变成语言中也叫作字典(比如在Python中)

• Map的每一个Key是唯一的，Value可以不是唯一的

• Map中的每一个Key对应一个Value

一、Map的接口设计

public interface Map<K, V> {
    int size;
    boolean isEmpty();
    void clear();
    V put(K key, V value);
    V get(K key);
    boolean containsKey(K key);
    boolean containsValue(V value);
    void traversal(Visitor<K, V> visitor);
    
    public static abstract class Visitor<K, V> {
        boolean stop;
        public abstract boolean visit(K key, V value);
    }
}

类似Set，Map可以直接利用之前学习的链表、二叉搜素树(AVL树、红黑树)等数据结构来实现。

二、直接由红黑树(RBTree)实现TreeMap

红黑树节点上存放的是K和V，即一个节点上既有key又有value。

• 通过RBTree实现的TreeMap
• 时间复杂度(平均)
  • 添加、删除、搜素：O(logn)
• 特点：
  • Key必须具备可比较性
  • 元素的分布是有顺序的
• 在实际应用中，很多时候的需求
• Map中存储的元素不需要讲究顺序
• Map中的Key不需要具备可比较性
• 不考虑顺序、不考虑Key的可比较性，Map有更好的实现方案，平均时间复杂度可以达到O(1)
• 那就是采取哈希表来实现Map

三、哈希表实现HashMap

HashMap底层通过哈希表来实现

四、LinkedHashMap

在HashMap的基础上维护元素的添加顺序，使得遍历的结果遵从添加顺序。(不要求从小到大，只是要求遍历按照元素添加的顺序)。

五、总结

1. 对遍历没有要求，是无序遍历的，就使用HashMap(底层是哈希表+红黑树，默认是根据桶的顺序遍历的)
2. 要求key遍历顺序是从小到大的，就使用TreeMap(底层是红黑树)
3. 要求遍历顺序是按照添加顺序的，就使用LinkedHashMap