526互联

第12章. 映射(Map)

发布时间 2023-12-06 20:53:34作者: Ac_c0mpany丶

映射(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