Map集合体系全景图-五八三

什么是Map

Map集合是一种存储键值对的数据结构，其中每个键都唯一且对应一个值。Map集合通常用于需要快速查找和访问数据的场景，例如字典、缓存、配置文件等。

Java中的Map集合有多种实现，包括HashMap、TreeMap、LinkedHashMap等。其中，HashMap是最常用的实现，它使用哈希表来存储键值对，可以快速查找和访问数据。TreeMap使用红黑树来存储键值对，可以保证键的有序性。LinkedHashMap则使用双向链表来维护键值对的插入顺序。

Map集合提供了一系列方法来操作键值对，例如put()方法用于添加键值对，get()方法用于获取指定键对应的值，containsKey()方法用于判断是否包含指定键等。

使用Map集合时需要注意键的唯一性，如果添加了重复的键，则会覆盖原有的值。此外，Map集合的键和值可以是任意类型，但通常使用基本类型或其包装类、字符串等常见类型作为键和值。

HashMap特点

HashMap是基于哈希表实现的，可以快速地进行插入、查找和删除操作。

HashMap允许存储键和值。

HashMap是无序的，即元素的顺序不是按照插入顺序或者其他顺序排列的。

HashMap的性能受到哈希函数的影响，如果哈希函数不好，可能会导致哈希冲突，影响性能。

HashMap的默认初始容量为16，负载因子为0.75，当HashMap中的元素数量超过容量*负载因子时，会自动扩容。

HashMap是线程不安全的，如果多个线程同时对同一个HashMap进行操作，可能会导致数据不一致的问题。可以使用ConcurrentHashMap来解决线程安全问题。

JDK1.8，哈希表采用的数据结构：

哈希表采用的数据结构是数组+链表/红黑树的组合结构。具体来说，哈希表中的每个元素都是一个链表或红黑树，数组中的每个元素指向一个链表或红黑树的根节点。当哈希表中的元素数量较少时，每个元素都是一个链表；当元素数量较多时，会将链表转化为红黑树，以提高查找效率

JDK1.8之前，哈希表采用的数据结构：

哈希表采用的数据结构是数组和链表的组合，也就是链表散列。每个数组元素都是一个链表的头节点，当发生哈希冲突时，新的元素会被插入到对应数组元素的链表中。这种数据结构的缺点是在哈希冲突严重时，链表会变得很长，导致查询效率降低。
HashMap优缺点

数组和链表+红黑树为什么比数组+链表更高效

数组：随机访问元素的时间复杂度为O(1)，插入和删除元素的时间复杂度为O(n)

链表：插入和删除元素的时间复杂度为O(1)，随机访问元素的时间复杂度为O(n)

红黑树的时间复杂度为O(log n)，具有较好的平衡性和搜索性能，适用于需要频繁插入、删除和搜索的场景。
因此，红黑树相比于数组和链表，具有更高的效率，尤其是在需要频繁插入、删除和搜索的场景下。

HashMap的优点：

快速的查找和插入操作，时间复杂度为O(1)；

可以存储大量的键值对；

支持键和值；

可以通过迭代器遍历键值对；

可以通过键快速查找对应的值。

HashMap的缺点：

HashMap是非线程安全的，需要在多线程环境下使用时进行同步处理；

HashMap的初始容量和负载因子需要合理设置，否则会影响性能；

HashMap的遍历顺序是不确定的，不适合需要按照顺序访问元素的场景；

当HashMap中的元素数量达到一定程度时，会出现哈希冲突，影响性能；

HashMap的实现是基于哈希表的，因此在存储空间上比较浪费。

HashMap使用场景

快速查找：如果需要快速查找键值对，可以使用HashMap。

高效插入和删除：如果需要高效插入和删除键值对，可以使用HashMap。

存储不同类型的键值对：如果需要存储不同类型的键值对，可以使用HashMap。

缓存：HashMap可以用于缓存数据，可以将数据存储在HashMap中，避免频繁地从数据库或者其他存储介质中读取数据。

HashMap和List是两种不同的数据结构，各自有自己的优缺点。

HashMap的优点：

快速查找：HashMap是基于哈希表实现的，可以快速查找元素，时间复杂度为O(1)。

高效插入和删除：HashMap的插入和删除操作也很高效，时间复杂度为O(1)。

可以存储键值对：HashMap可以存储键值对，可以根据键快速查找对应的值。

HashMap的缺点：

内存占用较大：HashMap需要维护哈希表，需要占用较多的内存空间。

不支持顺序访问：HashMap是无序的，不支持按照插入顺序或者其他顺序访问元素。

