Java: 知识点汇总 - Githubissues

虽然学习使用Java很多年，但是很多学校里学的数据结构实现和原理的的东西却忘得七七八八，偶尔复习一下，苟日新，日日新，又日新。我们就来一起复习一下这些基础知识吧！

数据结构

1. String, StringBuilder, StringBuffer

String 原理：

String做为一个Class，它的数据由一个final修饰的char array 存储 private final char value[]; 有一点要注意，在Java 7以前，String的object pool一般都放在Permanent generation里，和static待遇相同。Java 7开始String就丢到了heap里，因为Perm太小了（默认4M），而且Perm有取消的趋势。 String s = new String("abc") 会创建2个object, 一个放在heap，一个在常量池(JDK 7开始在heap)。

StringBuilder 原理：

StringBuilder继承了abstract修饰的AbstractStringBuilder类，它的数据也是由char array存储（初始默认长度是16）。 char[] value;. StringBuilder在每次append新的String进来的时候，做了2件事（1）确认这个StringBuilder的容量是否足够，如果不足，就扩容。扩容操作会新建一个char[]，大小为可以刚好存储加入新String。核心代码： ensureCapacityInternal(count + len); Arrays.copyOf(value, newCapacity(minimumCapacity));

（2）把要加入的String里的char一个个复制进来。核心代码： str.getChars(0, len, value, count); System.arraycopy(value, srcBegin, dst, dstBegin, srcEnd - srcBegin);

StringBuffer 原理：

StringBuffer就有意思了。它总的来说是一个thread-safe的StringBuilder，其方法有synchronized注释。

对比

String小巧，生成速度快，但是修改会产生大量Object，加大GC的工作量，影响性能，适用于immutable的数据。 StringBuilder生成速度比String慢，线程不同步，但是可以修改，修改不会显著加大GC工作量，默认推荐使用。 StringBuffer修改速度比StringBuilder要慢，但是线程同步，安全。

2. HashMap

我们一般会使用键值对（不重复的key，可重复的value）的时候用上Map类。

HashMap 原理

继承关系

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

数据存储

transient Node<K,V>[] table;
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
}

重要方法 put实现

将key hash化
对table做非空检查，如果为空，则resize初始化。
判断hash for key和table的最后一个元素是否都为null，如果是则新建一个node，把value放进去。
如果步骤3不符合，判断该index是否在table里存在，如果存在，并且hash值相等，直接修改value，否则步骤5.
如果index存在但是hash不相等且这个node是个list，比较这个node.next的hash，直到相等就覆盖value，如果到null还没找到，就新加一个node在这个list的尾部。如果这个node是tree, 进行tree查找，没找到就做一次balance insersion。
如果步骤5里这个node是list，并且这个list过长超过TREEIFY_THRESHOLD（默认8）了，则把list变成红黑树（treeifyBin）。
如果table的size超过threshold，就是说满了，resize table，size变成2倍大小。这里threshold默认是这个table里有75%的index都有node占用。因为超过一定大小，index碰撞会变得很严重（很多hash在和（n-1)bitwise and后的index坑位都已经被占了，只能在那个list或者tree后面‘排队’。

至于为什么一开始就不用搜索更快的tree作为node，注释里这么解释

Because TreeNodes are about twice the size of regular nodes, we
use them only when bins contain enough nodes to warrant use
(see TREEIFY_THRESHOLD). And when they become too small (due to
removal or resizing) they are converted back to plain bins.  In
usages with well-distributed user hashCodes, tree bins are
rarely used.

get实现 get就是put的反向实现，但是逻辑比put简单很多。

将key hash化。
在table这个entry里找这个hash的node，找到后对node（tree or list）查找(用的是e.hash == hash和key.equals())。O(n) for LinkedList, O(nlgn) for tree. 红黑树实在Java8之后才加入，之前都只是纯粹的list。但是如果list比较长，O(n)是很慢的。不过红黑树空间占用比较多，所有加了一个TREEIFY_THRESHOLD作为妥协。

get和put中index的实现

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

... 
    // n 是table的大小
    (n - 1) & hash
...

如果key为null，返回0.
拿到key的hashCode()，做法一般是从key这个对象的内存地址转化得到。
把hashcode和其右进16位后的值进行bitwise XOR
把步骤3里的值和（n - 1) 做bitwise and，最终拿到index. 这样子做虽有一定可能的概率发生index碰撞，但是可以减少resize的开销。其实hash，treenode的设计，都是性能上的权衡妥协。hash可以保证table数组查找为O(1)，list和tree的查找均摊查找复杂度也是O(1)并且这个O(1)的offset不至于太大。

使用注意:

不适合并发编程，对数据的修改是不是同步的，数据会不一致，而且如果两个thread同时发现需要resize，会陷入死循环（详情看方法resize()）。并发可以用Hashtable。 Hashtable和HashMap基本相同，但是其put和get有synchronized关键词标记以保证线程安全，加锁的操作导致速度慢了，而且在Java8里面的Node不是tree，而是普通的list，不接受null作为key。而现在用得更多的是ConcurrentHashMap，Hashtable一直处于被放弃支持的境地。ConcurrentHashMap比Hashtable更快，因为方法没有synchronized，而是只给其field加了transient，volatile。ConcurrentHashMap的bucket有被分段，每段加了一个锁。另外，其实HashMap可以通过Map m = Collections.synchronizeMap(hashMap);来做到线程同步。
key最好是immutable的(final修饰就是immutable的)，不然key被修改了，其hashcode()也不一样了，value也丢了。

