Map集合体系全景图
站长
· 阅读数 17
什么是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;
}
}
为什么要定义节点类
在HashMap中，每个键值对都被封装在一个节点(Node)对象中。节点对象包含了键、值、哈希值和指向下一个节点的引用。定义节点类的目的是为了在HashMap中存储键值对，并且可以通过哈希值快速定位到对应的节点。同时，节点类还实现了Map.Entry接口，使得节点对象可以被视为一个键值对。
继续HashMap源码分析
//并返回一个int类型的哈希值
static final int hash(Object key) {
int h;
//它首先判断传入的对象是否为空，如果是则返回0
//否则调用对象的hashCode()方法得到一个int类型的哈希码h
//然后将h右移16位并与原来的h进行异或运算，最终得到一个int类型的哈希值，拉链法方式来进行计算
//它可以减少哈希冲突的概率
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//用于获取一个对象的Comparable类型
static Class<?> comparableClassFor(Object x) {
//instanceof是Java中的一个关键字，用于判断一个对象是否属于某个类或其子类的实例
if (x instanceof Comparable) {
Class<?> c; //表示一个未知类型的类，可以通过调用其方法获取类的信息。
Type[] ts, as; Type t;
//Type[] ts 表示一个未知类型的数组，用于存储类型信息
//Type t：表示一个未知类型的类型，用于存储类型信息。
ParameterizedType p; //表示一个未知类型的参数类型
if ((c = x.getClass()) == String.class)
// 将变量x的类型赋值给变量c，如果x的类型是String类，则直接返回String类，不进行其他的检查。
return c;
//getGenericInterfaces() 方法返回的是 Type 对象的数组，表示该类所实现的泛型接口的类型。
if ((ts = c.getGenericInterfaces()) != null) {
for (int i = 0; i < ts.length; ++i) {
//判断 是否为 ParameterizedType类型
if (((t = ts[i]) instanceof ParameterizedType) &&
//判断其原始类型是否为 Comparable.class
((p = (ParameterizedType)t).getRawType() ==
Comparable.class) &&
//其实际类型参数 如果 as 不为空 ，并且长度为 1，且第一个参数为 c，
//则说明该类型实现了Comparable接口，并且泛型参数类型为c
(as = p.getActualTypeArguments()) != null &&
as.length == 1 && as[0] == c)
return c;
}
}
}
return null;
}
ParameterizedType是 Java 中的一个接口，表示一个参数化类型，即一个泛型类型实例化后的类型。例如，List<String>就是一个参数化类型，它实例化了List泛型类型，其中的类型参数为String。ParameterizedType接口提供了获取实际类型参数的方法，可以通过它来获取泛型类型实例化后的具体类型。
//该方法用于比较两个对象的大小关系
static int compareComparables(Class<?> kc, Object k, Object x) {
//两个对象类型不一致返回0，否则进行进行比较俩个对象
return (x == null || x.getClass() != kc ? 0 :
((Comparable)k).compareTo(x));
}
//这个方法通常用于计算哈希表的大小，确保哈希表的大小是2的幂次方，以便于哈希函数的计算。
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
// 存储元素的数组，总是2的幂次倍
transient Node<K,V>[] table;
// 存放具体元素的集
transient Set<Map.Entry<K,V>> entrySet;
// 存放元素的个数，注意这个不等于数组的长度。
transient int size;
// 每次扩容和更改map结构的计数器
transient int modCount;
// 阈值(容量*负载因子) 当实际大小超过阈值时，会进行扩容
int threshold;
// 负载因子
final float loadFactor;
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//用于计算大于等于给定整数的最小2的幂次方数。
//这个方法的作用是为了保证HashMap的桶的数量始终是2的幂次方，这样可以更高效地进行哈希计算
this.threshold = tableSizeFor(initialCapacity);
}
//创建一个具有指定初始容量的 HashMap 实例，并使用默认的负载因子
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//段代码中设置为默认的负载因子，而其他字段则使用默认值
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//创建一个包含指定map中所有键值对的新 HashMap 对象
public HashMap(Map<? extends K, ? extends V> m) {
//负载因子为默认
this.loadFactor = DEFAULT_LOAD_FACTOR;
//调用 putMapEntries 方法将指定map中的键值对添加到新的HashMap 对象中
putMapEntries(m, false);
}
//HashMap构造函数中用来将一个已有的Map中的键值对添加到新的HashMap中的方法
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//获取map大小
int s = m.size();
if (s > 0) {
if (table == null) {
//则根据 s 计算出初始容量 ft
float ft = ((float)s / loadFactor) + 1.0F;
//并将其设置为当前 HashMap 的 threshold。
//threshold 是一个阈值，表示当哈希表中的元素数量达到这个值时，
//需要进行扩容操作。在这段代码中，如果 s大于 threshold，就会调用 resize() 方法进行扩容
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
//遍历另一个 Map 中的所有键值对，将其添加到当前 HashMap 中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
Map源码重点扩容
//对哈希表进行扩容的方法
//获取旧表的长度和阈值，然后根据旧表的长度和阈值计算出新表的长度和阈值。
//如果旧表的长度大于0，则判断是否达到了最大容量，如果是则直接返回旧表；否则将旧表长度左移一位得到新表长度
//如果新表长度小于最大容量且旧表长度大于等于默认初始容量，则将阈值也左移一位，即将阈值翻倍
//如果旧表长度为0但阈值大于0，则将阈值作为新表长度；否则使用默认初始容量和默认负载因子计算出新表长度和阈值
//最后根据新表长度创建一个新的哈希表，将旧表中的元素转移到新表中，如果元素的哈希值在旧表长度范围内，则直接放入新表中
//最后根据新表长度创建一个新的哈希表，将旧表中的元素转移到新表中，如果元素的哈希值在旧表长度范围内，则直接放入新表中
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//旧表的长度大于0
if (oldCap > 0) {
//旧表是否达到了最大容量
if (oldCap >= MAXIMUM_CAPACITY) {
//阈值等于Integer的最大值
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果当前 HashMap 的容量小于最大容量，并且当前容量大于等于默认初始容量
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//则将新容量设置为原容量的两倍
newThr = oldThr << 1; // double threshold
}
//如果旧阈值在·大于0，则将新容量设置为旧阈值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { //否则，如果旧阈值为0，则表示使用默认值，将新容量设置为默认初始容量，同时将新阈值设置为默认初始容量乘以默认负载因子。
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新的阈值为0，则根据新的容量和负载因子来计算新的阈值。如果新的容量小于最大容量
//并且新的容量乘以负载因子小于最大容量，则使用新的容量乘以负载因子作为新的阈值。
//否则，新的阈值将被设置为Integer.MAX_VALUE，表示使用最大的阈值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//新表长度创建一个新的哈希表，将旧表中的元素转移到新表中
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//新表长度创建一个新的哈希表，将旧表中的元素转移到新表中
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//如果元素e是一个树节点，则调用其split()方法将其子节点也插入到新哈希表中
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// 将元素e插入到新哈希表中,并保持原有的顺序
//还定义了四个节点变量loHead、loTail、hiHead和hiTail
//用于保存元素e的前驱和后继节点
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
Map源码重点将键值对插入到HashMap
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判断节点数组是否为空，或者是否为零
if ((tab = table) == null || (n = tab.length) == 0)
//进行扩容
n = (tab = resize()).length;
//根据哈希值hash 计算出键在哈希表中的索引 i指针 p指向哈希表中索引为i的位置。
//&是按位与运算符，用于将 n - 1 和 hash 进行按位与运算，得到一个在 0到n - 1范围内的整数
if ((p = tab[i = (n - 1) & hash]) == null)
//为空，则直接将新节点插入
tab[i] = newNode(hash, key, value, null);
else {
//不为空则遍历链表或红黑树
Node<K,V> e; K k;
//查找是否已经存在相同的key，如果存在，则更新对应的value值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)//用于判断p是否是TreeNode类型的实例
//强制转换为TreeNode<K,V>类型，然后调用putTreeVal方法将参数传递给它
//表示将一个键值对插入到树形结构中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//binCount 表示当前链表的长度
for (int binCount = 0; ; ++binCount) {
// 如果当前节点的下一个节点为空，说明当前节点是链表的最后一个节点
//将新节点插入到当前节点的下一个节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果链表长度大于等于该值8，则将链表转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
//- 如果找到了相同的键值对，则不进行插入操作。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//哈希表中某个键值对进行更新操作的代码
if (e != null) {
//哈希表中某个键值对进行更新操作的代码
V oldValue = e.value;
//如果onlyIfAbsent为false或者oldValue为
if (!onlyIfAbsent || oldValue == null)
//则将该键值对的值更新为新值value
e.value = value;
//则将该键值对的值更新为新值value
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
//链表转换为红黑树的方法
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//首先判断数组是否为空或长度是否小于最小树化容量
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();//扩容方法
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {//replacementTreeNode 是一个方法，用于将链表节点转换为红黑树节点
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
//如果数组中该位置已经存在节点
if ((tab[index] = hd) != null)
hd.treeify(tab); 转换为红黑树
}
}