ArrayList

ArrayList无参构造的初始容量为0

ArrayList有参构造的初始容量根据所给的长度进行创建（如果是集合，就根据集合的大小进行创建）

调用add方法触发扩容

当往ArrayList添加元素的时候。触发第一次扩容，创建一个长度为10的新数组，然后将元素添加进新数组里面，再用新的数组替换掉旧的空数组。

当数组内元素为10时，进行第二次扩容，扩容为第一次容量的1.5倍，即15（以后每一次扩容都是上一次的1.5倍）

注意：此处的1.5倍其实是上一次容量二进制右移一位，再加上它本身，如第三次扩容：15右移一位是7，7+15为22

调用addAll方法触发扩容

在下一次扩容的容量跟实际的元素个数之间选择一个较大值

如：添加元素个数为16个，那么数组容量将会扩容到22

0 10 15 22 33 49 73 109

Iterator

Fail-Fast策略

在通过迭代器遍历的同时如果有人对集合进行修改，那么就抛出异常

ArrayList的迭代器采用了Fail-Fast策略

源码分析

增强for循环在首次调用内部会生成一个迭代器，在执行过程中，expectedModCount作为迭代器的成员变量，记录了迭代器刚开始迭代时的修改次数。modCount作为list的成员变量，记录list修改次数，该数会记录在expectedModCount里

接下来调用hasNext方法和next方法，调用next方法之前会进行一次校验（checkForComodification方法）

当在迭代的过程中，对集合进行了修改，此时expectedModCount的值就会变换，导致二者不等，那么就会直接抛出异常

Fail-Save策略

在通过迭代器遍历的同时如果有人对集合进行修改，可以采取应对策略而不是抛出异常，如牺牲一致性来让整个遍历正常完成

CopyOnWriteArrayList采用了Fail-Save策略

源码分析

在迭代器内部会首先创建一个数组，将要遍历的数组复制过去，然后遍历该数组

当我们在迭代的过程中调用add方法添加新元素的时候，实际上在add方法的内部是先将原来的数组复制一份，然后让长度加一，而新添加的元素加到了新的数组的最后一位，所以遍历的时候使用的是旧数组，而添加元素的时候使用的是新数组，二者互不干扰

LinkedList与ArrayList的比较

LinkedList

基于双向链表，无需连续内存

随机访问慢（要沿着链表遍历）

头尾插入删除性能高

占用内存多

ArrayList

基于数组，需要连续内存

随机访问快（指根据下标访问）

尾部插入、删除性能可以，其它部分插入、删除都会移动数据，因此性能会低

可以利用 cpu 缓存，局部性原理

随机访问速度

ArrayList内部实现了RandomAccess接口（LinkedList没有），该接口是一个标识接口，如果实现了该接口，那么当获取其中某个元素时就直接根据下标get就行。如果没有实现该接口，那么只能通过迭代器的next方法获取下一个元素

增删速度

LinkedList：头尾插入删除性能高

ArrayList：尾部插入、删除性能可以，其它部分插入、删除都会移动数据，因此性能会低

局部性

cpu读取数据是按照缓存行读取到缓存的，就是cpu会把需要的数据加载到缓存中，查找数据时，会先从缓存找，找不到再到内存中去找。

数组作为连续内存，而cpu缓存会把一片连续的内存空间读入，这样连续内存的数组更容易整块读取到缓存中，当进行遍历时，直接命中缓存。

链表是跳跃式的地址，很轻易就会跳出缓存，跑到内存中去查找数据。所以会慢很多

HashMap

1.7 数组+链表

1.8 数组+（链表/红黑树）

原理

在实例化之后，底层创建了一个长度是16的一维数组Entry[] table，在进行put操作时，先获得key的hashCode，通过hash()散列算法得到hash值，进而定位到数组的位置

如果该位置上为空，此时添加成功

如果该位置上不为空，意味着此位置上存在一个或多个数据（以链表的形式存在），此时比较该元素与其他元素的hash值（调用equals方法），当返回false时添加成功，返回true时使用新的value替换掉旧的value

扩容

capacity 容量，默认16。

loadFactor 加载因子，默认是0.75

threshold 阈值。阈值=容量*加载因子。默认12。当元素数量超过阈值时便会触发扩容。

二次哈希的意义

下面是HashMap根据二次Hash计算出的哈希码，计算键值对下标的代码，length是底层数组的长度。HashMap采用了位运算，而非常见的取模运算

1
2
3

static int indexFor(int h, int length) {
    return h & (length-1);
}

当不进行二次hash的时候，假设数组长度为16，当哈希码为5时，下标Index结果是5

 00000000000000000000000000000101
&00000000000000000000000000001111
=00000000000000000000000000000101
=5

当哈希码为65541时，下标Index结果依然是5，不同的哈希码算出相同的下标，出现了哈希碰撞

 00000000000000010000000000000101
&00000000000000000000000000001111
=00000000000000000000000000001101
=5

通过例子可以发现哈希码的高位压根就没有参与运算，全部被丢弃了

