Java中Map相关讲解（HashMap、TreeMap、LinkedHashMap）

哈希表：

??哈希表（Hash table，也叫散列表）是一种数据结构，它可以根据关键码值(Key value)而直接进行访问。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
??给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希（Hash）表，函数f(key)为哈希(Hash) 函数。
??哈希表的插入和查找操作都非常快速，时间复杂度为O(1)，这使得它在很多程序中都被广泛使用，例如拼音检查器。然而，哈希表也有自己的缺点，例如当哈希表被填满时，性能下降的比较严重。此外，哈希表是由链表和数组组成的，其中链表负责增删操作，效率极高，但查询效率较低；数组则负责查询操作，查询效率极高，但增删效率较低。因此，哈希表中继承了链表和数组的优缺点，不仅查询效率高，增删效率也高。

红黑树：

??红黑树（Red Black Tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构。它最早由Rudolf Bayer在1972年发明，当时被称为平衡二叉B树（symmetric binary B-trees）。后来在1978年被Leo J. Guibas和Robert Sedgewick修改为现在的“红黑树”。
??红黑树的主要性质如下：
??1. 每个节点要么是红色，要么是黑色。
??2. 根节点总是黑色的。
??3. 每个叶节点（NIL或空节点）都是黑色的。
??4. 如果一个节点是红色的，那么它的两个子节点都是黑色的。
??5. 对于每个节点，从该节点到其所有后代叶节点的简单路径上，黑色节点的数量相同。
??红黑树可以在O(log n)时间内做查找、插入和删除操作，这里的n是树中元素的数目。虽然红黑树在最坏情况下的时间复杂度比AVL树稍差一些，但在插入和删除时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。红黑树在实践中是高效的，是一种相对平衡的二叉查找树。

链表：

??链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
??相比于线性表顺序结构，链表操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多。但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
??链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言，如C,C++和Java依靠易变工具来生成链表。

Map 概述：

??Map接口是一个键值对的集合，它继承自Collection接口中的size()和isEmpty()等方法，同时还提供了根据键查找值的方法，以及添加、删除和更新键值对的方法。在Java中，Map接口有几个常见的实现类，每个实现类都具有不同的性能和用途。
??HashMap：基于哈希表实现，具有快速的查找和插入操作，适用于需要快速查找键值对的场景。
??TreeMap：基于红黑树实现，可以对键进行排序，并提供了一系列与排序相关的方法，适用于需要对键进行排序的场景。
??LinkedHashMap：基于哈希表和链表实现，保持键值对的插入顺序，适用于需要保持插入顺序的场景。

??HashMap，TreeMap，LinkedHashMap比较：
??HashMap，TreeMap，和LinkedHashMap都是Java中用于存储键值对的数据结构，但它们之间有一些重要的区别。

1. HashMap：
   ?? ● 这是一个基于哈希表的Map实现。它提供了极快的查找速度，通常在O(1)的时间复杂度内。
   ?? ● HashMap不保证元素的顺序，这使得它的插入和查找操作非常高效，但如果你需要保持插入顺序，你可能需要使用LinkedHashMap。
   ?? ● HashMap是线程不安全的，如果你在多线程环境中使用，你可能需要使用Collections.synchronizedMap()方法或者ConcurrentHashMap。

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

public class HashMapExample {
    public static void main(String[] args) {
        Map<String, Integer> scores = new HashMap<>();
        scores.put("Alice", 90);
        scores.put("Bob", 80);
        scores.put("Charlie", 95);

        System.out.println("Scores: " + scores);

        scores.remove("Bob");
        System.out.println("Scores after removal: " + scores);

        int aliceScore = scores.get("Alice");
        System.out.println("Alice's score: " + aliceScore);

        boolean containsCharlie = scores.containsKey("Charlie");
        System.out.println("Contains Charlie: " + containsCharlie);
    }
}

2. TreeMap：
   ?? ● TreeMap是基于红黑树的Map实现，它保证了键的自然顺序或者自定义顺序。这意味着当你迭代TreeMap时，元素会按照键的排序顺序返回。
   ?? ● TreeMap的查找、插入和删除操作的时间复杂度都是O(log n)，这比HashMap慢一些，但比ArrayList快一些。
   ?? ● TreeMap也是线程不安全的，如同HashMap，如果你在多线程环境中使用，你可能需要使用Collections.synchronizedMap()方法。

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

public class TreeMapExample {
    public static void main(String[] args) {
        Map<String, Integer> scores = new TreeMap<>();
        scores.put("Alice", 90);
        scores.put("Bob", 80);
        scores.put("Charlie", 95);

        System.out.println("Scores: " + scores);

        scores.remove("Bob");
        System.out.println("Scores after removal: " + scores);

        int aliceScore = scores.get("Alice");
        System.out.println("Alice's score: " + aliceScore);

        String firstKey = scores.firstKey();
        String lastKey = scores.lastKey();
        System.out.println("First key: " + firstKey);
        System.out.println("Last key: " + lastKey);
    }
}

3. LinkedHashMap：
   ?? ● LinkedHashMap是HashMap的一个子类，它通过维护一个双向链表来保证插入顺序。这意味着元素按照它们插入的顺序被保存。最近最少使用的元素会被放在链表的尾部。
   ?? ● LinkedHashMap的查找操作时间复杂度为O(1)，与HashMap相同。但是插入和删除操作的时间复杂度为O(n)，这比HashMap慢一些。
   ?? ● LinkedHashMap也是线程不安全的，如同HashMap和TreeMap，如果你在多线程环境中使用，你可能需要使用Collections.synchronizedMap()方法。

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

public class LinkedHashMapExample {
    public static void main(String[] args) {
        Map<String, Integer> scores = new LinkedHashMap<>();
      
        scores.put("Alice", 90);
        scores.put("Bob", 80);
        scores.put("Charlie", 95);

        System.out.println("Scores: " + scores);

        scores.remove("Bob");
        System.out.println("Scores after removal: " + scores);

        int aliceScore = scores.get("Alice");
        System.out.println("Alice's score: " + aliceScore);

        boolean containsCharlie = scores.containsKey("Charlie");
        System.out.println("Contains Charlie: " + containsCharlie);
    }
}

?? 总的来说，选择哪种类型的Map取决于你的需求。如果你需要快速查找并且不关心元素的顺序，那么HashMap是最好的选择。如果你需要保持元素的顺序并且不关心线程安全问题，那么TreeMap是最好的选择。如果你需要保持插入的顺序并且不关心线程安全问题，那么LinkedHashMap是最好的选择。