`

Map

 
阅读更多

Map 

表示键与值的一对一关系，键不允许重复。通过键可以快速找到值。

API:

方法摘要
 void clear()
          从此映射中移除所有映射关系（可选操作）。
 boolean containsKey(Object key)
          如果此映射包含指定键的映射关系，则返回 true。
 boolean containsValue(Object value)
          如果此映射将一个或多个键映射到指定值，则返回 true。
 Set<Map.Entry<K,V>> entrySet()
          返回此映射中包含的映射关系的 Set 视图。
 boolean equals(Object o)
          比较指定的对象与此映射是否相等。
 V get(Object key)
          返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回 null。
 int hashCode()
          返回此映射的哈希码值。
 boolean isEmpty()
          如果此映射未包含键-值映射关系，则返回 true。
 Set<K> keySet()
          返回此映射中包含的键的 Set 视图。
 V

put(K key, V value)
          将指定的值与此映射中的指定键关联（可选操作）。

如果此映射以前包含一个该键的映射关系，则用指定值替换旧值
 void putAll(Map<? extends K,? extends V> m)
          从指定映射中将所有映射关系复制到此映射中（可选操作）。
 V remove(Object key)
          如果存在一个键的映射关系，则将其从此映射中移除（可选操作）。
 int size()
          返回此映射中的键-值映射关系数。
 Collection<V> values()
          返回此映射中包含的值的 Collection 视图。

 

Map 的子类：

  

  


 

HashMap ：非线程安全的,允许key或value 为null,不支持排序。key相等的判断条件：hashcode和equals 都相等。

LinkedHashMap:在 HashMap 的基础上提供了按插入顺序排序的功能。

TreeMap: 非线程安全的, 允许key或value 为null,支持自然排序或指定 的Comparator进行排序。key相等的判断条件：key.compareTo(map里面的key)==0 或Comparator.compare(key, map里面的) ==0

EnumMap:转为key为枚举类准备的MAP,key只能属于同一个枚举类。非线程安全的,不允许key为null,但允许value为null。 key相等的判断条件：key.ordinal() ==  map里面的 key.ordinal() 

IdentityHashMap:非线程安全的,key相等的判断条件： 通过==(直等)来判断

 

ConcurrentHashMap：线程安全，不允许key或value为null,不支持排序,key相等的判断条件：hashcode和equals 都相等。

ConcurrentSkipListMap:线程安全,不允许key或value为null,支持 排序,key相等的判断条件：key.compareTo(map里面的key)==0 或Comparator.compare(key, map里面的) ==0

 

 Map的选择：

单线程下：

        仅需要记录两个对象的映射关系就用HashMap,

         需要按put时顺序遍历就用LinkedHashMap,

         需要进行key的大小排序就用TreeMap

         key中要放一个枚举类型的所有实例，就用EnumMap.

         只能用key对象（逻辑上相等不行），才能取出value对象,则用IdentityHashMap。

 多线程下：

         仅需要记录两个对象的映射关系就用ConcurrentHashMap,

         还需要进行key的大小排序就用 ConcurrentSkipListMap

         也可以使用Collections.synchronizedMap(Map<K,V> map)对任何一个非线程安全的Map进行包装而达到线程安全的目的，但迭代时必须同步迭代器，多线程频繁该问时，性能没有优势。

{

    HashMap:记录两个对象之间的映射关系，不在乎遍历时的随机顺序问题，以key对象的逻辑上(数据值)相等来查找value对象时使用,key对象需要实现hashCode和equals 。

   LinkedHashMap: 记录两个对象之间的映射关系，按put时先后顺序遍历，以key对象的逻辑上(数据值)相等来查找value对象时使用,key对象需要实现hashCode和equals 。

    TreeMap：记录两个对象之间的映射关系，按key的从小到大顺序遍历，以key对象compareTo(treeMap里的key)==0 来查找value对象时使用，key对象需要 Comparable接口。

     EnumMap：记录一个枚举类的所有实例与其它对象的对应、按枚举实例的声明顺序遍历 时使用。

     IdentityHashMap：记录两个对象之间的映射关系，只有与key对象是同一个实例，才能取出对应的value对象。

}

 

 

   

 

 

 

HashMap :

 构建器： HashMap(int initialCapacity, float loadFactor) 

          构造一个带指定初始容量和加载因子的空 HashMap。

          默认的 initialCapacity 为16，默认的 loadFactor 为0.7。

         当HashMap中添加的元素数（HashMap.size()）>=  initialCapacity * loadFactor时， HashMap自动扩大容量，大约为原容量的2倍。如果较多数据存入HashMap,未设定  initialCapacity ，则HashMap 可能会多次扩充容量，多消耗性能。

      key为自定义的类，需要实现equqls 和 hashCode 方法。

内部数据结构：

    1.数组：  Entry[] table = new Entry[capacity]

     2. 链表：Entry 对象是个链表，通过next属性指向下一个  Entry :

            Entry<K,V> {

              final K key;

              V value;

             Entry<K,V> next;//下一个元素

            final int hash;//key的hashCode值

          }   

 

   put(key,value)时 ,根据key的hashCode 计算出table的数组下标i，如果table[i]已存在，则对table[i]即  Entry链表进行比较 ，如果 entry.hash == key.hash &&  entry.key.equals(key) 即key的hashCode和equals都相等，则认为key相同，则将value存入entry.value,即替换旧value.

     Entry链表中没有相同的key,则新生成Entry加入链表。

     Entry链表存在的原因：多个hashCode计算出的table的数组下标相同。

 

 

 LinkedHashMap :

   在HashMap的基础上，记录了元素的添加顺序，keySet(),entrySet() 返回的Iterator 按添加顺序排序：

   

 private static class Entry<K,V> extends HashMap.Entry<K,V> {
        // These fields comprise the doubly linked list used for iteration.
        Entry<K,V> before, after;
       private void remove() {
            before.after = after;
            after.before = before;
        }

        /**
         * Inserts this entry before the specified existing entry in the list.
         */
        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }
}

 

 

void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMap.Entry<K,V> old = table[bucketIndex];
	Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
        table[bucketIndex] = e;
        e.addBefore(header);//记录顺序
        size++;
    }

 

TreeMap:

  TreeMap 提供对插入的元素排序的功能 

  keySet().iterator 或 entrySet().iterator 排key类由小到大顺序排列。

  

 key 需要实现Comparable接口 或者提供Comparator类完成对KEY的自定义排序。

 key 不需要实现equals 和 hashcode方法，get(key) 和containsKey(key) 方法是根据 key.compareTo(treeMap里的key)==0 或 Comparator.compare(key,treeMap里的key)==0 来判断的。

 

 

构建器：

 

TreeMap()
          使用键的自然顺序构造一个新的、空的树映射。
TreeMap(Comparator<? super K> comparator)
          构造一个新的、空的树映射，该映射根据给定比较器进行排序。
TreeMap(Map<? extends K,? extends V> m)
          构造一个与给定映射具有相同映射关系的新的树映射，该映射根据其键的自然顺序 进行排序。
TreeMap(SortedMap<K,? extends V> m)
          构造一个与指定有序映射具有相同映射关系和相同排序顺序的新的树映射。

 

内部数据结构：

  红黑树(一种二叉树)：树的最左侧存的是最小key的Entry,最右侧存的是最大key的Entry.

      

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

 

  put 代码：

 

public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {
	    // TBD:
	    // 5045147: (coll) Adding null to an empty TreeSet should
	    // throw NullPointerException
	    //
	    // compare(key, key); // type check
            root = new Entry<K,V>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                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<K,V>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }
 

 

    TreeMap提供的方法API：

 

 Map.Entry<K,V> ceilingEntry(K key)
          返回一个键-值映射关系，它与大于等于给定键的最小键关联；如果不存在这样的键，则返回 null。
 K ceilingKey(K key)
          返回大于等于给定键的最小键；如果不存在这样的键，则返回 null。
 NavigableSet<K> descendingKeySet()
          返回此映射中所包含键的逆序 NavigableSet 视图。
 NavigableMap<K,V> descendingMap()
          返回此映射中所包含映射关系的逆序视图。
 Map.Entry<K,V> firstEntry()
          返回一个与此映射中的最小键关联的键-值映射关系；如果映射为空，则返回 null。
 Map.Entry<K,V> floorEntry(K key)
          返回一个键-值映射关系，它与小于等于给定键的最大键关联；如果不存在这样的键，则返回 null。
 K floorKey(K key)
          返回小于等于给定键的最大键；如果不存在这样的键，则返回 null。
 SortedMap<K,V> headMap(K toKey)
          返回此映射的部分视图，其键值严格小于 toKey。
 NavigableMap<K,V> headMap(K toKey, boolean inclusive)
          返回此映射的部分视图，其键小于（或等于，如果 inclusive 为 true）toKey。
 Map.Entry<K,V> higherEntry(K key)
          返回一个键-值映射关系，它与严格大于给定键的最小键关联；如果不存在这样的键，则返回 null。
 K higherKey(K key)
          返回严格大于给定键的最小键；如果不存在这样的键，则返回 null。
 Map.Entry<K,V> lastEntry()
          返回与此映射中的最大键关联的键-值映射关系；如果映射为空，则返回 null。
 Map.Entry<K,V> lowerEntry(K key)
          返回一个键-值映射关系，它与严格小于给定键的最大键关联；如果不存在这样的键，则返回 null。
 K lowerKey(K key)
          返回严格小于给定键的最大键；如果不存在这样的键，则返回 null。
 NavigableSet<K> navigableKeySet()
          返回此映射中所包含键的 NavigableSet 视图。
 Map.Entry<K,V> pollFirstEntry()
          移除并返回与此映射中的最小键关联的键-值映射关系；如果映射为空，则返回 null。
 Map.Entry<K,V> pollLastEntry()
          移除并返回与此映射中的最大键关联的键-值映射关系；如果映射为空，则返回 null。
 NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
          返回此映射的部分视图，其键的范围从 fromKey 到 toKey。
 SortedMap<K,V> subMap(K fromKey, K toKey)
          返回此映射的部分视图，其键值的范围从 fromKey（包括）到 toKey（不包括）。
 SortedMap<K,V> tailMap(K fromKey)
          返回此映射的部分视图，其键大于等于 fromKey。
 NavigableMap<K,V> tailMap(K fromKey, boolean inclusive)
          返回此映射的部分视图，其键大于（或等于，如果 inclusive 为 true）fromKey。

 

Comparator<? super K> comparator()
          返回对此映射中的键进行排序的比较器；如果此映射使用键的自然顺序，则返回 null。
 Set<Map.Entry<K,V>> entrySet()
          返回在此映射中包含的映射关系的 Set 视图。
 K firstKey()
          返回此映射中当前第一个（最低）键。
 SortedMap<K,V> headMap(K toKey)
          返回此映射的部分视图，其键值严格小于 toKey。
 Set<K> keySet()
          返回在此映射中所包含键的 Set 视图。
 K lastKey()
          返回映射中当前最后一个（最高）键。
 SortedMap<K,V> subMap(K fromKey, K toKey)
          返回此映射的部分视图，其键值的范围从 fromKey（包括）到 toKey（不包括）。
 SortedMap<K,V> tailMap(K fromKey)
          返回此映射的部分视图，其键大于等于 fromKey。
 Collection<V> values()
          返回在此映射中所包含值的 Collection 视图。

 EnumMap:

  以枚举类型为KEY的Map. 专为枚举类型使用。 Map中KEY只能源于同一个枚举类。

构建器：

 EnumMap(Class<K> keyType)

          创建一个具有指定键类型的空枚举映射。  keyType为枚举类Class对象。

 

内部数据结构：

   K[] keyUniverse :保存key的数组。由于枚举类实例数固定的，在由构建器初始化时，能够获得枚举类实例个数从而定义数组大小。

   Object[] vals:key对应的 value.

 

key 如何对应到数组中：

int index = ((Enum)key).ordinal();  

ordinal() 方法返回该枚举实例在枚举类中的声明顺序序号。第一个实例枚举序号为0，以此类推。 

 

 

 IdentityHashMap：

key是否相同判断： 通过==(直等)来判断

内部使用数据结构：

  Object[] table ，数组下标为偶数存key对象, 下标+1存该key对应的value.

 

key 如何对应的数组下标上：

 通过key的默认hashCode()方法的获得 hashCode ，根据hashCode再计算出数组下标：

 

  private static int hash(Object key, int length) {
        int h = System.identityHashCode(key);
        // Multiply by -127, and left-shift to use least bit as part of hash
        return ((h << 1) - (h << 8)) & (length - 1);
    }

 

不同key对应数组同一下标，如何存储：

 后put的key ，计算出的下标+2,判断是否为null,不存null则存保存在该位置 ，否则下标继续下移二位。 

 

 put 方法：

 

  public V put(K key, V value) {
        Object k = maskNull(key);
        Object[] tab = table;
        int len = tab.length;
        int i = hash(k, len);//根据key 计算出数组下标

        Object item;
        while ( (item = tab[i]) != null) {
            if (item == k) {//相同的key 则覆盖value
		V oldValue = (V) tab[i + 1];
                tab[i + 1] = value;
                return oldValue;
            }
            i = nextKeyIndex(i, len);//数组下标下移两位
        }

        modCount++;
        tab[i] = k;//不为空则存上
        tab[i + 1] = value;
        if (++size >= threshold)
            resize(len); // len == 2 * current capacity.
        return null;
    }

  

 ConcurrentHashMap：
 支持并发的HashMap。 保证线程安全。
 
 key相等的判断条件：hashCode 和 equals 都相等。(e.hash != hash || !key.equals(e.key))
 
 V

putIfAbsent(K key, V value)
          如果指定键已经不再与某个值相关联，则将它与给定值关联。

      相当于原子的执行下面的代码：

      if (!map.containsKey(key)) 

      return map.put(key, value);
  else
       return map.get(key);
 
  
 boolean

remove(Object key, Object value)
          只有目前将键的条目映射到给定值时，才移除该键的条目。

相当于原子的执行：

  if (map.containsKey(key) && map.get(key).equals(value)) {
       map.remove(key);
       return true;
   } else return false;
 V

replace(K key, V value)
          只有目前将键的条目映射到某一值时，才替换该键的条目。

相当于原子的执行：

 if (map.containsKey(key)) {
       return map.put(key, value);
   } else return null;
 boolean

replace(K key, V oldValue, V newValue)
          只有目前将键的条目映射到给定值时，才替换该键的条目。

相当于原子的执行：

  if (map.containsKey(key) && map.get(key).equals(oldValue)) {
       map.put(key, newValue);
       return true;
   } else return false;

 

ConcurrentSkipListMap:

 

  与TreeMap 类似，但支持并发操作。线程安全的。

 

 

 

  • 大小: 96.5 KB
分享到：
| 类的定义
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    java循环Map java迭代Map

    Map a = new HashMap(); //方法一 Iterator it = a.entrySet().iterator(); while (it.hasNext()) { Map.Entry pairs = (Map.Entry) it.next(); System.out.println(pairs.getValue()); } //以下方法需要jdk5以上...

    map.zip_电机_电机MAP_电机效率_电机效率map_绘制电机MAP

    电机MAP（Map，通常指的是性能图或特性曲线）是展示电机效率、功率和其他关键性能参数随转速和转矩变化关系的图表。这种图表对于电机设计、优化和控制系统的研究具有重要意义。 电机效率MAP的绘制涉及到多个步骤和...

    Map (c++实现的简易map)

    在C++编程中，`Map`是一种非常重要的数据结构，它允许我们以键值对的形式存储数据，其中每个键（key）都是唯一的，并且通过这个键可以快速访问对应的值（value）。`Map`通常用于存储关联数组，它提供了一种灵活的...

    GameMap_地图_gamemap_gamemap官网_分割地图_gamemap下_

    《GameMap：游戏地图设计与分割技术详解》 在游戏开发中，地图是构建游戏世界不可或缺的元素。本文将深入探讨GameMap，一种专用于游戏地图设计和管理的工具，以及其中涉及到的关键技术和概念。 首先，我们要理解...

    map_电机_效率map_

    电机效率Map是电机性能分析中的一个重要概念，它用于描述电机在不同工况下运行的效率分布情况。在本文中，我们将深入探讨电机效率Map的绘制方法、意义以及如何利用工具进行计算。 电机效率是指电机输出的机械功率与...

    C语言头文件 MAP C语言头文件 MAP

    C语言头文件 MAPC语言头文件 MAPC语言头文件 MAPC语言头文件 MAPC语言头文件 MAPC语言头文件 MAPC语言头文件 MAPC语言头文件 MAPC语言头文件 MAPC语言头文件 MAPC语言头文件 MAPC语言头文件 MAPC语言头文件 MAPC语言...

    map.toString()后转换成Map类型

    ### Map.toString()后转换成Map类型的实现方法及解析 在Java编程中，有时我们需要将一个`Map`对象转换为字符串形式进行存储或传输，而在接收端又需要将该字符串重新转换回`Map`对象以便进一步处理。本篇将详细介绍...

    Scala的Map相关方法整合

    ### Scala的Map相关方法整合 在Scala编程语言中，`Map`是一种常用的数据结构，用于存储键值对。本文将详细介绍Scala中Map的各种方法及其用途，帮助开发者更好地理解和使用这些功能。 #### 1. `def++(xs:Map[(A,B)]...

    rammap自动运行程序

    **RAMMap工具详解** RAMMap是一款强大的内存分析工具，由微软的 Sysinternals 团队开发，主要用于分析和理解操作系统的内存使用情况。这个工具能够帮助用户深入洞察系统内存的分配和使用，包括物理内存、分页文件...

    map_map_增删查改_STL_C++_

    本节我们将深入探讨STL中的`map`容器，了解其基本概念，并通过实际代码示例展示如何进行增、删、查、改等操作。 `map`容器是一种关联容器，它将唯一的键值与关联的值进行存储，这里的键值通常是用来查找对应值的。`...

    MapBrowser1.2.rar_MapBrows_MapBrowser1.03_mapbrowser 1.2_梦幻_梦幻西游

    《MapBrowser 1.2：梦幻西游的资源探索利器》 MapBrowser 1.2 是一款专为梦幻西游玩家设计的资源提取工具，它以其高效、易用的特性深受用户喜爱。作为一款强大的游戏辅助软件，MapBrowser 1.2 能够帮助玩家深入挖掘...

    详解Python map函数及Python map()函数的用法

    Python的`map()`函数是一个非常实用的内置高阶函数，它的主要作用是对一个或多个序列（通常是列表）的每个元素应用指定的函数，并返回一个新的列表，包含应用函数后的结果。这个函数非常适合在函数式编程中使用，...

    m_map用法详解.rar_M map_m_map_m_map sst_matlab世界地图_世界地图 MATLAB

    《m_map在MATLAB中的应用详解》 MATLAB作为一个强大的数值计算和数据分析工具，其丰富的工具箱使得在各个领域都有广泛的应用。其中，m_map工具箱是专为地图绘制和地理数据分析而设计的，它提供了丰富的函数和数据，...

    C++11 unordered_map与map（插入,遍历，Find）效率对比。

    在C++编程中，`std::map`和`std::unordered_map`是两种常见的关联容器，它们都用于存储键值对，但实现机制和性能特点有所不同。本篇文章将深入探讨这两种容器在插入、遍历和查找操作上的差异，并通过实例分析它们...

    ResultSet 转为listmap

    ResultSet 转为 List&lt;Map&gt; ResultSet 转为 List&lt;Map&gt; 是一种常见的数据处理操作。在 Java 中，使用 JDBC 连接数据库时，通常会返回一个 ResultSet 对象，该对象包含了查询结果集的所有记录。为了方便数据处理和使用...

    c++中map的基本用法和嵌套用法实例分析

    C++中的`map`是一个关联容器，它存储键值对，其中每个键都是唯一的。`map`的数据结构通常实现为红黑树，提供了O(log n)的时间复杂度进行插入、查找和删除操作。下面我们将详细探讨`map`的基本用法和嵌套用法。 ### ...

    素材_tilemap素材_使用TileMap快速构造2D关卡_

    TileMap（瓷砖地图）是一种高效且灵活的工具，常用于构建2D游戏的环境和场景。本素材包主要围绕如何使用TileMap来快速构造2D关卡，帮助开发者节省时间和精力，专注于游戏玩法的创新。 1. TileMap简介： TileMap是2...

    java一键xml转map，一键map转xml工具类

    在Java编程中，XML（可扩展标记语言）和Map（映射）是两种常见的数据存储和交换格式。XML因其结构化和易于解析的特性，在数据交换和配置文件中广泛使用，而Map则作为Java中存储键值对的高效数据结构。在实际开发中，...

    map工具，分析linux生產的map文件

    在Linux系统中，map文件是一种重要的调试和性能分析工具，它包含了程序在内存中的映射信息。本篇文章将深入探讨map工具以及如何分析由Linux生产出的map文件，旨在帮助IT专业人士更好地理解和优化他们的系统。 首先...

    java Pojo转Map

    将Pojo对象转换为Map，可以简化数据处理过程，尤其是在JSP页面上展示数据时，Map的灵活性更加突出。本文将详细介绍如何实现Java中的Pojo到Map的转换，并通过具体的示例来演示这一过程。 首先，我们需要一个Pojo类，...

Magicbox
Global site tag (gtag.js) - Google Analytics