Java Map 01 - Map

  在Java语言规范中,Map作为Java集合框架中的一员,提供了对同类型数据进行存储、插入、删除和查找等需求的实现过程。其实现机制和特点使得Map是一个无序的(部分实现可以保证顺序),不可存储相同key的数据结构。本文演示代码段的执行环境基于JDK版本1.7

概述

  Map是Java集合框架体系中的成员之一,和Collection相互独立且两者地位平等。Map本身只是一个接口定义,其定义了对Map进行操作的方法API,且所有的map实现类都会实现Map接口定义的方法。

  Map是一个保存键值对映射的数据结构,map不允许维护重复的key,且每个key最多只能映射一个value。Map接口完全取代了抽象类Dictionary类。Map提供了三种浏览集合内数据的方式:键集合、值集合和键值对集合。像TreeMap这样的实现类可以保证元素遍历的顺序,而像HashMap这样的实现类则无法保证元素遍历的顺序,也就是说其是一个无序结构。需要注意的是,Map的key如果存储的是可变的对象,那么由于equals()方法的影响无法保证根据可变对象可以正确的存储和获取Map集合中的元素。除此之外,也不允许map集合以其自身作为key存储到map集合中(equals()和hashCode()方法无法保证)。

  通用的map实现需要提供两种标准的构造器:一个是无参构造器,用来构建一个空map集合。另一个是只含有一个以map作为参数的构造器,这个构造方法允许用户实现map复制。

  有些实现类对维护的key和value值会有一些限制。例如,有的实现禁止null类型的key和value值,有的实现则限制了key的类型。尝试加入key-value映射会抛出NullPointerException或者ClassCastException异常。尝试查找违反规则的key或者value会抛出异常或者直接返回false。

  Map接口的常见实现有AbstractMapHashMapConcurrentHashMapLinkedHashMapHashtable、TreeMap,而TreeMap则实现了NavigableMap和SortedMap声明的一系列方法。其结构如图1所示:

图 - 1

关于上述几个具体实现类之间,分别有其适应的应用场景和特点:

  • HashMap
    1. HashMap是一个key不可重复的集合结构;
    2. 遍历HashMap时,从底层数组首部依次向后遍历;
    3. 底层实现依赖于数组,查找元素可以保证常量时间的性能,插入和删除需要的时间和集合存储的键值对数量成比例;
    4. HashMap需要考虑扩容情况,扩容规则是按照当前容量的两倍进行扩容;
    5. HashMap不是一个线程安全的集合实现;
    6. HashMap可以允许key、value为null,如果key为null,那么该键值对会存储在内部数组的第一个下标位置上;
    7. 加入到HashMap的元素只需要保证hashcode()和equals()方法被实现即可(默认实现或者自定义实现)。不需要实现Comparable或者Comparator接口;
  • LinkedHashMap
    1. LinkedHashMap是一个有序的,key不可重复的集合结构。其顺序默认为元素插入顺序,但是也具有访问顺序的特性(最近被访问的元素位于集合的尾部位置,即LRU);
    2. 底层依赖于链表,查找元素时需要逐个遍历,时间开销和链表长度成比例,元素插入和移除可以保证常量时间内完成;
    3. LinkedHashMap同样存在扩容过程;
    4. LinkedHashMap同样也不是一个线程安全的集合实现;
    5. LinkedHashMap允许key、value为null;
    6. 加入到LinkedHashMap的元素只需要保证hashcode()和equals()方法被实现即可(默认实现或者自定义实现)。不需要实现Comparable或者Comparator接口;
  • Hashtable
    1. Hashtable是一个key不可重复的集合;
    2. 遍历Hashtable时,从底层数组尾部依次向前遍历;
    3. 底层实现依赖于数组,具体实现和HashMap类似;
    4. Hashtable需要考虑扩容情况,扩容规则是按照当前容量的两倍与1的和进行扩容;
    5. Hashtable是HashMap的线程安全版本;
    6. Hashtable的key和value均不允许为null;
    7. 加入到Hashtable的元素只需要保证hashcode()和equals()方法被实现即可(默认实现或者自定义实现)。不需要实现Comparable或者Comparator接口;
  • TreeMap
    1. TreeMap是一个key不可重复的集合;
    2. 遍历TreeMap的元素时,要么按照自然排序进行遍历(集合内元素实现的Comparable接口),要么按照特定的规则进行遍历(集合内元素实现的Comparator接口);
    3. 底层实现依赖于红黑树结构,查找、插入和删除性能都可以达到O($ \lg n $);
    4. TreeMap不需要考虑扩容。但是在元素插入后需要重新调整树结构以保持红黑树的性质;
    5. TreeMap也不是一个线程安全的集合实现;
    6. TreeMap不允许key为null,但是value可以为null;
    7. 加入到TreeMap的元素需要实现Comparable或者Comparator接口,否则元素无法正常加入到集合中;
  • ConcurrentHashMap
    1. ConcurrentHashMap是一个key不可重复的集合;
    2. 遍历ConcurrentHashMap时,从底层数组尾部依次向前遍历;
    3. 底层实现依赖于数组,数组元素是Segment实例,每个Segment实例内部又维护了一个HashEntry数组。类似于书本分页设计,一个Segment实例类似于一本书的一页,而Segment实例内部的HashEntry数组类似于每页中的每一行;
    4. ConcurrentHashMap需要考虑扩容,在扩容时针对的是某个具体的segment实例内部的HashEntry数组进行扩容;
    5. ConcurrentHashMap是HashMap的另一个线程安全的实现版本;
    6. ConcurrentHashMap可以允许多个线程同时对集合内的不同元素进行锁定和处理,如果是对同一个键值对实体或者同一个Segment实例内部的键值对实体进行处理,那么依旧存在锁抢占,即同一时刻只有线程可以访问一个键值对实体或者一个特定的segment内部的HashEntry数组;
    7. 加入到ConcurrentHashMap的元素只需要保证hashcode()和equals()方法被实现即可(默认实现或者自定义实现)。不需要实现Comparable或者Comparator接口;