sorted： HashMap不是sorted，但是TreeMap和LinkedHashMap是sorted。

3. Vector, List

Vector同步，线程安全。

4. LinkedList, ArrayList

LinkedList本质是linked nodes,。ArrayList本质是数组，但是有index，这个数组在填满后需要新建复制一个大的。两者都有space的浪费。LinkedList每个node需要更多空间，ArrayList的数组tail需要预留一定冗余。 LinkedList使用场景：不会随意对list不同位置的value进行访问。希望在list中或者head加入删除元素。希望按顺序访问其中元素。 ArrayList使用场景：会对list随意位置频繁访问，希望在tail增加元素。

Keywords

extends inheritance. single inheritance for Java
implements multiple implementation for Java
protected The “protected” keyword allows the subclass to access the attributes directly.
static 表示这个variable, method, nested class是这个class本身的固有属性。
final 修饰后该variable不可修改。
abstract
transient 代表该variable不会被serializable。

并发编程

Runnable和Thread Runnable一般是implements，而Thread一般是extends。前者不同线程间共享数据（需要互斥锁synchronized，注意不是直接给数据加synchronized...），后者内部数据独立。
volatile 只能赋值于variable。优化器在用到这个variable时必须每次都小心地重新读取这个variable的值，而不是使用保存在寄存器里的备份。它修饰的variable不会被编译器优化。保证修改的值会立即被更新到主存，保证了可见性，但是不保证原子性。不会造成线程堵塞。能够保证修饰的variable本身有有序性（内存屏障）。适用于状态variable（boolean）和JAVA的double check。
synchronized 保证任一时刻只有一个线程使用该variable或者执行该代码块，保证了大范围（赋值和读取之外）操作的原子性，可见性和有序性。可能造成线程堵塞。我们知道自增是两个原子操作（读取+赋值）组成的非原子操作，我们有三个保证原子性的方法。
```
public synchronized void increase() {
inc++;
}
```
```
// 加锁
Lock lock = new ReentrantLock(); 
public  void increase() {
lock.lock();
try {
    inc++;
} finally{
    lock.unlock();
}
}
```
```
// atomic wrapper classes
public  AtomicInteger inc = new AtomicInteger();  
public  void increase() {
inc.getAndIncrement();
}
```
让线程停止的Thread的方法：优先级，yield，sleep，join 优先级： 1-10. 默认5。用于提高程序的效率。高优先级有大概率抢到CPU时间。
```
Thread t = new MyThread();  
 t.setPriority(8);  
 t.start();
```
yield：该线程让步于其他相同优先级的线程。 Thread.yield() sleep：暂停线程。帮助所有线程获得运行机会。指定的睡眠时间是最短时间。 Thread.sleep(123); join：让一个线程加入另外一个线程的尾部。非静态。
```
Thread t = new MyThread();  
t.start();  
t.join(); 
```
wait，notify, notifyAll 与sleep不同，wait是Object的方法。wait后，需要别的线程执行notify或者notifyAll，才能继续执行。 sleep 让线程从 [running] -> [阻塞态] 时间结束/interrupt -> [runnable] wait 让线程从 [running] -> [等待队列]notify -> [lock pool] -> [runnable] notify, notifyAll也是Object的方法，注释是这么说的：Wakes up all threads that are waiting on this object's monitor.

GC

GC的工作原理

reference在stack，object在heap，没有reference的object就会被回收。优先级较低的后台进程。

Young gen， Old gen，Permanent gen

Young gen会放刚new的object，并且频繁快速gc符合条件的对象。 Young gen里又分Eden，Fron Survivor和To Survivor (8:1:1)，survivor有一个一定是空的。但是如果object超大，一次GC就可能被丢进Old gen。 Old gen放多次GC后还存在的对象(MaxTenuringThreshold默认15次)。空间Young gen：Old gen约等于1：2. Permanent gen放一些static，String（为了解决String内容重复问题）。针对Permanent gen的Major GC，触发条件苛刻。

Minor GC，Major GC = Full GC

Minor GC是发生于Young gen的GC。 Major GC是发生于Old gen和Permanent gen的GC，时间更久。

有哪些GC

Serial（UseSerialGC）串行收集器，复制算法。 SerialOld （UseSerialGC）串行收集器，标记整理算法。 CMS（Concurrent Low Pause Collector）经典的Stop Tow World（STW）。STW initial mark -- concurrent marking -- concurrent precleaning -- STW remark -- concurrent sweeping -- concurrent reset。缺点：因为标记清理算法，会有内存碎片。需要更多CPU资源。需要更大的heap，默认old gen 68%启动GC。 ParNew （UseParNewGC）并行收集器，复制算法。 G1 GC

哪些算法

根搜索标记-清除：扫描--标记--清除，没有对活着的对象进行整理，会有内存碎片。复制：在标记-清除后，将存活对象往一端空闲空间移动，更新stack里的reference，成本高，但是解决了内存碎片的问题。 Young gen的Minor GC一般用复制算法，Major GC一般用标记-清除算法。

System.gc() 可以触发full GC但不是马上执行，比较影响性能。

Reflection

原理：

Exception

Throwable Exception & Error RunTimeException & other Exceptions

Joldnine / joldnine.github.io

Java: 知识点汇总 #16