Java源码解析(一)

一、关键字

volatile 可见的

在多线程场景下，由该关键字修饰的共享变量被某一个线程修改后就会通知到其他线程，避免其他线程依旧从自己的私有空间拿已经过期的变量的缓存值。

transient 无需序列化

该关键字修饰的变量不会被序列化，比如toString()就不会将该变量加入进来

default 默认实现

一般用在接口之中修饰方法，可以在接口种写出该方法的默认实现，实现类就无需强制实现该方法

native 引用外部实现

被该关键字修饰的方法，说明该方法是使用其他语言实现的，大部分情况是C语言，会有相应的dll文件库供调用

二、集合

1.ArrayList

底层是数组，对于查询匹配的速度很快，删除的速度较慢

• 允许 put null 值，会自动扩容；
• size、isEmpty、get、set、add 等方法时间复杂度都是 O (1)；
• 是非线程安全的，多线程情况下，一般使用CopyOnWriteArrayList或者推荐使用线程安全类：Collections.synchronizedList；
• 增强 for 循环，或者使用迭代器迭代过程中，如果数组被改变（modCount变化），会快速失败，抛出异常。
• 扩容，每次扩大1.5倍，且默认初始容量为10，如果扩容一次则为15，最大不超过int型最大值。在拷贝时，最好先指定好目标集合的容量，拒绝for循环逐个add，这样会一直扩容影响性能。在一个addAll()执行时，如果自动扩容一次仍然不够，则直接扩容到目标大小。
• 删除，删除一个元素后，还要将后面的元素整体向前移动一位，用的是数组拷贝。所以在批量删除不要for+remove，而是采用removeAll(list)来进行删除

2.LinkedList

底层是双向链表，新增删除的速度很快，查询的速度较慢

• 链表每个节点我们叫做 Node，Node 有 prev 属性，代表前一个节点的位置，next 属性，代表后一个节点的位置；
• first 是双向链表的头节点，它的前一个节点是 null。
• last 是双向链表的尾节点，它的后一个节点是 null；
• 当链表中没有数据时，first 和 last 是同一个节点，前后指向都是 null；
• 因为是个双向链表，只要机器内存足够强大，是没有大小限制的。
• 在节点查询时，会根据index的大小来决定从前面开始还是从后面开始查
• 迭代器不是普通的，而是双向的ListIterator，除了hasNext()和next()外，还有hasPrevious()和previous()

3.HashMap

底层是：java7里数组+链表，java8里是数组+(链表/红黑树)
链表长度超过8且数组大小超过64，链表自动变化为红黑树，当红黑树大小小于6时就又变回链表

• 允许 null 值，不同于 HashTable ，是线程不安全的；
• load factor（影响因子） 默认值是 0.75， 是均衡了时间和空间损耗算出来的值，较高的值
  会减少空间开销（扩容减少，数组大小增长速度变慢），但增加了查找成本（hash 冲突增
  加，链表长度变长），不扩容的条件：数组容量*loadfactor > 需要的数组大小；
• 如果有很多数据需要储存到HashMap中，建议 HashMap 的容量一开始就设置成足够的大小，这样可以防止在其过程中不断的扩容，影响性能；
• HashMap 是非线程安全的，我们可以自己在外部加锁，或者通过Collections.synchronizedMap 来实现线程安全，Collections.synchronizedMap 的实现是在每个方法上加上了 synchronized 锁；还可以使用ConcurrentHashMap
• 在迭代过程中，如果HashMap的结构被修改，会快速失败，与modCount有关。

  向HashMap增加一个(key,value)

