Java笔记：Map从入门到性能分析

Map从入门到性能分析

课程目标

HashMap的构造方法，合适的遍历，复制转换
HashMap的底层原理（存取、初始化、扩容）
TreeMap、LinkedHashMap的用法
性能分析

运行环境：

Idea
Java Version 1.8

Map接口及其实现类

1、继承关系

Map
    -HashMap 
        -LinkedHashMap
    -SortedMap
        -TreeMap

2、Map接口通用的方法

// 存
V put(K key, V value)

// 取
V get(Object key)

// 数量
int size()

// 删除
V remove(Object key)

// 包含测试
boolean containsKey(Object key)

3、HashMap构造方法

HashMap()

// initialCapacity 初始化大小
HashMap(int initialCapacity)

// loadFactor 负载因子
HashMap(int initialCapacity, float loadFactor)

4、HashMap基本用法

package com.demo.map;

import java.util.HashMap;
import java.util.Map;

public class MapDemo {
    public static void main(String[] args) {
        Map<String, Integer> userMap = new HashMap<>();

        userMap.put("Tom", 23);

        System.out.println(userMap.get("Tom"));
        // 23
    }
}

5、HashMap的Entry结构

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

6、使用示例

Map<String, Integer> userMap = new HashMap<>();

userMap.put("Tom", 21);
userMap.put("Jack", 22);
userMap.put("Steve", 23);

System.out.println(userMap.get("Tom"));
// 21

System.out.println(userMap);
// {Tom=21, Steve=23, Jack=22}

7、HashMap的遍历-keySet

获取key, 再通过key取到valu

for (String key : userMap.keySet()) {
    System.out.println(key + ": " + userMap.get(key));
}
// Tom: 21
// Steve: 23
// Jack: 22

8、HashMap的遍历-values

只能获取value

for (Integer value : userMap.values()) {
    System.out.println(value);
}
// 21
// 23
// 22

9、HashMap的遍历-entrySet

获取Map.Entry 对象

for (Map.Entry<String, Integer> entry : userMap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}
// Tom: 21
// Steve: 23
// Jack: 22

10、HashMap的遍历-Iterator

import java.util.Iterator;

Iterator<Map.Entry<String, Integer>> iterator = userMap.entrySet().iterator();

