2、HashMap

HashMap 作为最常用的map,我们来看看他有什么特性吧。

1、数据结构

底层是用的是数组加链表的结构（jdk1.8 加入了红黑树的特性）,允许key 为null(hash 为 0),下图为示例

image.png

在jdk1.8以后 当桶中的节点数超过8个，桶中的数据就会由单向链表转为红黑树结构。
当删除桶中节点到6个时，会将红黑树转为单向链表。

1. 8 这个数字的选择,是因为hash 桶的分布完全符合泊松分布，根据算法一个桶中8个节点的概率已经接近0，所以树化的 概率还是很低的。
2. 选择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示例。