不管哈希码的高位是多少，都不会影响最终Index的计算结果，因为只有低位才参与了运算，这样的哈希函数是不好的，它会带来更多的冲突，影响HashMap的效率。

HashMap为了解决这个问题，将哈希码的高16位与低16位进行异或运算，得到一个新的哈希码，这样就可以让高位也参与到运算，这个函数也被称为扰动函数

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

总结：HashMap通过二次哈希，引入扰动函数，拿高16位和低16位做异或运算，把高位的特征和地位的特征组合起来，以此来降低哈希碰撞的概率

注意：二次 hash 是为了配合 容量是 2 的 n 次幂 这一设计前提，如果 hash 表的容量不是 2 的 n 次幂，则不必二次 hash，容量是 2 的 n 次幂 这一设计计算索引效率更好，但 hash 的分散性就不好，需要二次 hash 来作为补偿，没有采用这一设计的典型例子是 Hashtable

数组容量为何是2的n次幂

1、当数组容量是2的n次幂时，计算索引时可以用按位与运算代替求模运算，提高运算性能

2、扩容时使用hash & oldCap == 0的元素留在原来位置，否则新位置 = 旧位置 + oldCap

3、可以尽量避免hash冲突的发生

从HashMap的源码中可以看到HashMap在扩容时选择了位运算，向集合中添加元素时，会使用(n - 1) & hash的计算方法来得出该元素在集合中的位置。

hash表初始数组长度是16进行一次扩容数组长度就会变成32，他们的二进制分别是10000和100000。

(n-1)&hash中n就是hash表原来的长度，n-1就会使二进制发生如下的变化：

1 2	16 10000 -> 15 01111 32 100000 -> 31 011111

(n-1)&hash，接下来就会与被插入的对象hash进行按位与运算，看下面几个例子：

1 2	01111 & 01001 = 01001 01111 & 01101 = 01101

如果数组扩容不是按2的n次幂来运算，那么就会有hash冲突的情况出现。比如数组长度16进行一次扩容以后变成了25（二进制11001），与带插入新元素进行&运算时就会出现hash冲突，如下：

1 2	11001 & 10111 = 10001 11001 & 10011 = 10001

树化与退化

树化规则

当链表长度超过树化阈值 8 时，先尝试扩容来减少链表长度，如果数组容量已经 >=64，才会进行树化

树化意义

红黑树用来避免 DoS 攻击，防止链表超长时性能下降，树化应当是偶然情况，是保底策略

hash 表的查找，更新的时间复杂度是 *O(1)*，而红黑树的查找，更新的时间复杂度是 *O(log_2⁡n )*，TreeNode 占用空间也比普通 Node 的大，如非必要，尽量还是使用链表

hash 值如果足够随机，则在 hash 表内按泊松分布，在负载因子 0.75 的情况下，长度超过 8 的链表出现概率是 0.00000006，树化阈值选择 8 就是为了让树化几率足够小

退化规则

情况1：在扩容时如果拆分树时，树元素个数 <= 6 则会退化链表

情况2：remove 树节点时，若 root、root.left、root.right、root.left.left 有一个为 null ，也会退化为链表（在移除之前进行检查）

put方法流程总结

HashMap 是懒惰创建数组的，首次使用才创建数组

计算索引（桶下标）

如果桶下标还没人占用，创建 Node 占位返回

如果桶下标已经有人占用

已经是 TreeNode 走红黑树的添加或更新逻辑
是普通 Node，走链表的添加或更新逻辑，如果链表长度超过树化阈值，走树化逻辑

返回前检查容量是否超过阈值，一旦超过进行扩容

注意：

链表插入节点，1.7是头插法，1.8是尾插法

1.7是大于等于阈值且没有空位时才进行扩容，1.8是大于阈值就扩容

1.8在扩容计算Node时会进行优化

加载因子为何默认为0.75F

加载因子就是表示Hash表中元素的填满程度（加载因子 = 填入表中的元素个数 / 散列表的长度）

0.75F 在空间占用与查询时间之间取得较好的权衡

大于这个值，填满的元素变多，空间利用率变高，发生冲突的机会变大

小于这个值，填满的元素变少，冲突发生的机会减小，但空间浪费更多，而且还会提高扩容rehash操作的次数

key 的设计

HashMap 的 key 可以为 null，但其他 Map 不一定

key 的 hashCode 应该有良好的散列性

作为 key 的对象，必须实现 hashCode 和 equals，并且 key 的内容不能修改（不可变）点我查看

注意：如果 key 可变，例如修改了 age 会导致再次查询时查询不到

String中hashCode() 的设计

value：是一个 private final 修饰的 char 数组，String 类是通过该数组来存在字符串的

hash：是一个 private 修饰的 int 变量，用来存放 String 对象的 hashCode

h = 31 * h + val[i];：目标是达到较为均匀的散列效果，每个字符串的 hashCode 足够独特，31 代入公式有较好的散列特性，并且 31 * h 可以被优化为，缩短计算时间

1
2
3

1、32 ∗h -h
2、2^5  ∗h -*
3、h≪5  -h

代码如下

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}