while (iterator.hasNext()){
    Map.Entry<String, Integer> entry = iterator.next();
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

// Tom: 21
// Steve: 23
// Jack: 22

11、性能分析

完整代码

package com.demo.map;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class MapDemo {

    public static void showMapByKeySet(Map<String, Integer> userMap) {
        long start = System.currentTimeMillis();

        Integer value;
        for (String key : userMap.keySet()) {
            // System.out.println(key + "=" + userMap.get(key));
            value = userMap.get(key);
        }

        long end = System.currentTimeMillis();
        System.out.println("keySet=" + (end - start));
    }


    public static void showMapByValues(Map<String, Integer> userMap) {
        long start = System.currentTimeMillis();

        Integer value;
        for (Integer v : userMap.values()) {
            // System.out.println(value);
            value = v;
        }

        long end = System.currentTimeMillis();
        System.out.println("values=" + (end - start));
    }


    public static void showMapByEntrySet(Map<String, Integer> userMap) {
        long start = System.currentTimeMillis();

        Integer value;
        for (Map.Entry<String, Integer> entry : userMap.entrySet()) {
            // System.out.println(entry.getKey() + ": " + entry.getValue());
            value = entry.getValue();
        }

        long end = System.currentTimeMillis();
        System.out.println("entrySet=" + (end - start));
    }


    public static void showMapByIterator(Map<String, Integer> userMap) {
        long start = System.currentTimeMillis();
        Iterator<Map.Entry<String, Integer>> iterator = userMap.entrySet().iterator();

        Integer value;
        while (iterator.hasNext()) {
            Map.Entry<String, Integer> entry = iterator.next();
            // System.out.println(entry.getKey() + ": " + entry.getValue());
             value = entry.getValue();
        }

        long end = System.currentTimeMillis();
        System.out.println("iterator=" + (end - start));
    }


    public static void main(String[] args) {
        Map<String, Integer> userMap = new HashMap<>();

        String[] keys = new String[]{
                "a", "b", "c", "d", "e",
                "f", "g", "h", "i", "j"
        };

        String key;

        for (int i = 0; i < 100000; i++) {
            // 让key接近真实环境
            key = keys[(int) (Math.random() * keys.length)] + i * 100;
            userMap.put(key, i);
        }

        showMapByKeySet(userMap); // keySet=16
        showMapByValues(userMap); // values=9
        showMapByEntrySet(userMap); // entrySet=10
        showMapByIterator(userMap); // iterator=9
        
    }
}

结论：

推荐 Iterator
避免 keySet
常用 EntrySet

12、HashMap示例

Map<String, String> user1 = new HashMap<>();
user1.put("name", "Tom");
user1.put("age", "23");

Map<String, String> user2 = new HashMap<>();
user2.put("name", "Jack");
user2.put("age", "24");


Map<String, String> user3 = new HashMap<>();
user3.put("name", "Steve");
user3.put("age", "25");


// 将数据放入Map
Map<String, Map> userMap = new HashMap<>();
userMap.put("Tom", user1);
userMap.put("Jack", user2);
userMap.put("Steve", user3);

System.out.println(userMap);
// {
//  Tom={name=Tom, age=23},
//  Steve={name=Steve, age=25},
//  Jack={name=Jack, age=24}
// }


// 将数据放入List
List<Map> userList = new ArrayList<>();
userList.add(user1);
userList.add(user2);
userList.add(user3);

System.out.println(userList);
// [
//  {name=Tom, age=23},
//  {name=Jack, age=24},
//  {name=Steve, age=25}
// ]

HashMap底层原理

1、HashMap默认参数

初始化大小=16
负载因子=0.75 有效长度：16*0.75 = 12
扩容倍数=2

HashMap()

// 等同于
HashMap(16, 0.75f)

根据hash码取余数来决定位置

key是字符串类型

先使用hashCode()方法将key转换成hash码后并进行优化

对优化后的hash码进行取址，确定在HashMap中的位置

int indexFor(int h, int length)

数字key存放原理

初始大小 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

要存入的值 
120 % 16  = 8
37 % 16   = 5
61 % 16   = 13 
40 % 16   = 8
92 % 16   = 12
78 % 16   = 14

存放位置 0 1 2 3 4  5   6  7 8    9 10 11 12  13  14 15
                   37       120          92  61  78
                            40

验证代码

Map<Integer, String> map = new HashMap<>();

map.put(120, "120");
map.put(37, "37");
map.put(61, "61");
map.put(40, "40");
map.put(92, "92");
map.put(78, "78");

System.out.println(map);
//  {37=37, 120=120, 40=40, 92=92, 61=61, 78=78}

2、带参构造方法

HashMap(int initialCapacity, float loadFactor)
HashMap(int initialCapacity)

HashMap(5)

initialCapacity 初始化长度内部计算

// 1073741824
static final int MAXIMUM_CAPACITY = 1 << 30;

static final int tableSizeFor(int cap) {
    int n = cap - 1; // 4 => 100
    n |= n >>> 1;  // 100 | 010 => 110
    n |= n >>> 2;  // 110 | 001 => 111
    n |= n >>> 4;  // 111 | 000 => 111
    n |= n >>> 8;  // 111 | 000 => 111
    n |= n >>> 16; // 111 | 000 => 111
    // 111 => 7 + 1 => 8
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

// 取到大于5，最小的2的n次方
tableSizeFor(5) // 8

2倍扩容后重新计算位置

120 % 16 = 8   ->  120 % 32 = 24
37  % 16 = 5   ->  37  % 32 = 5
61  % 16 = 13  ->  61  % 32 = 29
40  % 16 = 8   ->  40  % 32 = 8
92  % 16 = 12  ->  92  % 32 = 28
78  % 16 = 14  ->  78  % 32 = 14

3、问题：

// 问题1：初始化长度是多少？
new HashMap(5) // 8

// 问题2：以下初始化后存入10000条数据，会发生扩容吗？
new HashMap(10000, 0.75f)
// 后台优化：2^14 = 16384 * 0.75 = 12288
// 所以，不会扩容

4、性能测试

package com.demo.map;

import java.util.HashMap;
import java.util.Map;

/**
 * 创建10个HashMap,每个HashMap添加1万条数据
 * 传递不同的构造参数，比较速度
 *
 * initialCapacity=16      avg=2318299
 * initialCapacity=10000   avg=1926625
 */
public class MapDemo {

    public static void main(String[] args) {
        long sum = 0L;

        for (int i = 0; i < 10; i++) {
            sum += inputMap(10000);
        }

        System.out.println("avg=" + (sum/10));

    }

    public static long inputMap(int initialCapacity) {
        Map<String, Object> map = new HashMap<>(initialCapacity);
        String key;

        // 获取纳秒
        long start = System.nanoTime();

        for (int i = 0; i < 10000; i++) {
            key = String.valueOf(i);
            map.put(key, "value");
        }

        long end = System.nanoTime();
        long timespan = end - start;
        System.out.println("timespan=" + timespan);
        return timespan;
    }

}

HashMap常用方法

添加元素put putIfAbsent

判断是否为空isEmpty，删除节点remove，清空clear

判断是否有key(containsKey)，是否有value(containsValue)

替换某个key的value（replace， put）

代码实例

Map<String, Object> map = new HashMap<>();

// 添加数据
map.put("name", "Tom");
map.put("age", "12");

// 替换数据
map.put("name", "Jack");
// 替换数据
map.replace("name", "Steve");

//存在则不替换
map.putIfAbsent("name", "Seven");

// 移除数据
map.remove("age");

// 判断key存在，值存在
System.out.println(map.containsKey("name")); // true
System.out.println(map.containsValue("name")); // false

// 判空
System.out.println(map.isEmpty());

System.out.println(map);
// {name=Steve, age=12}

// 清空数据
map.clear();

forEach (Lambda表达式)

Map<String, Integer> map = new HashMap<>();

// 添加数据
map.put("a", 1);
map.put("b", 2);

map.forEach((key, value) -> {
    System.out.println(key + ": " + value);
});
// a: 1
// b: 2

getOrDefault获取默认值

Map<String, Integer> map = new HashMap<>();

Integer value = map.getOrDefault("a", 666);
System.out.println(value); // 666

LinkedHashMap

性能测试

数据量不同，性能表现也不一样

package com.demo.map;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;


public class MapDemo {

    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        Map<String, Integer> linkedMap = new LinkedHashMap<>();

        long start, end;

        // 插入测试
        start = System.currentTimeMillis();
        for (int i = 0; i < 100000; i++) {
            map.put(String.valueOf(i), i);
        }
        end = System.currentTimeMillis();
        System.out.println("map put=" + (end - start));

        start = System.currentTimeMillis();
        for (int i = 0; i < 100000; i++) {
            linkedMap.put(String.valueOf(i), i);
        }
        end = System.currentTimeMillis();
        System.out.println("linkedMap put=" + (end - start));

        // 取出测试
        start = System.currentTimeMillis();
        for (Integer value : map.values()) {
        }
        end = System.currentTimeMillis();
        System.out.println("map get=" + (end - start));

        start = System.currentTimeMillis();
        for (Integer value : map.values()) {
        }
        end = System.currentTimeMillis();
        System.out.println("linkedMap get=" + (end - start));

        // map put = 29
        // linkedMap put = 22
        // map get = 6
        // linkedMap get = 3
    }

}

LinkedHashMap实现LRU(Least Recently Used)

LinkedHashMap有序

LRU实现

package com.demo.map;

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUMap<K, V> extends LinkedHashMap<K, V> {

    private int maxSize;

    public LRUMap(int maxSize){
        super(16, 0.75f, true);
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > this.maxSize;
    }
}

package com.demo.map;

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUMap<K, V> extends LinkedHashMap<K, V> {

    private int maxSize;

    public LRUMap(int maxSize){
        super(16, 0.75f, true);
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > this.maxSize;
    }
}

测试代码

package com.demo.map;

public class MapDemo {

    public static void main(String[] args) {
        LRUMap<String, Integer> lruMap = new LRUMap<>(3);
        lruMap.put("a", 1);
        lruMap.put("b", 2);

        lruMap.get("a");
        lruMap.put("c", 3);
        lruMap.put("d", 4);

        System.out.println(lruMap);
        //    {a=1, c=3, d=4}
    }

}

TreeMap

默认是key升序排序，可以自定义比较器Comparator

package com.demo.map;

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class MapDemo {

    public static void main(String[] args) {
        Map<String, String> treeMap = new TreeMap<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o2.compareTo(o1);
            }
        });

        treeMap.put("a", "a");
        treeMap.put("c", "c");
        treeMap.put("b", "b");

        System.out.println(treeMap);
        // 默认： {a=a, b=b, c=c}
        // 比较器排序后：{c=c, b=b, a=a}
    }

}

