Map从入门到性能优化

我会带着你远行 2022-12-19 13:10 162阅读 0赞

### 文章目录 ###

*  一、Map简介
 *  二、Map的常用方法
 *  三、HashMap
 *   *  3.1 基本用法
     *  3.2 基本原理（Entry基本介绍）
     *  3.3 构造方法（map初始化及扩容）
     *   *  3.3.1 无参构造方法
         *  3.3.2 单参数构造方法
         *  3.3.3 双参数构造方法
     *  3.4 几种遍历
     *   *  3.4.1 ketSet
         *  3.4.2 values
         *  3.4.3 entrySet
         *  3.4.4 iterator
         *  3.4.5 性能分析
         *   *  3.4.5.1 key
             *  3.4.5.2 value
     *  3.5 常用方法
 *  四、LinkedHashMap
 *  五、TreeMap
 *  六、总结

# 一、Map简介 #

Map是一组“键值对”对象，在我们平时的开发和面试中，都是使用频率特别高的知识点之一。我在这里简单分析一下Map的家族，并且重点介绍我们最经常使用的HashMap。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMjQ3NDM1_size_16_color_FFFFFF_t_70_pic_center]  
基本概念：  
  **capacity**：map的容量，默认16；长度不够存储时会根据加载因子自动进行扩容。  
  **load factor**：加载因子，默认0.75；当map中存储的长度大于capacity\*load factor时扩容。

# 二、Map的常用方法 #

========常用方法======
    //获取map的大小
    int size();
    //判断map是否为空
    boolean isEmpty();
    //判断map是否包含某个key
    boolean containsKey(Object key);
    //判断map是否包含某个value
    boolean containsValue(Object value);
    //根据map里的key获取对应的value
    V get(Object key);
    //向map里新增一个值
    V put(K key, V value);
    //根据key移除对应的值
    V remove(Object key);
    //key和value都相等是才会移除某个值
    boolean remove(Object key, Object value)
    //将另一个map的值添加到当前map上
    void putAll(Map<? extends K, ? extends V> m);
    //清空map里所有的key、value
    void clear();
    //获取map的所有key的set集合
    Set<K> keySet();
    //获取map的所有的value
    Collection<V> values();
    //返回所有的Entry集合（key不相同即可）
    Set<Map.Entry<K, V>> entrySet();
    ========下面方法不常用，了解即可========
    boolean equals(Object o);
    int hashCode();
    V getOrDefault(Object key, V defaultValue)
    forEach(BiConsumer<? super K, ? super V> action)
    void replaceAll(BiFunction<? super K, ? super V, ? extends V> function)
    V putIfAbsent(K key, V value)
    boolean replace(K key, V oldValue, V newValue)
    V replace(K key, V value)
    V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)
    V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)
    V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)
    Entry<K, V>下的方法
    K getKey();
    V getValue();
    V setValue(V value);
    boolean equals(Object o);
    int hashCode();
    comparingByKey()
    comparingByValue()
    comparingByKey(Comparator<? super K> cmp)

# 三、HashMap #

## 3.1 基本用法 ##

简单演示：

public class map { 
        public static void main(String[] args) { 
            Map<String,String> map = new HashMap<>();
            map.put("a","a1");
            map.put("c","c1");
            map.put("d","d1");
            map.put("b","b1");
            map.put("e","b1");
    
            Set<Map.Entry<String, String>> entries = map.entrySet(); for (Map.Entry<String, String> entry : entries) { 
                System.out.println(entry.getKey() + ":" + entry.getValue());
            }
        }
    }

运行结果：

a:a1
    b:b1
    c:c1
    d:d1
    e:b1

知识点：

map的输出是按照一定的顺序的，但是不是put的顺序，具体的顺序需要在 **3.2基本原理** 中找到。

## 3.2 基本原理（Entry基本介绍） ##

map底层是以Entry对象的方式存放的。下面贴一下HashMap底层存储对应源码。

注：Entry是接口，Node是实现该接口的类。

> 由下面源码可以分析：  
>   
> 1、Node含有三个变量和一个引用  
>   
> 2、这里的key和value就是对应我们map里存放的key和value。  
>   
> 3、next可以指向下一个Node节点。  
>   
> 4、hash存放的是优化之后的hash值。

