Java基础汇总（二）

Java集合

1.ArrayList和LinkedList

• 是否线程安全：两者都不是线程安全的
• 底层数据结构：Object数组，双向链表
• 是否支持快速随机访问
• 插入删除元素速度
• 空间占用：ArrayList尾部会预留一定的容量

RandomAccess接口

public interface RandomAccess {
}

RandomAccess是一个标志性接口，没有任何定义。标志实现这个接口的类具有随机访问的功能。

在binartSearch()方法中，会判断传入的list是否RandomAccess实现

2.ArrayList,Vectors,CopyOnWriteArrayList

CopyOnWriteArrayList

• 实现了List接口
• 内部持有一个ReentrantLock lock = new ReentrantLock();
• 底层是用volatile transient声明的数组 array
• 读写分离，写时复制出一个新的数组，完成插入、修改或者移除操作后将新数组赋值给array

增删改都需要获得锁，并且锁只有一把，而读操作不需要获得锁，支持并发。

CopyOnWriteArrayList为什么并发安全且性能比Vector好？

我知道Vector是增删改查方法都加了synchronized，保证同步，但是每个方法执行的时候都要去获得锁，性能就会大大下降，而CopyOnWriteArrayList 只是在增删改上加锁，但是读不加锁，在读方面的性能就好于Vector，CopyOnWriteArrayList支持读多写少的并发情况。

3.HashSet,CopyOnWriteArraySet

HashSet

• HashSet实际上就是HashMap，只是将value设置成null
• HashSet中的元素不重复的
• HashSet中的元素是无序的

CopyOnWriteArraySet

HashSet对应的并发类为什么叫CopyOnWriteArraySet，而不是叫CopyOnWriteHashSet呢？

public class CopyOnWriteArraySet<E> extends AbstractSet<E>
        implements java.io.Serializable {
    private static final long serialVersionUID = 5457747651344034263L;

    private final CopyOnWriteArrayList<E> al;

    /**
     * Creates an empty set.
     */
    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList<E>();
    }
    ...
}

CopyOnWriteArraySet的底层存储结构竟然是CopyOnWriteArrayList，那么我们就可以知道它的名字的由来了，并且知道它支持并发的原理跟CopyOnWriteArrayList是一样的。

4.ConsurrentHashMap，HashMap，Hashtable

HashTable

• 底层数组+链表实现，无论key还是value都不能为null，线程安全，实现线程安全的方式是在修改数据时锁住整个HashTable，效率低。
• 初始size为11，扩容：newsize = olesize*2+1
• 计算index的方法：index = (hash & 0x7FFFFFFF) % tab.length

ConcurrentHashMap

• 在JDK1.7的时候，ConcurrentHashMap（分段锁） 对整个桶 数组进?了分割分段(Segment)，每?把锁只锁容器其中?部分数据，多线程访问容器?不同数 据段的数据，就不会存在锁竞争，提?并发访问率。
• 到了 JDK1.8 的时候已经摒弃了Segment的 概念，?是直接? Node 数组+链表+红?树的数据结构来实现，并发控制使? synchronized 和 CAS 来操作，每次对一个桶上锁。
• synchronized只锁定当前链表或红??叉树的?节点，这样只要hash不冲突，就不会产?并发，效率? 提升N倍

5.HashMap

参数

• DEFAULT_INITIAL_CAPACITY = 1<<4 // 缺省容量
• MAXIMUM_CAPACITY = 1 << 30 // 最大容量
• DEFAULT_LOAD_FACTOR = 0.75 // 缺省装载因子
• TREEIFY_THRESHOLD = 8 // 将链表变成红黑树的阈值
• UNTREEIFY_THRESHOLD = 6 // 将红黑树变回链表的阈值
• MIN_TREEIFY_CAPACITY = 64 // 会转换成红黑树的最小容量，就是说如果map的容量低于64， 就算一个桶里面数量大于8也不会转换成红黑树
• size // 容量
• modCount // modify的次数
• threshold // 扩容阈值，超过这个阈值，将扩容
• loadFactor // 装在因子

Node

• hash
• key
• value
• next

注意点

• 在put的时候，会对key进行一个hash，但并不是直接将key的hashCode进行hash，而需要进行一步处理

  // 注意在hash过程中，会进处理。(h = key.hashCode()) ^ (h >>> 16); 相当于在散列过程中同时考虑高16位的信息
  static final int hash(Object key) {
      int h;
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

• jdk 1.8 与 1.7 的区别 ： Entry-> Node, 添加红黑树, 头插改成尾插

头插改成尾插的原因是：为了防止resize过程中形成循环链表

• 设置成的目的

1. 在hash的过程中，需要对size取模，而如果size的长度是，则可通过的计算方法得到。

2. 创建Map过程中，初始的size不一定是, 如果不是，则会进行处理：

  // 这是java11中的写法，与java8中有所不同
  static final int tableSizeFor(int cap) {
     int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
     return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
  }

3. resize过程中需要rehash, 因为扩容成原来的两倍，所以原本桶中的Node有两种rehash可能：留在原桶;rehash到index+oldCap的位置，而判断的方法只需要对于原来的hash值在进行一次hash，&oldCap即可：举个例子，如果oldCap=8 (oX1000)，则扩容后是16，原本在桶7位置的只需要判断是放在7还是放在15，所以只需要将hash &= oldCap 即可。

• key为null时

key如果为null，会默认将hash为0，hash后放在桶0中。

注意：在ConcurrentHashMap中是不能插入key为null的，ConcurrentHashMap不能put null 是因为 无法分辨是key没找到的null还是有key值为null，这在多线程里面是模糊不清的，所以压根就不让put null。

6.如何选用集合

主要根据集合的特点来选?，?如我们需要根据键值获取到元素值时就选?Map接?下的集合，需要排序时选择TreeMap,不需要排序时就选择HashMap,需要保证线程安全就选?ConcurrentHashMap.当我们只 需要存放元素值时，就选择实现Collection接?的集合，需要保证元素唯?时选择实现Set接?的集合 ?如TreeSet或HashSet，不需要就选择实现List接?的?如ArrayList或LinkedList，然后再根据实现 这些接?的集合的特点来选?。