耗时对比

package com.demo.map;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.TreeMap;


public class MapDemo {

    public static void main(String[] args) {
        Map<String, Integer> hashMap = new HashMap<>();
        Map<String, Integer> linkedMap = new LinkedHashMap<>();
        Map<String, Integer> treeMap = new TreeMap<>();

        long count = 1000;

        long start, end;

        // 插入测试
        start = System.currentTimeMillis();
        for (int i = 0; i < count; i++) {
            hashMap.put(String.valueOf(i), i);
        }
        end = System.currentTimeMillis();
        System.out.println("map put=" + (end - start));

        start = System.currentTimeMillis();
        for (int i = 0; i < count; i++) {
            linkedMap.put(String.valueOf(i), i);
        }
        end = System.currentTimeMillis();
        System.out.println("linkedMap put=" + (end - start));

        start = System.currentTimeMillis();
        for (int i = 0; i < count; i++) {
            treeMap.put(String.valueOf(i), i);
        }
        end = System.currentTimeMillis();
        System.out.println("treeMap put=" + (end - start));

        // 取出测试
        start = System.currentTimeMillis();
        for (Integer value : hashMap.values()) {
        }
        end = System.currentTimeMillis();
        System.out.println("map get=" + (end - start));

        start = System.currentTimeMillis();
        for (Integer value : linkedMap.values()) {
        }
        end = System.currentTimeMillis();
        System.out.println("linkedMap get=" + (end - start));

        start = System.currentTimeMillis();
        for (Integer value : treeMap.values()) {
        }
        end = System.currentTimeMillis();
        System.out.println("treeMap get=" + (end - start));
    }

}

课程小结

Map接口的常见方法
对比不同的遍历方法，效率
底层原理，创建Map时，针对不同情况选择合适的构造方法
HashMap、LinkedMap、TreeMap区别与选择

Java笔记：Map从入门到性能分析

课程目标

运行环境：

Map接口及其实现类

HashMap底层原理

LinkedHashMap

TreeMap

耗时对比

课程小结

继续阅读

关于Gradle配置的小结

Java小案例——随机数猜测随机数猜测

nginx location中斜线的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的简单使用

neo4j之cypher使用文档

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

spark/scala关于【资源文件】加载方法概述外部文件加载方案测试资源文件打包入jar包中小结

mybatis_入门程序Mybatis入门

AOP编程_Android优雅权限框架(1)概念基础，2021金三银四前言正文大纲正文

Effective Java 8:通用程序设计

OOM三种类型

工厂模式-三种类型

【递归】高效率求2的n次幂

win10本地scala和spark安装安装scala安装spark

scala (3) Function 和 Method