HashMap 简介
JDK1.8 后的 HashMap 在底层数据结构上采纳数组 + 链表 / 红黑树，通过散列映射来存储键值对数据，因为在查问上应用散列码 hashcode，所以在查问上的访问速度较快。HashMap 能够存储值为 null 的键（key）和值（value），然而 null 作为键只能有一个，而 null 作为值能够有多个。它是无序的、非线程平安的。
HashMap 底层数据结构
在 JDK1.7 及之前的 HashMap 底层是由数组 + 链表形成，也就是链表散列。其中，数组是 HashMap 的主体，链表则是次要为了解决哈希抵触而存在的。
JDK1.8 当前的 HashMap 在解决哈希抵触时有了较大的变动，当链表长度大于阈值（默认为 8）（将链表转换为红黑树之前会判断，如果以后数组的长度小于 64，那么会抉择先进行数组扩容，而不是间接转换为红黑树）时，将链表转化为红黑树，以缩小搜寻工夫。
HashMap 底层实现
通过 key 的 hashcode 通过扰动函数解决后失去 hash 值，而后通过(n-1) & hash 判断以后元素寄存的地位（这里的 n 指的是数组的长度），如果以后地位存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否雷同，如果雷同的话，间接笼罩；不雷同就通过拉链法解决抵触。
扰动函数：hashmap 的 hash 办法，应用 hash 办法即扰动函数为了避免一些实现比拟差的 hashcode()办法，换句话说扰动函数能够缩小碰撞。
拉链法：将链表和数组相结合。即创立一个链表数组，数组中每一格就是一个链表。若遇到哈希抵触，则将抵触的值加到链表中即可。
HashMap 的长度为什么是 2 的幂次方
hash 值的取值范畴是 2147483648 到 2147483647，大略有 40 亿的映射空间，只有 hash 函数映射的比拟平均涣散，个别很难呈现碰撞。然而一个长度为 40 亿的数组，内存是放不下的。因而这个散列值不能间接拿来用，须要先对数组的长度进行取模运算，失去的余数用来作为寄存的地位也就是对应的数组下标。这个取模运算计算方法是“(n-1)&hash”（n 代表数组长度）。
这个时候有人要问：取模操作不是 % 吗？
起因：采纳二进制位操作 &，绝对于 % 可能进步运算效率。因而，取余（%）操作中如果除数是 2 的幂次则等价于与其除数减一的与（&）操作，也就是说，hash%length==hash&(length-1)，而这个等式成立的前提是 length 是 2 的 n 次方。
HashMap 的扩容机制
要理解 HashMap 的扩容过程，首先须要理解 HashMap 中的变量
Node<K,V>：链表节点，蕴含了 key，value，hash 值，next 指针四个元素；table：Node<K,V> 类型的数组，外面的元素是链表，用来寄存 HashMap 元素的实体；size：示意以后 HashMap 蕴含的键值对数量
final float loadFactor：负载因子，用于扩容
int threshold：扩容的阈值，决定了 HashMap 何时扩容，以及扩容后的大小，个别等于 table * loadFactor
static final float DEFAULT_LOAD_FACTORY = 0.75f：默认的负载因子
static final int DEFAULT_INITIAL_CAPACITY = 1<<4：默认的 table 初始容量（16）static final int TREEIFY_THRESHOLD = 8：链表长度大于该参数转红黑树
statci final int UNTREEIFY_THRESHOLD = 6：当树的节点数小于等于该参数转成链表
何时进行扩容？
当以后存入的数据容量大于阈值 threshold 时须要进行 resize 扩容。而 threshold 取决于两个因素：以后长度容量 capacity 以及负载因子 loadFactory。
threshold = capacity * loadFactory
HashMap 扩容能够分为三种状况
第一种：应用默认构造方法初始化 HashMap。HashMap 在一开始初始化的时候会返回一个空的 table，并且 threshold 为 0。因而第一次扩容的容量为默认值 DEFAULT_INITIAL_CAPACITY = 1<<4，因而 threshold = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12。
第二种：指定初始容量的办法结构 HashMap。初始容量等于 threshold，接着 threshold = 以后的容量（threshold）* DEFAULT_LOAD_FACTOR。
第三种：HashMap 不是第一次扩容。如果 HashMap 曾经扩容过的话，那么每次 table 的容量以及 threshold 量为原有的两倍。
上面是 HashMap 扩容机制外围办法 Node<K,V>[] resize()的源码
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;// 首次初始化后的 table 为 null
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;// 默认结构器下的阈值为 0
int newCap, newThr = 0;
if (oldCap > 0) { //table 扩容过
// 以后 table 容量大于最大值的时候返回以后 table
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//table 的容量乘以 2，threshold 的值也乘以 2
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// 应用带有初始容量的结构器时，table 容量为初始化失去的 threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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)
// 以后 index 没有产生 hash 抵触，间接对 2 取模，即移位运算 hash & (2^n-1)
// 扩容都是依照 2 的幂次方进行扩容，因而 newCap = 2^n
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 以后 index 对应的节点为红黑树，当树的个数小于等于 UNTREEIFY_THRESHOLD 则转成链表
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
把以后 index 对应的链表分成两个链表，缩小扩容的迁徙量
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;
// 扩容长度为以后 index 地位 + 旧的容量
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
}
HashMap 与 HashSet、HashTable 的区别
HashMap 和 HashSet
HashSet 底层是基于 HashMap 实现的，且都是非线程平安的
HashMap 和 HashTable
ConcurrentHashMap
JDK1.7
由 Segment 数组 +HashEntry 数组 + 链表实现：
ConcurrentHashMap 分段锁对整个桶数组进行了宰割分段（segment），每一把锁只锁容器的其中一部分数据，多线程拜访容器里不同数据段的数据，就不会存在锁竞争，进步并发访问率。
JDK1.8
到了 JDK1.8 的时候曾经摒弃了 segment 的概念，而是间接用 Node 数组 + 链表 + 红黑树实现。同时采纳 CAS 和 synchronized 来保障并发平安，整个看起来就像是优化且线程平安的 HashMap。
synchronized 只锁定以后链表或红黑二叉树的首节点，这样只有 hash 不抵触，就不会产生并发，效率又晋升 N 倍。
汇合框架底层数据结构总结
那么如何选用汇合呢？
次要依据汇合的特点来选用，比方咱们须要依据键值获取到元素值时就选用 Map 接口下的汇合，须要排序时抉择 TreeMap，不须要排序时就抉择 HashMap，须要保障线程平安就选用 ConcurrentHashMap。
当咱们只须要寄存元素值时，就抉择实现 Collection 接口的汇合，须要保障元素惟一时抉择实现 Set 接比的汇合比方 TreeSet 或 HashSet，不须要就抉择实现 List 接口的比方 ArrayList 或 LinkedList，而后再依据实现这些接口的汇合的特点来选用。
最初
在文章的最初作者为大家整顿了很多材料！包含 java 外围知识点 + 全套架构师学习材料和视频 + 一线大厂面试宝典 + 面试简历模板 + 阿里美团网易腾讯小米爱奇艺快手哔哩哔哩面试题 +Spring 源码合集 +Java 架构实战电子书等等！有须要的敌人能够关注 公众号：前程有光回复材料主动下载