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

Map从入门到性能分析

课程目标

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

运行环境：

1. Idea
2. 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 userMap = new HashMap();

        userMap.put("Tom", 23);

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

5、HashMap的Entry结构

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

6、使用示例

Map 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取到value

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 entry : userMap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}
// Tom: 21
// Steve: 23
// Jack: 22

10、HashMap的遍历-Iterator

import java.util.Iterator;

Iterator iterator = userMap.entrySet().iterator();

while (iterator.hasNext()){
    Map.Entry 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 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 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 userMap) {
        long start = System.currentTimeMillis();

        Integer value;
        for (Map.Entry 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 userMap) {
        long start = System.currentTimeMillis();
        Iterator iterator = userMap.entrySet().iterator();

        Integer value;
        while (iterator.hasNext()) {
            Map.Entry 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 userMap = new HashMap();

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

        String key;

        for (int i = 0; i > 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 = 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