/** * Basic hash bin node, used for most entries. (See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) */
    static class Node<K,V> implements Map.Entry<K,V> { 
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    
        Node(int hash, K key, V value, Node<K,V> next) { 
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    
        public final K getKey()        {  return key; }
        public final V getValue()      {  return value; }
        public final String toString() {  return key + "=" + value; }
    
        public final int hashCode() { 
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
    
        public final V setValue(V newValue) { 
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
    
        public final boolean equals(Object o) { 
            if (o == this)
                return true;
            if (o instanceof Map.Entry) { 
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

## 3.3 构造方法（map初始化及扩容） ##

### 3.3.1 无参构造方法 ###

/** * Constructs an empty <tt>HashMap</tt> with the default initial capacity * (16) and the default load factor (0.75). */
    public HashMap() { 
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

由源码分析，无参构造方法执行时会默认初始化长度为16，加载因子为0.75；

### 3.3.2 单参数构造方法 ###

/** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and the default load factor (0.75). * * @param initialCapacity the initial capacity. * @throws IllegalArgumentException if the initial capacity is negative. */
    public HashMap(int initialCapacity) { 
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

由源码分析，单参数构造方法中指定的是capacity初始长度。这里面调用的是双参构造函数，具体的我们在下一节讨论。

### 3.3.3 双参数构造方法 ###

/** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */
        public HashMap(int initialCapacity, float loadFactor) { 
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
            this.loadFactor = loadFactor;
            this.threshold = tableSizeFor(initialCapacity);
        }

/** * Returns a power of two size for the given target capacity. */
    static final int tableSizeFor(int cap) { 
       int n = cap - 1;
       n |= n >>> 1;
       n |= n >>> 2;
       n |= n >>> 4;
       n |= n >>> 8;
       n |= n >>> 16;
       return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

由源码分析，双参数构造方法可自定义初始容量和加载因子。

> 这里我们又能再详细分析一下这里的条件：  
>   
> 1、MAXIMUM\_CAPACITY是map的最大容量，数值为1 << 30 = 1073741824  
>   
> 2、初始容量不能小于0  
>   
> 3、初始容量大于MAXIMUM\_CAPACITY时，取MAXIMUM\_CAPACITY的值为初始容量。  
>   
> 4、加载因子不能小于等于0，不能为非数字类型。  
>   
> 5、初始化容量并不一定是传入的值，而是大于initialCapacity的最接近的2的幂次方。

## 3.4 几种遍历 ##

### 3.4.1 ketSet ###

通过ketSet可以求出map中所有的key，然后再通过key可以求出对应的value。

for (String key:map.keySet()) { 
       String value = map.get(key);
    }

### 3.4.2 values ###

values方法的结果本身就是value集合。

for (String value:map.values()) { }

### 3.4.3 entrySet ###

entrySet求出的是上面介绍过的entry对象的集合。

for (Map.Entry<String,String> entry:map.entrySet()) { 
        entry.getKey();
        entry.getValue();
    }

### 3.4.4 iterator ###

iterator是通过entrySet进行迭代器遍历。

Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
    while (iterator.hasNext()) { 
        Map.Entry<String, String> next = iterator.next();
        next.getKey();
        next.getValue();
    }

### 3.4.5 性能分析 ###

既然上面写了四种遍历方法，那性能对比究竟如何呢？

为了测试能尽可能的真实，下面我取用500w条数据，通过分别运行十次取平均值且多次实验的方式，尽可能的消除由于cpu资源分配带来的的影响。

#### 3.4.5.1 key ####

如果我们的目的是尽可能快的求key。

values只能求value，不能求key，不需要参加，直接出局。

实验代码：

package com.java.example.demo.map;
    
    import java.util.HashMap;
    import java.util.Iterator;
    import java.util.Map;
    
    public class HashMapKeyDemo { 
    
        public static void main(String[] args) { 
            Map<String,String> map = new HashMap<>();
            for (int i = 0; i < 5000000; i++) { 
                map.put("k" + i,"v" + i);
            }
    
            long keySet = 0;
            long entrySet = 0;
            long iterator = 0;
    
            HashMapKeyDemo demo = new HashMapKeyDemo();
            for (int i = 0; i < 10; i++) { 
                keySet += demo.keySet(map);
                entrySet += demo.entrySet(map);
                iterator += demo.iterator(map);
            }
    
            System.out.println("keySet耗时：" + keySet/10 + "ms");
            System.out.println("entrySet耗时：" + entrySet/10 + "ms");
            System.out.println("iterator耗时：" + iterator/10 + "ms");
        }
    
        private long keySet(Map<String,String> map){ 
            long startTime = System.currentTimeMillis();
            for (String key:map.keySet()) { 
            }
            long endTime = System.currentTimeMillis();
            return endTime - startTime;
        }
    
        private long entrySet(Map<String,String> map){ 
            long startTime = System.currentTimeMillis();
            for (Map.Entry<String,String> entry:map.entrySet()) { 
                entry.getKey();
            }
            long endTime = System.currentTimeMillis();
            return endTime - startTime;
        }
    
        private long iterator(Map<String,String> map){ 
            long startTime = System.currentTimeMillis();
            Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
            while (iterator.hasNext()) { 
                Map.Entry<String, String> next = iterator.next();
                next.getKey();
            }
            long endTime = System.currentTimeMillis();
            return endTime - startTime;
        }
    
    }

实验结果：  
![在这里插入图片描述][20201107220734176.png_pic_center]  
  通过上面的结果，我们发现仅求key的情况下，三种方式耗时是差不多的。为了防止数据量过小导致的数据不准确，我们以1000w的数据再测一次。  
![在这里插入图片描述][20201107221253617.png_pic_center]  
  再次运行的结果也是及其相近的，只是keySet稍多一点。

#### 3.4.5.2 value ####

如果我们的目的是尽可能快的求value。  
  实验代码：

package com.java.example.demo.map;
    
    import java.util.HashMap;
    import java.util.Iterator;
    import java.util.Map;
    
    public class HashMapDemo { 
    
        public static void main(String[] args) { 
            Map<String,String> map = new HashMap<>();
            for (int i = 0; i < 5000000; i++) { 
                map.put("k" + i,"v" + i);
            }
    
            long keySet = 0;
            long values = 0;
            long entrySet = 0;
            long iterator = 0;
    
            HashMapDemo demo = new HashMapDemo();
            for (int i = 0; i < 10; i++) { 
                keySet += demo.keySet(map);
                values += demo.values(map);
                entrySet += demo.entrySet(map);
                iterator += demo.iterator(map);
            }
    
            System.out.println("keySet耗时：" + keySet/10 + "ms");
            System.out.println("values耗时：" + values/10 + "ms");
            System.out.println("entrySet耗时：" + entrySet/10 + "ms");
            System.out.println("iterator耗时：" + iterator/10 + "ms");
        }
    
        private long keySet(Map<String,String> map){ 
            long startTime = System.currentTimeMillis();
            for (String key:map.keySet()) { 
                map.get(key);
            }
            long endTime = System.currentTimeMillis();
            return endTime - startTime;
        }
    
        private long values(Map<String,String> map){ 
            long startTime = System.currentTimeMillis();
            for (String value:map.values()) { 
    
            }
            long endTime = System.currentTimeMillis();
            return endTime - startTime;
        }
    
        private long entrySet(Map<String,String> map){ 
            long startTime = System.currentTimeMillis();
            for (Map.Entry<String,String> entry:map.entrySet()) { 
                entry.getValue();
            }
            long endTime = System.currentTimeMillis();
            return endTime - startTime;
        }
    
        private long iterator(Map<String,String> map){ 
            long startTime = System.currentTimeMillis();
            Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
            while (iterator.hasNext()) { 
                Map.Entry<String, String> next = iterator.next();
                next.getValue();
            }
            long endTime = System.currentTimeMillis();
            return endTime - startTime;
        }
    
    }

实验结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMjQ3NDM1_size_16_color_FFFFFF_t_70_pic_center 1]

通过几次对比可以看出，通过keySet求value的耗时是远远超过其他三种的，其他三种的耗时很接近，我们还是改用1000w的数据再测一次。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMjQ3NDM1_size_16_color_FFFFFF_t_70_pic_center 2]  
  这次比较跟上次很相似，均是keySet一骑绝尘。通过对比还是更推荐entrySet和iterator。

## 3.5 常用方法 ##

# 四、LinkedHashMap #

# 五、TreeMap #

# 六、总结 #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMjQ3NDM1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/07ce5433aff84952b556adcafb0a1cc0.png
[20201107220734176.png_pic_center]: https://img-blog.csdnimg.cn/20201107220734176.png#pic_center
[20201107221253617.png_pic_center]: https://img-blog.csdnimg.cn/20201107221253617.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMjQ3NDM1_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201107215834915.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMjQ3NDM1,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMjQ3NDM1_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201107221907727.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMjQ3NDM1,size_16,color_FFFFFF,t_70#pic_center