1. 计算出key的hash，根据hash寻找其对应的数组下标位置，一般是index=hash%(length)，而数组长度length一般是2的幂次，计算公式就是：index=hash&(length-1)
2. 判断数组的index位置是否为空，为空则直接将(key,value)以及hashnew进一个Node再放在数组的此位置，否则需要处理hash冲突
3. 发生hash冲突，需要先判断此处是链表还是红黑树
4. 如果是链表，则从头遍历链表，看是否有与key重复的节点，有就再根据是否覆盖进行覆盖，没有就new一个Node添加到链表尾部，并判断链表是否需要转化成红黑树
5. 如果是红黑树，就用红黑树的方式新增，先看key是否存在于红黑树，判断依据是优先根据compareTo()其次根据equals()来判断是否相等，不相等则继续自旋寻找直到下一子节点为空，然后将新增节点放在下一个子节点，然后着色和旋转结束
6. 无论何种方式新增一个值后，都要判断是否需要扩容，判断数组容量*loadfactor > 目前元素数量是否成立，否则要扩容，扩容是新建一个2倍大的新数组，然后将原来的数据重新添加到新数组上

4.TreeMap

TreeMap的底层是红黑树，其原理和HashMap里的红黑树原理一样，不过TreeMap利用红黑树左小右大的特性来维护了一个整体根据key排序的Map，他的查找增加删除操作containsKey、get、put、remove都是log(n)复杂度，而HashMap的这些操作理想是O(1)复杂度

TreeMap的操作于HashMap的红黑树操作是一样的
增加：

1. 根据compareTo()来判断大小然后确定在左边还是右边，如果是本身则说明已经找到，则直接覆盖，否则就继续查找左边或右边（左小右大）
2. 直到查找到叶子节点，则新增一个节点，然后着色、旋转，达到平衡结束

5.LinkedHashMap

LinkedHashMap是HashMap的子类，它在HashMap的基础上增加了顺序。HashMap是没有顺序的，你很难给HashMap维护某种顺序，但是LinkedHashMap通过在HashMap.Node里增加before和after指针，将所有的节点串成了一个双向链表。

以下两种顺序可以选择：（一经初始化后无法更改）

• 按照插入顺序进行访问；
• 实现了访问最少最先删除功能，其目的是把很久都没有访问的 key 自动删除。

实现插入顺序访问比较简单，只要每次插入都只插入到尾部即可实现。
访问最少最先删除功能，则在每次的get等访问操作里额外加一个将此元素放置到尾部即可。
虽然是双向链表，但它的迭代器只提供了从头往后访问。

6.HashSet

1. 底层实现基于 HashMap，所以迭代时不能保证按照插入顺序，或者其它顺序进行迭代；
2. add、remove、contanins、size 等方法的耗时性能，是不会随着数据量的增加而增加的，这个主要跟 HashMap 底层的数组数据结构有关，不管数据量多大，不考虑 hash 冲突的情况下，时间复杂度都是 O (1)；
3. 线程不安全的，如果需要安全请自行加锁，或者使用Collections.synchronizedSet；
4. 迭代过程中，如果数据结构被改变，会快速失败的，会抛出ConcurrentModificationException 异常。

HashMap存储的(key,value)，而HashSet只需要存储key就可以了，所以它内部的HashMap的所有value都是指向同一个静态默认值，然后对增删改查进行简单封装一下就是HashSet了。
反倒是其构造函数比较有意思：

// 对 HashMap 的容量进行了计算
public HashSet(Collection<? extends E> c) {
 map = new HashMap<>(Math.max((int) (c.size()/0.75f) + 1, 16));
 addAll(c);
}

如果数据集的大小小于16，就构造一个16大小的HashMap，否则就构造一个恰好比不用扩容的大小

7.TreeSet

TreeSet主要是对TreeMap的复用，但也有些功能是TreeMap复用的TreeSet

8.java7和java8的区别

• 所有的List、Map、Set都增加了forEach()方法
• List：ArrayList无参初始化时，java7默认初始化一个10大小的数组，而java8默认初始化一个空数组，直到第一次添加数据时再扩容至10
• Map：HashMap由数组+链表变为数组+链表/红黑树，所以几乎所有方法都重新写了一遍；新增了getOrDefault()、putIfAbsent()、compute()、computeIfPresent()等方法；和ArrayList一样，初始化的数组大小为空，只有第一次新加值才扩容至16
• java8的Arrays还增加了一些parallel开头的方法支持并行计算