HashMap扩容
数组容量是有限的，数据多次插入的，到达一定的数量就会进行扩容，也就是resize。
初始容量
16
为什么16？
16只是因为作者认为16这个初始容量是能符合常用而已。
Hashmap中的链表大小超过八个时会自动转化为红黑树，当删除小于六时重新变为链表，为啥呢？
根据泊松分布，在负载因子默认为0.75的时候，单个hash槽内元素个数为8的概率小于百万分之一。
所以将7作为一个分水岭，等于7的时候不转换，大于等于8的时候才进行转换，小于等于6的时候就化为链表。
何时扩容
扩容触发的两个因素：
-
Capacity：HashMap当前长度。
-
LoadFactor：负载因子，默认值0.75f。
如何扩容
长度扩大以后，Hash的规则也随之改变。
index = HashCode（Key） & （Length - 1）
链表的插入
Java 8 之前使用头插法，因为新插入的元素用到的可能性更大一些
Java 8 开始改为尾插法，原因与多线程有关
头插法造成的环形链表
举个例子，现在往一个容量大小为2的put两个值，负载因子是0.75是不是我们在put第二个的时候就会进行resize？
2*0.75 = 1 所以插入第二个就要resize了
现在我们要在容量为2的容器里面用不同线程插入A，B，C，假如我们在resize之前打个短点，那意味着数据都插入了但是还没resize那扩容前可能是这样的。
我们可以看到链表的指向A->B->C
Tip：A的下一个指针是指向B的
因为resize的赋值方式，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置
在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。
就可能出现下面的情况，大家发现问题没有？
B的下一个指针指向了A
因此可能会出现上面的环形链表
尾插法的实现
因为java8之后链表有红黑树的部分。
红黑树的引入巧妙的将原本O(n)的时间复杂度降低到了O(logn)。
使用头插会改变链表的上的顺序，但是如果使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。
就是说原本是A->B，在扩容后那个链表还是A->B
Java7在多线程操作HashMap时可能引起死循环，原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系。
Java8在同样的前提下并不会引起死循环，原因是扩容转移后前后链表顺序不变，保持之前节点的引用关系。
然而Java 8的 HashMap 依然不是线程安全的
put/get方法都没有加同步锁，多线程情况最容易出现的就是：无法保证上一秒put的值，下一秒get的时候还是原值，所以线程安全还是无法保证。
Index运算
Node数组的默认初始化大小 -> 1 « 4 -> 16
我们在创建HashMap的时候，阿里巴巴规范插件会提醒我们最好赋初值，而且最好是2的幂。
这样是为了位运算的方便，位与运算比算数计算的效率高了很多，之所以选择16，是为了服务将Key映射到index的算法。
我前面说了所有的key我们都会拿到他的hash，但是我们怎么尽可能的得到一个均匀分布的hash呢？
通过Key的HashCode值去做位运算。
再根据 ` index = HashCode（Key） & （Length- 1）`
15的的二进制是1111，那10111011000010110100 &1111 十进制就是4
之所以用位与运算效果与取模一样，性能也提高了不少！
在使用不是2的幂的数字的时候，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。
只要输入的HashCode本身分布均匀，index的结果就是均匀的。
HashCode() 重写
equals()方法和hashCode()方法分别是用来做什么的？
equals()方法
该方法是用来判断两个对象是否是同一个对象。
在Object类源码（如下所示）中，其底层是使用了“==”来实现
也就是说通过比较两个对象的内存地址是否相同判断是否是同一个对象。
public boolean equals(Object obj) {
return (this == obj);
}
但是在实际应用中，该方法不能满足的我们的需求。
因为我们认为两个对象即使不是指向的同一块内存，只要这两个对象的各个字段属性值都相同，那么就认为这两个对象是同一个对象。
所以就需要重写equals（）方法，即如果两个对象指向内存地址相同或者两个对象各个字段值相同，那么就是同一个对象。
hashCode()方法
一提到hashcode，很自然就想到哈希表。
将某一key值映射到表中的一个位置，从而达到以O(1)的时间复杂度来查询该key值。
Object类源码（如下所示）中，hashCode()是一个native方法，哈希值的计算利用的是内存地址。
public native int hashCode();
可以认为利用哈希表也能起到一定的判重的作用，但是现实是可能存在哈希冲突，即使是两个不同的对象，他们的哈希值也可能相同。
总之，记住哈希表具有优越的查询性能，并且存在哈希冲突。
equals()方法和hashCode()方法两者有什么关系
两者事实关系如下：
-
如果两个对象相同（即用equals比较返回true），那么它们的hashCode值一定要相同！！！！；
-
如果两个对象不同（即用equals比较返回false），那么它们的hashCode值可能相同也可能不同；
-
如果两个对象的hashCode相同（存在哈希冲突），那么它们可能相同也可能不同(即equals比较可能是false也可能是true)
-
如果两个对象的hashCode不同，那么他们肯定不同(即用equals比较返回false)
为什么重写equals()就一定要重写hashCode()方法
对于对象集合的判重，如果一个集合含有10000个对象实例，仅仅使用equals()方法的话
那么对于一个对象判重就需要比较10000次，随着集合规模的增大，时间开销是很大的。
但是同时使用哈希表的话，就能快速定位到对象的大概存储位置，并且在定位到大概存储位置
后续比较过程中，如果两个对象的hashCode不相同，也不再需要调用equals（）方法，从而大大减少了equals()比较次数。
所以从程序实现原理上来讲的话，既需要equals()方法，也需要hashCode()方法。
那么既然重写了equals（），那么也要重写hashCode()方法，以保证两者之间的配合关系。
基于以上分析，我们可以在Java集合框架中得到验证。
由于HashSet是基于HashMap来实现的，所以这里只看HashMap的put方法即可。源码如下
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
//这里通过哈希值定位到对象的大概存储位置
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//if语句中，先比较hashcode，再调用equals()比较
//由于“&&”具有短路的功能，只要hashcode不同，也无需再调用equals方法
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
我们在实际应用过程中，如果仅仅重写了equals（），而没有重写hashCode()方法，会出现什么情况？
字段属性值完全相同的两个对象因为hashCode不同，所以在hashmap中的table数组的下标不同，从而这两个对象就会同时存在于集合中
所以重写equals()就一定要重写hashCode()方法。
对于“为什么重写equals()就一定要重写hashCode()方法？”
这个问题应该是有个前提，就是你需要用到HashMap,HashSet等Java集合。
用不到哈希表的话，其实仅仅重写equals()方法也可以吧。
而工作中的场景是常常用到Java集合，所以Java官方建议重写equals()就一定要重写hashCode()方法。
多线程下的Map
Collections.synchronizedMap
Collections.synchronizedMap(new HashMap<>(16));
在SynchronizedMap内部维护了一个普通对象Map，还有排斥锁mutex
我们在调用这个方法的时候就需要传入一个Map，可以看到有两个构造器，如果你传入了mutex参数，则将对象排斥锁赋值为传入的对象。
如果没有，则将对象排斥锁赋值为this，即调用synchronizedMap的对象，就是上面的Map。
创建出synchronizedMap之后，再操作map的时候，就会对方法上锁，如图全是🔐
Hashtable
与HashMap的区别
1.Hashtable 是不允许键或值为 null 的，HashMap 的键值则都可以为 null。
因为Hashtable在我们 put 空值的时候会直接抛空指针异常，但是HashMap却做了特殊处理。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这是因为Hashtable使用的是安全失败机制（fail-safe），这种机制会使你此次读到的数据不一定是最新的数据。
如果你使用null值，就会使得其无法判断对应的key是不存在还是为空，因为你无法再调用一次contain(key）来对key是否存在进行判断，ConcurrentHashMap同理。
2.实现方式不同：Hashtable 继承了 Dictionary类，而 HashMap 继承的是 AbstractMap 类。
3.初始化容量不同：HashMap 的初始容量为：16，Hashtable 初始容量为：11，两者的负载因子默认都是：0.75。
4.扩容机制不同：当现有容量大于总容量 * 负载因子时，HashMap 扩容规则为当前容量翻倍，Hashtable 扩容规则为当前容量翻倍 + 1。
5.迭代器不同：HashMap 中的 Iterator 迭代器是 fail-fast 的，而 Hashtable 的 Enumerator 不是 fail-fast 的。
当其他线程改变了HashMap 的结构，如：增加、删除元素，将会抛出ConcurrentModificationException 异常，而 Hashtable 则不会。
Fail-Fast
快速失败（fail—fast）是java集合中的一种机制
在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。
迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。
集合在被遍历期间如果内容发生变化，就会改变modCount的值。
每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。
java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改）算是一种安全机制吧。
Fail-Safe
采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。
由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，故不会抛 ConcurrentModificationException 异常
ConcurrentHashMap @1.7
ConcurrentHashMap 由 Segment 数组、HashEntry 组成，和 HashMap 一样，仍然是数组加链表。
static final class Segment<K,V> extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
// 和 HashMap 中的 HashEntry 作用一样，真正存放数据的桶
transient volatile HashEntry<K,V>[] table;
transient int count;
// 记得快速失败（fail—fast）么？
transient int modCount;
// 大小
transient int threshold;
// 负载因子
final float loadFactor;
}
HashEntry跟HashMap差不多的，但是不同点是，他使用volatile去修饰了他的数据Value还有下一个节点next。
并发度高的原因
原理上来说，ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。
不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。
每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。
就是说如果容量大小是16他的并发度就是16，可以同时允许16个线程操作16个Segment而且还是线程安全的。
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();//这就是为啥他不可以put null值的原因
int hash = hash(key);
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject
(segments, (j << SSHIFT) + SBASE)) == null)
s = ensureSegment(j);
return s.put(key, hash, value, false);
}
他先定位到Segment，然后再进行put操作。
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
// 将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {
if (e != null) {
K k;
// 遍历该 HashEntry，如果不为空则判断传入的 key 和当前遍历的 key 是否相等，相等则覆盖旧的 value。
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else {
// 不为空则需要新建一个 HashEntry 并加入到 Segment 中，同时会先判断是否需要扩容。
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
//释放锁
unlock();
}
return oldValue;
}
首先第一步的时候会尝试获取锁，如果获取失败肯定就有其他线程存在竞争，则利用 scanAndLockForPut() 自旋获取锁。
尝试自旋获取锁。
如果重试的次数达到了 MAX_SCAN_RETRIES 则改为阻塞锁获取，保证能获取成功。
get 逻辑比较简单，只需要将 Key 通过 Hash 之后定位到具体的 Segment ，再通过一次 Hash 定位到具体的元素上。
由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的，保证了内存可见性，所以每次获取时都是最新值。
ConcurrentHashMap 的 get 方法是非常高效的，因为整个过程都不需要加锁。
ConcurrentHashMap @1.8
1.8中抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性。
跟HashMap很像，也把之前的HashEntry改成了Node，但是作用不变
把值和next采用了volatile去修饰，保证了可见性，并且也引入了红黑树，在链表大于一定值的时候会转换（默认是8）。
PUT
ConcurrentHashMap在进行put操作的还是比较复杂的，大致可以分为以下步骤：
-
根据 key 计算出 hashcode 。
-
判断是否需要进行初始化。
-
即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
-
如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
-
如果都不满足，则利用 synchronized 锁写入数据。
-
如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。
synchronized性能改进
synchronized之前一直都是重量级的锁，但是后来java官方是对他进行过升级的，他现在采用的是锁升级的方式去做的。
针对 synchronized 获取锁的方式，JVM 使用了锁升级的优化方式，就是先使用偏向锁优先同一线程然后再次获取锁
如果失败，就升级为 CAS 轻量级锁，如果失败就会短暂自旋，防止线程被系统挂起。最后如果以上都失败就升级为重量级锁。
所以是一步步升级上去的，最初也是通过很多轻量级的方式锁定的。