什么是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); 转换为红黑树
}
}