部分方法

方法声明 备注
Map.Entry<K,V> lowerEntry(K key) 返回严格小于key的最大key的键值对映射
K lowerKey(K key) 返回严格小于key的最大key
Map.Entry<K,V> floorEntry(K key) 返回小于等于key的最大key的键值对映射
K floorKey(K key) 返回小于等于key的最大key
Map.Entry<K,V> ceilingEntry(K key) 返回大于等于key的最小key的键值对映射
K ceilingKey(K key) 返回大于等于key的最小key
Map.Entry<K,V> higherEntry(K key) 返回严格大于key的最小key的键值对映射
K higherKey(K key) 返回严格大于key的最小key
Map.Entry<K,V> firstEntry() 返回当前map集合中key最小的键值对映射
Map.Entry<K,V> lastEntry() 返回当前map集合中key最大的键值对映射
Map.Entry<K,V> pollFirstEntry() 取出并返回当前map集合中key最小的键值对映射
Map.Entry<K,V> pollLastEntry() 取出并返回当前map集合中key最大的键值对映射
NavigableMap<K,V> descendingMap() 返回当前map集合的一个逆序集合
NavigableMap<K,V> navigableKeySet() 返回当前map集合的key值集合
NavigableMap<K,V> descendingKeySet() 返回当前map集合的key值一个逆序集合
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) 返回当前map集合中自fromKey到toKey的子集合,由fromInclusive和toInclusive指定是否包含fronKey和toKey
NavigableMap<K,V> headMap(K toKey, boolean inclusive) 返回小于等于toKey的集合,由inclusive指定是否等于toKey
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) 返回大于等于fromKey的集合,由inclusive指定是否等于fromKey
SortedMap<K,V> subMap(K fromKey, K toKey) 返回当前map集合中自fromKey(包含)到toKey(不包含)的子集合。
SortedMap<K,V> headMap(K toKey) 返回小于toKey的集合
SortedMap<K,V> tailMap(K fromKey) 返回大于fromKey的集合

涉及基础知识点

  1. NIL

参考文献

  1. RUNOOB.COM. Java 集合框架 [E]
  2. J Steven Perry. 第 10 单元:Java 集合 [E]
  3. ORACLE. Collections Framework Overview [E]




------------- End of this article, thanks! -------------


  版权声明:本文由Nathan R. Lee创作和发表,采用署名(BY)-非商业性使用(NC)-相同方式共享(SA)国际许可协议进行许可,转载请注明作者及出处。
  本文作者为 Nathan R. Lee
  本文标题为 Java Map 01 - Map
  本文链接为 https://marcuseddie.github.io/2018/java-Collection-Map.html