map是用于存储键值对(<key, value>)的集合类，也就是是一组键值对的映射（数学概念）。在java中map是一个接口，是和collection接口同一等级的集合根接口。
一、初始参数
//HashMap的默认初始长度16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//HashMap的最大长度2的30次幂
static final int MAXIMUM_CAPACITY = 1 << 30;
//HashMap的默认加载因子0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//HashMap链表升级成红黑树的临界值
static final int TREEIFY_THRESHOLD = 8;
//HashMap红黑树退化成链表的临界值
static final int UNTREEIFY_THRESHOLD = 6;
//HashMap链表升级成红黑树第二个条件：HashMap数组(桶)的长度大于等于64
static final int MIN_TREEIFY_CAPACITY = 64;
//HashMap底层Node桶的数组
transient Node<K,V>[] table;
//扩容阈值，当你的hashmap中的元素个数超过这个阈值，便会发生扩容
//threshold = capacity * loadFactor
int threshold;二、数据结构
HashMap底层是由数组（Node<K, V>[] table）+ 链表 + 红黑树 组成。
由hash(Object key)计算key的哈希值，通过计算出的哈希值存储到对应到相应的数组中。
三、新增机制
（1）判断数组是否为空或长度为0，做扩容处理
（2）计算hash值，插入对应的数组索引中，如果对应数组索引为null，则直接创建node节点，反之依次判断：
1）当前节点和hash和key与插入的key相同，则直接替换value值
2）当前节点为树形结构TreeNode，直接使用putTreeVal函数插入
3）当前节点为链表，依次循环判断，每个节点是否和插入的key相同，相同则替换
特殊情况下，链表节点大于7（阈值8）的时候对链表升级为红黑树，便于插入查询。
public V put(K key, V value) {
// 调用puVal方法，添加元素
return this.putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node[] tab;
int n;
// 如果桶数组为空，则进行扩容操作
if ((tab = this.table) == null || (n = tab.length) == 0) {
n = (tab = this.resize()).length;
}
Object p;
int i;
// 计算hash值，判断桶数组中该位置的元素是否为空， 如果为空直接插入新增插入node节点
if ((p = tab[i = n - 1 & hash]) == null) {
tab[i] = this.newNode(hash, key, value, (Node)null);
} else {
Object e;
Object k;
// 判断当前节点的key是否和插入的key一致， 如果一致则直接替换
if (((Node)p).hash == hash && ((k = ((Node)p).key) == key || key != null && key.equals(k))) {
e = p;
}
// 判断当前节点是否是树节点，如果是树节点则调用putTreeVal方法插入节点
else if (p instanceof TreeNode) {
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
}
// 否则则遍历链表，判断key是否一致，一致则替换，不一致则插入
else {
int binCount = 0;
while(true) {
if ((e = ((Node)p).next) == null) {
((Node)p).next = this.newNode(hash, key, value, (Node)null);
// 链表节点长度大于7则进化为红黑树
if (binCount >= 7) {
this.treeifyBin(tab, hash);
}
break;
}
if (((Node)e).hash == hash && ((k = ((Node)e).key) == key || key != null && key.equals(k))) {
break;
}
p = e;
++binCount;
}
}
// 判断e是否为空，不为空则返回旧值
if (e != null) {
V oldValue = ((Node)e).value;
if (!onlyIfAbsent || oldValue == null) {
((Node)e).value = value;
}
// 调用afterNodeAccess方法，将节点移动到链表尾部
this.afterNodeAccess((Node)e);
return oldValue;
}
}
++this.modCount;
// 判断是否扩容
if (++this.size > this.threshold) {
this.resize();
}
this.afterNodeInsertion(evict);
return null;
}
四、扩容机制
当插入数量大于阈值时（数组长度 * 负载因子）
table容量变为两倍（size << 1）,重新计算每个key的hash值进行插入
五、复杂度
平均情况下插入、查找、删除时间复杂度为O(1)
最糟糕情况下插入、查找、删除时间复杂度为O(n)或者O(logn)
原因：由于不同的key可能有相同的哈希值，导致都插入到同一个数组索引上，使链表（红黑树）个数为n，插入、查找、删除效率降低。
六、链表和红黑树互转流程（面试突击截取）
（1）链表升级为红黑树
在 JDK 1.8 之后，HashMap 默认是先使用数组 + 链表存储数据，但当满足以下两个条件时：
- 链表的数量大于阈值（默认是 8）
- 并且数组长度大于 64 时
为了（查询）的性能考虑会将链表升级为红黑树进行存储，具体执行流程如下：
- 创建新的红黑树对象，并将链表内所有的键值对全部添加到红黑树中。
- 将原来的链表引用指向新创建的红黑树。
（2）红黑树退化为链表
当进行了删除操作，导致红黑树的节点小于等于 6 时，会发生退化，将红黑树转换为链表。这是因为当节点数量较少时，红黑树对性能的提升并不明显，反而占用了更多的内存空间。具体执行流程如下：
- 从红黑树的根节点开始，按照中序遍历的顺序将所有节点加入到一个新的链表中。
- 将原来的红黑树引用指向新创建的链表。
No responses yet