HashMap 作为最常用的map,我们来看看他有什么特性吧。
1、数据结构
底层是用的是数组加链表的结构（jdk1.8 加入了红黑树的特性）,允许key 为null(hash 为 0),下图为示例
在jdk1.8以后 当桶中的节点数超过8个，桶中的数据就会由单向链表转为红黑树结构。
当删除桶中节点到6个时，会将红黑树转为单向链表。
- 8 这个数字的选择,是因为hash 桶的分布完全符合泊松分布，根据算法一个桶中8个节点的概率已经接近0，所以树化的 概率还是很低的。
- 选择6 转换为单向链表而不是7的原因是当某个树 减少一个 立即选择转换会导致转换过于频换，因为对单一key 添加删除可能频换发生，而两个key操作而hash 桶相同的概率就小的多。
2、数组长度与加载因子
底层的结构是数组加链表的结构，那么数据长度和该如何确定，数组如何扩容？
加载因子是什么，如何确定加载因子的大小
(1)、数组长度的选择
HashMap的长度一定是2的幂次方,在计算key在数组中 index = (n - 1) & hash
根据index的计算公式 若n 不是2的幂次方 ，比如 15(二进制00001111) 减1 = 00001110 与上任意数 都会导致最后一位是0，使得数组中偶数位的桶无法被利用。同理必须要保持n - 1后几位全是1的状态。比如00111111,11111111.这就要求n 必须是2的幂次方，才能使得数组中的桶全部被利用，符合泊松分布的要求。
下面是hashMap 初始化 数组长度的代码
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)、加载因子的选择
所谓的加载因子其实是空间利用率，所以加载因子的范围在 0 ~ 1 之间,如果加载因子小了 比如 map 长度为 16 加载因子为 0.5 那么 当map 中放值8个数据的时候，map就需要开始扩容。加载因子选择过小会导致空间利用率过低，但是降低了hash冲突的概率，提高了查询效率。加载因子选择过大 能够提供空间利用率，却提高了hash冲突的概率。
总结：加载因子是空间与时间的折中，合理的加载因子是让二者保持平衡。hashMap的默认加载因子是0.75. 看看官网说明
* 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
意思是桶的分布式符合泊松分布定理的，当加载因子为0.75的时候，并且列出桶中数据的概率
3、树化（红黑树）
和红黑树数据结构一直，之后再写红黑树的java示例。