哈希冲突：如果哈希函数不好，可能会出现哈希冲突，影响查找效率。

List的优点：

支持顺序访问：List是有序的，支持按照插入顺序或者其他顺序访问元素。

内存占用较小：List只需要存储元素本身，不需要维护哈希表，占用内存较小。

可以存储重复元素：List可以存储重复元素。

List的缺点：

查找效率低：List的查找效率较低，需要遍历整个列表，时间复杂度为O(n)。

插入和删除效率低：List的插入和删除操作效率较低，需要移动其他元素，时间复杂度为O(n)。

不支持快速查找：List不支持快速查找元素，需要遍历整个列表才能找到对应的元素。

HashMap和List的使用场景：

如果需要快速查找元素，可以使用HashMap。

如果需要按照顺序访问元素，可以使用List。

如果需要存储键值对，并且需要快速查找对应的值，可以使用HashMap。

如果需要存储重复元素，可以使用List。

HashMap简单使用案例教学

假设我们要统计一篇文章中每个单词出现的次数，可以使用HashMap来实现。具体步骤如下：

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {

    String article = "Java is a programming language and computing platform first released by Sun Microsystems in 1995. It is the underlying technology that powers state-of-the-art programs including utilities, games, and business applications. Java runs on more than 1 billion devices worldwide, including PCs, mobile phones, and smart TVs.";

    //1.  将文章内容按照空格分割成单词，并存储到一个字符串数组中。
    String[] words = article.split(" ");
    //2.创建一个HashMap对象，用于存储每个单词出现的次数
    HashMap<String, Integer> wordCount = new HashMap<>();
    //3.  遍历单词数组，统计每个单词出现的次数，并将结果存储到HashMap中。
    for (String word : words) {
        if (wordCount.containsKey(word)) {
            wordCount.put(word, wordCount.get(word) + 1);
        } else {
            wordCount.put(word, 1);
        }
    }
    //遍历HashMap打印每个单词出现的次数
    for (String word : wordCount.keySet()) {
        System.out.println(word + ": " + wordCount.get(word));
    }
}

HashMap源码分析

//定义了一个泛型类HashMap，它继承了AbstractMap类，并实现了Map接口，同时也实现了Cloneable和Serializable（序列化）接口
//AbstractMap是一个抽象类，实现了Map接口的大部分方法，但是将一些方法留给具体的子类去实现
public class HashMap<K,V> extends AbstractMap<K,V>  
implements Map<K,V>, Cloneable, Serializable {}
//默认的初始容量，即HashMap创建时的默认容量大小为16。
//<< 是Java中的位运算符，表示左移运算符
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
//HashMap的最大容量，即2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;  
//负载因子，默认达到多少进行扩容那
static final float DEFAULT_LOAD_FACTOR = 0.75f;  
//当链表长度达到该值时，链表会转化为红黑树
static final int TREEIFY_THRESHOLD = 8;  
//当红黑树节点数小于该值时，红黑树会转化为链表
static final int UNTREEIFY_THRESHOLD = 6;  
//当HashMap的容量小于该值时，不会将链表转化为红黑树
static final int MIN_TREEIFY_CAPACITY = 64;

//下面这段代码定义了HashMap中的节点(Node)类，
//每个节点包含了键(key)、值(value)、哈希值(hash)和指向下一个节点的指针(next)。
//节点类实现了Map.Entry接口，提供了getKey()、getValue()、setValue()等方法，
//同时还重写了hashCode()、equals()和toString()方法，以便在HashMap中使用。
static class Node<K,V> implements Map.Entry<K,V> {  
final int hash;  
final K key;  
V value;  
Node<K,V> next;  
  
Node(int hash, K key, V value, Node<K,V> next) {  
this.hash = hash;  
this.key = key;  
this.value = value;  
this.next = next;  
}  
  
public final K getKey() { return key; }  
public final V getValue() { return value; }  
public final String toString() { return key + "=" + value; }  
  
public final int hashCode() {  
return Objects.hashCode(key) ^ Objects.hashCode(value);  
}  
  
public final V setValue(V newValue) {  
V oldValue = value;  
value = newValue;  
return oldValue;  
}  
  
public final boolean equals(Object o) {  
if (o == this)  
return true;  
if (o instanceof Map.Entry) {  
Map.Entry<?,?> e = (Map.Entry<?,?>)o;  
if (Objects.equals(key, e.getKey()) &&  
Objects.equals(value, e.getValue()))  
return true;  
}  
return false;  
}  
}