Map集合接口具體實作類：LinkedHashMap以及TreeMap

1.LinkedHashMap的概述
2.TreeMap概述
總結

前面我們學習了Map接口中最常用的實作類：HashMap，并且對HashMap的底層實作原理做了一定的深入探讨。下面我們将要了解的是Map接口中的另外兩大實作類：LinkedHashMap與TreeMap。

1.LinkedHashMap的概述

LinkedHashMap實作了Map接口，而且繼承自HashMap。

它的多種操作都是建立在HashMap的操作基礎上的。

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

同HashMap不同的是，LinkedHashMap維護了一個Entry的雙向連結清單，保證了插入Entry中的順序。

JavaSE學習筆記 Map接口的具體實作類：LinkedHashMap以及TreeMap1.LinkedHashMap的概述2.TreeMap概述總結

如上圖所示，加入順序為key1，key2，key3，key4，就會維護上面紅線所示的雙向連結清單。

為實作雙向連結清單，LinkedHashMap底層源碼這樣進行設定：

//LinkedHashMap中的node直接繼承自HashMap中的Node。并且增加了雙向的指針
static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

由上面源碼中設定可知，LinkedHashMap 鍵的資料結構是連結清單和哈希表，連結清單保證了鍵有序，哈希表保證了鍵唯一。

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
import java.util.function.BiConsumer;

public class MyTest {
    public static void main(String[] args) {
        LinkedHashMap<String, String> map = new LinkedHashMap<>();
        //LinkedHashMap 鍵的資料結構是 連結清單和哈希表，連結清單保證了鍵有序，哈希表保證了鍵唯一
        map.put("s001", "張三");
        map.put("s001", "張三豐");
        map.put("s002", "李四");
        map.put("s003", "王五");
        map.put("s004", "陳六");

        //周遊LinkedHashMap方式一
        Set<String> keySet = map.keySet();
        for (String key : keySet) {
            String value = map.get(key);
            System.out.println(key+"======="+value);
        }
        System.out.println("============");

        //周遊LinkedHashMap方式二
        Set<Map.Entry<String, String>> entries = map.entrySet();
        for (Map.Entry<String, String> entry : entries) {
            String key = entry.getKey();
            String value = entry.getValue();
            System.out.println(key+"==="+value);
        }
        System.out.println("=============");

        //周遊LinkedHashMap方式三
        map.forEach(new BiConsumer<String, String>() {
            @Override
            public void accept(String key, String value) {
                System.out.println(key+"===="+value);
            }
        });
    }
}

LinkedHashMap相對于HashMap而言，它繼承了HashMap，僅僅重寫了幾個方法，以改變它疊代周遊時的順序。

2.TreeMap概述

TreeMap的資料結構為紅黑樹，可以保證鍵的排序性和唯一性。排序分為自然排序與比較器排序。TreeMap線程不安全，并且效率比較高。

案例示範：TreeMap集合鍵是Integer，值是String類型

public class MyTest2 {
    public static void main(String[] args) {
        TreeMap<Integer, String> treemap = new TreeMap<>();

        treemap.put(15,"張三");
        treemap.put(10,"李四");
        treemap.put(13,"王五");
        treemap.put(14,"陳六");
        treemap.put(11,"劉七");
        treemap.put(12,"趙八");

        System.out.println(treemap);
    }
}

TreeMap是雙列集合，雙列集合的鍵需要保持唯一，在此例中Intege類中源碼實作Compareable接口，重寫了CompareTo()方法。

運作後的結果為：

JavaSE學習筆記 Map接口的具體實作類：LinkedHashMap以及TreeMap1.LinkedHashMap的概述2.TreeMap概述總結

案例示範2：TreeMap集合鍵是Student，值是String類型的案例，按照Student類中的屬性年齡的大小進行排序。

方式一：自然排序

//自定義類：Student類
//自然排序，實作Compareable接口，重寫CompareTo方法
public class Student  implements Comparable<Student>{
    private String name;
    private int age;

    public Student() {
    }

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return age == student.age &&
                Objects.equals(name, student.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    @Override
    public int compareTo(Student stu) {
        //比較年齡大小
        int num = age-stu.age;
        //如果年齡相同，比較姓名内容是否相同
        int num1=num==0?name.compareTo(stu.name):num;

        return num1;

    }
}


//測試類
import java.util.TreeMap;
public class MyTest3 {
    public static void main(String[] args) {
        TreeMap<Student, String> treemap = new TreeMap<>();

        treemap.put(new Student("張三",23),"s001");
        treemap.put(new Student("李四",24),"s002");
        treemap.put(new Student("王五",25),"s003");
        treemap.put(new Student("陳六",23),"s004");

        System.out.println(treemap);
    }
}

運作後的結果為：

JavaSE學習筆記 Map接口的具體實作類：LinkedHashMap以及TreeMap1.LinkedHashMap的概述2.TreeMap概述總結

方案二：比較器排序

//自定義的Student類
public class Student {
    private String name;
    private int age;

    public Student() {
    }

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return age == student.age &&
                Objects.equals(name, student.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';


    }
    }


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

public class MyTest {
    public static void main(String[] args) {
        TreeMap<Student, String> treemap = new TreeMap<>(new Comparator<Student>() {
            @Override
            public int compare(Student s1, Student s2) {
                //比較年齡大小
                int num = s1.getAge() - s2.getAge();
                //當年齡相同時，比較姓名内容是否相等
                int num2 = num == 0 ? s1.getName().compareTo(s2.getName()) : num;
                return num2;
            }
        });


        treemap.put(new Student("張三",23),"s001");
        treemap.put(new Student("李四",24),"s002");
        treemap.put(new Student("王五",25),"s003");
        treemap.put(new Student("陳六",23),"s004");

        System.out.println(treemap);


    }
}

運作後的結果為：

JavaSE學習筆記 Map接口的具體實作類：LinkedHashMap以及TreeMap1.LinkedHashMap的概述2.TreeMap概述總結

總結

本節主要介紹了LinkedHashMap以及TreeMap的使用，其中需要了解LinkedHashMap與HashMap的差別:LinkedHashMap相對于HashMap而言，它繼承了HashMap，僅僅重寫了幾個方法，以改變它疊代周遊時的順序。TreeMap則重點掌握排序的兩種方式：自然排序與比較器排序。

JavaSE學習筆記 Map接口的具體實作類：LinkedHashMap以及TreeMap1.LinkedHashMap的概述2.TreeMap概述總結

JavaSE學習筆記 Map接口的具體實作類：LinkedHashMap以及TreeMap1.LinkedHashMap的概述2.TreeMap概述總結

Map集合接口具體實作類：LinkedHashMap以及TreeMap

1.LinkedHashMap的概述

2.TreeMap概述

總結

繼續閱讀

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Java中的日期類（Date）月曆類(Calendar)及其與String的轉換綜合練習——輸入生産日期計算保存期限及促銷日

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器