HashMap
当hashMap的entry数量达到当前容量的负载因子比例，
eg：初始容量为16,当前容量达到12，而负载因子为0.75
就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。因此通常建议能提前预估 HashMap 的大小最好，尽量的减少扩容带来的性能损耗，也能保证hashMap的寻址效率。
探究点：
hash表中确定元素下标原理探究
核心是对象的hashCode，先确定hashCode方法的定义惹：
1, Whenever it is invoked on the same object more than once during
an execution of a Java application, the {@code hashCode} method
must consistently return the same integer.
2, This integer need not remain consistent from one execution of an
application to another execution of the same application.
3, As much as is reasonably practical, the hashCode method defined by
class {@code Object} does return distinct integers for distinct
objects. (This is typically implemented by converting the internal
address of the object into an integer)
实践表明默认的hashCode()函数确实为不同对象生成了独一无二的int值，但这不表明默认hashCode()就保证不同对象的hashcode唯一性。
实践中hashCode普遍用于hashTable相关数据结构，我们更应该注重hashCode和equals的关系——如果equals判定为相同的两个对象，那么hashCode必须要相同；如果equals判断两个对象不一致，那么不要求他们的hashCode一定不同。
int hash = hash(key);
int i = indexFor(hash, table.length);
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
hash方法为将hash值的靠近末尾位尽可能打散——
对key的hashCode进行扰动计算，防止不同hashCode的高位不同但低位相同导致的hash冲突。简单点说，就是为了把高位的特征和低位的特征组合起来，降低哈希冲突的概率，也就是说，尽量做到任何一位的变化都能对最终得到的结果产生影响。
indexFor是保证 table 元素在当前容量范围内分布均匀，将hash生成的整型转换成链表数组中的下标——
将hash结果对当前容量的二进制表示-1进行取模。hashMap中使用位运算(&)来代替取模运算(%)，数值结果是一样的，但位运算(&)效率要比代替取模运算(%)高很多，主要原因是位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。除了性能之外，还有一个好处就是可以很好的解决负数的问题，使得得到的结果全部为正数。
至于为什么hashMap容量必须为2的非负数次方倍，扩容也必须是*2——
长度减一后进行取模运算时保证被取模数尾数都为一，比如长度为16,减一后换成二进制就为1111，能够减少hash碰撞，均匀使用数组空间。
总的来说，保证hash冲突尽量减少是需要两个方法配合使用的。
目前看来，散列碰撞有几种发生情形：
- 不同对象产生了相同的hashCode
- 不同的hashCode产生了相同的散列值
所以判断对象的唯一性一定不能仅仅通过hash值，需要结合equals方法。
Hashmap在使用时候需要保证元素尽可能分布均匀，在散列算法不变的基础上提供一个大容量数组可以尽可能打散元素但是这样浪费空间，元素
参考：
https://blog.csdn.net/j1231230/article/details/78072115
https://www.hollischuang.com/archives/2091
https://www.iteye.com/blog/helloworldfengyun-2053869
负载因子探究
负载因子 = 总键值对数 / 桶个数
负载因子越大，意味着哈希表越满，越容易导致冲突，性能也就越低。因此，一般来说，当负载因子大于某个常数(可能是 1，或者 0.75 等)时，哈希表将自动扩容。
为什么采用0.75作为初始负载因子？
Ideally, under random hashCodes, the frequency of
nodes in bins follows a Poisson distribution
(http://en.wikipedia.org/wiki/Poisson_distribution) with a
parameter of about 0.5 on average for the default resizing
threshold of 0.75, although with a large variance because of
resizing granularity. Ignoring variance, the expected
occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
factorial(k)). The first values are:
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million
注意wiki链接中的关键字：Poisson_distribution
泊淞分布啊
简单翻译一下就是在理想情况下,使用随机哈希码,节点出现的频率在hash桶中遵循泊松分布，同时给出了桶中元素个数和概率的对照表。
从上面的表中可以看到当桶中元素到达8个的时候，概率已经变得非常小，也就是说用0.75作为加载因子，每个碰撞位置的链表长度超过８个是几乎不可能的。
哈希表在自动扩容时，一般会创建两倍于原来个数的箱子，因此即使 key 的哈希值不变，对箱子个数取余的结果也会发生改变，因此所有键值对的存放位置都有可能发生改变，这个过程也称为重哈希(rehash)。
负载因子不能解决hash表性能问题——假设所有 key 的哈希值都一样，那么即使扩容以后他们的位置也不会变化。虽然负载因子会降低，但实际存储在每个箱子中的链表长度并不发生改变，因此也就不能提高哈希表的查询性能。
https://bestswifter.com/hashtable/
JDK1.8中对put操作的改进
在一个桶下当链的长度长于8时就要将其变换成红黑树，这样就能将寻址时间复杂度从O(n)降低到O(logn)。
逻辑流程如下：
多线程操作hashMap为什么会造成死循环
put操作中如果遇到需要resize的情形，就会调用transfer方法将老数据转移到新table中，这个过程没有线程保护，导致新table桶下形成环形链，这样当获取一个不存在的 key 时，计算出的 index 正好是环形链表的下标就会出现死循环。
https://blog.csdn.net/zhuqiuhui/article/details/51849692#commentBox
无论是 1.7 还是 1.8 其实都能看出 JDK 没有对它做任何的同步操作，所以并发会出问题，甚至 1.7 中出现死循环导致系统不可用（1.8 已经修复死循环问题）。
ConcurrentHashMap
？ 为什么要用ConcurrentHashMap，它适合什么场景，有什么优缺点？
实现也分1.7和1.8
先看1.7版本
HashEntry的结构
唯一的区别就是其中的核心数据如 value ，以及链表都是 volatile 修饰的，保证了获取时的可见性。
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
int hash = hash(key);
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
s = ensureSegment(j);
return s.put(key, hash, value, false);
}
首先是通过 key 定位到 Segment，之后在对应的 Segment 中进行具体的 put。
由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的，保证了内存可见性，所以每次获取时都是最新值。
ConcurrentHashMap 的 get 方法是非常高效的，因为整个过程都不需要加锁。
再看1.8版本
Java 7为实现并行访问，引入了Segment这一结构，实现了分段锁，理论上最大并发度与Segment个数相等。Java 8为进一步提高并发性，摒弃了分段锁的方案，而是直接使用一个大的数组，采用了 CAS + synchronized 来保证并发安全性。
同时为了提高哈希碰撞下的寻址性能，Java 8在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为O(N)）转换为红黑树（寻址时间复杂度为O(long(N))）。
对于put操作，如果Key对应的数组元素为null，则通过CAS操作将其设置为当前值。如果Key对应的数组元素（也即链表表头或者树的根元素）不为null，则对该元素使用synchronized关键字申请锁，然后进行操作。如果该put操作使得当前链表长度超过一定阈值，则将该链表转换为树，从而提高寻址效率。
对于读操作，由于数组被volatile关键字修饰，因此不用担心数组的可见性问题。同时每个元素是一个Node实例（Java 7中每个元素是一个HashEntry），它的Key值和hash值都由final修饰，不可变更，无须关心它们被修改后的可见性问题。而其Value及对下一个元素的引用由volatile修饰，可见性也有保障。对于Key对应的数组元素的可见性，由Unsafe的getObjectVolatile方法保证。
CAS 比较和交换
Compare and swap
CAS有3个操作数
内存值V
旧的预期值A
要修改的新值B
当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做
当多个线程尝试使用CAS同时更新同一个变量时，只有其中一个线程能更新变量的值(A和内存值V相同时，将内存值V修改为B)，而其它线程都失败，失败的线程并不会被挂起，而是被告知这次竞争中失败，并可以再次尝试(否则什么都不做)
看了上面的描述应该就很容易理解了，先比较是否相等，如果相等则替换(CAS算法)
参考文章
http://www.jasongj.com/java/concurrenthashmap/
https://zhuanlan.zhihu.com/p/35668936
https://crossoverjie.top/2018/07/23/java-senior/ConcurrentHashMap/
