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