JAVA知识梳理

多线程相关

---

死锁

死锁四个条件：

1. 互斥条件

   • 临界资源只能被一个线程拥有

2. 占有且等待

   • 线程/进程拥有补发临界资源，但同时请求另外一些临界资源

3. 占有不释放

   • 在请求到其它临界资源前，已拥有的临界资源不会被释放

4. 循环链

   • 多个线程/进程形成循环请求链

饥饿

线程一直不能获得所需要的资源，如：低优先级线程请求资源一直被高优先级线程持有

多线程操作特性

1. 原子性

   • 操作不可中断

2. 有序性

   • 多线程操作是有序的，但可能出现cpu指令重排：

     • cpu采用流水线指令模式，可能出现后面指令提前到前面执行

3. 可见性

   • 线程对临界资源的操作，其他线程能看到最新的临界资源

   • violate

     • 保证有序性和可见性

     • 临界资源发生变化时，强迫写到共享内存

线程状态

1. 新建

   • new

2. 就绪

   • start：等待系统调度运行

   • yield：从运行切换到就绪，重新参与资源竞争

3. 运行

   • run

4. 阻塞

   • join

   • sleep

   • suspend

5. 结束

   • 正常运行结束

   • stop： 不建议使用

6. 中断

   • 并不会中断线程，只是设置中断标识位

   • 通过中断，使线程跳出阻塞状态（sleep等）

线程并发包：java.util.concurrent

1. synchronized

   • 重入锁

     • 线程可重复访问已获得的临界资源，无需释放和再申请锁

   • 配合object.wait，object.notify实现多线程通信

     • 使用前需获得锁

     • wait执行完后自动释放锁

     • notify/notifyall不会释放锁，只是发送一个通知，当同步块执行完后才会释放锁

2. 重入锁：reentrantlock

   • 重入锁

   • 可设置优先响应中断，获得锁的过程中，可优先响应中断，避免死锁

   • 可设置超时时长：获取的过程中，可设置等待时长

   • 可设置是否为公平锁

     • 公平锁：按申请的先后顺序获得锁

     • 不公平锁：随机分配

   • 可与condition(notify/signal)配合使用，实现多线程通信，类似synchronized+object.wait+object.notify

3. 信号量：semaphone

   • 实现多个线程同时访问临界资源

4. 读写锁：writereadlock

   • 读不阻塞

   • 写阻塞

5. 计时器：countdownlatch

   • 计数为0时，线程访问临界资源，跳出阻塞

6. 循环栅栏：cyclebarrier

   • 类似countdownlatch，但可重复计数

7. locksupport

   • 可实现线程的暂停和回复：park、unpark

   • 即使先unpark在park也无问题，不像suppend和resume，resume发生在suppend前出问题

线程并发集合

1. concurrentmap

2. collections集合方法

3. copyandwritelist

4. blockingqueue

线程池

创建线程池的几个参数：

1. corepoolsize：核心线程数

2. maxnumpoolsize：最大线程数

3. keepalive：闲置线程（非核心线程）存活时间

4. unit：存活时间单位

5. workqueue：当无空闲线程处理任务时，任务放到该工作队列等待调度

   • BlockingQueue实例，不同实例对应了不同调度策略和拒绝策略

6. threadfactory：线程创建工厂

7. handler：任务拒绝执行策略

CAS

1. 比较并交换/无锁/乐观锁

2. a-b-a问题

   • 线程x读取遍历z的值为a,线程y读取到z的值也为a，但此时z的值可能已经经过多次变化

   • 可通过版本号优化

3. AutoInteger等

   • 内部采用死循环获取临界资源方式，效率低

锁优化

1. 锁持有时间

2. 加锁粒度：细化、粗化

3. 锁分离

JVM

---

参考：https://juejin.im/post/5b85ea54e51d4538dd08f601

java内存划分

1. 堆

   • 线程共享

2. 方法区

   • 线程共享

3. native栈

4. java栈

5. pc

java堆划分

1. 新生代minor

   • eden区

     • 对象一般分配在新生代的eden区，大对象和长期存活对象分配在老年代

     • eden区对象经过一次gc后，将移动到surrivor区，surrivor区经过n次（一般为15次）gc后，将移动到老年代

   • surrivor区

     • from区

     • to区

2. 老年代major

3. 永久代/元空间

java引用

1. 强引用

2. 软引用

3. 弱引用

4. 虚引用

java如何标识对象是否存活？

1. 引用计数：循环计数问题

2. 可达性分析：GCRoot

3. string对象存活：字符串无string对象引用

4. class存活：实例都释放，且加载它的classloader被释放

GC算法

1. 标记清除

   • 标记内存回收对象，再回收

   • 效率高，但存在内存碎片问题

2. 复制

   • 将内存划分为两块，在其中一款分配对象，gc后，存活的对象移动到另外一块

3. 标记整理

   • 类似复制，但没有将内存划分为两块，只是在内存的一端分配对象，存活的对象移动到另外一端

4. 分代回收

   • 新生代：复制算法

     • 频繁、快、高效

   • 老年代：标记清除、标记整理

     • 慢，低效，时间间隔久

5. 常用gc处理器

   • 串行

   • 并发、并行：gc线程和用户线程

设计模式

---

六大原则

1. 单一原则

   • 类、接口、方法功能单一

2. 里氏代换原则

   • 子类应扩展父类抽象方法，但不应该扩展父类非抽象方法

3. 依赖倒置原则

   • 抽象不依赖细节，细节应该依赖抽象

4. 接口隔离原则

   • 接口方法尽量少，功能划分为多个接口

5. 迪米特拉原则

   • 类对依赖的类了解尽可能少，减少代码耦合

6. 开放封闭原则

   • 扩展开放，修改封闭

集合/数据结构

---

Collections

1. set

   • 元素唯一

   • treeset

     • 红黑树结构

   • hashset

     • hash算法计算元素存放地址

2. list

   • arraylist

     • 线性存储

   • vector

     • 线程安全

   • linkedlist

     • 可实现fifo、stack

     • 同时实现了list和queue

3. queue

   • priorityqueue

     • 优先队列

map

1. hashmap

   • 数组+链表实现

   • 多个数据的hash值相同时，通过链表连接

2. hashtable

   • 线程安全

3. treemap

   • 红黑树

4. linkedhashmap

   • 基于双向链表实现的hashmap

   • 支持插入排序和访问排序

     • 访问排序：每次访问完后的元素放在链表头，lru算法

其他

1. hash指元素使用hash算法计算存储地址

2. link/tree，指元素是链表或者树的结构

IO

---

1. 字节流

2. 字符流

3. randomaccessfile

4. NIO

   • 非阻塞、内存映射方式，面向块

   • channel

   • buffer

     • 外部数据读写 与buffer交互

   • selector

     • 异步IO

序列化

---

1. 原理

   • java为序列化对象采用序列号机制，当序列化一个对象时，先检查该对象是否已经序列化

     • 未序列化，采用流中数据构建，并为该对象关联一个序列号

     • 已序列化，直接根据关联的序列号，获得该对象引用

2. 版本号

   • 根据类的超类、接口和域等属性计算得到，当上述信息发生变化时，版本号会发生变化

   • 一般将版本号静态写死，防止序列化时版本号不一致发生异常

3. static、transient域和方法，不能被序列化

4. 序列化产生新的对象（不调用构造函数），单例模式失效

创建对象的几种方式

---

1. 调用构造函数

2. new

3. 反射

4. 序列化

   • 不调用构造函数，通过二进制流构造

5. clone

   • 不调用构造函数

其他

---

1. classloader

   • 双亲委派模型

   • 引导classloader

     • 最顶层的加载类，主要加载核心类库，%JRE_HOME%\lib下的rt.jar、resources.jar、charsets.jar和class等

   • 扩展classloader

     • 加载目录%JRE_HOME%\lib\ext目录下的jar包和class文件

   • 系统（应用）classloader

     • 加载当前应用classpath所有类

• https://mp.weixin.qq.com/s/izdIkiU5YcR-rIOw0ehU4g

• https://blog.csdn.net/linzhiqiang0316/article/details/80473906

常用算法

---

1. 深搜，DFS

Node* DFS(Node* root,int data)
{
    if(root.key == data)
        return root;

    Node*[] chids = data->childs();
    for(Node* child : childs)
    {
        if(child.key == data)
            return child;      
        
        DFS(child,data);
    }
}

2. 广搜

Node* BFS(Node* root,int data)
{
    if(root.key == data)
        return root;
    
    FIFO<Node*> fifo = new FIFO<Node*>();
    fifo.queue(root);
    
    return BFS_Visit(fifo,data);
}

Node* BFS_Visit(FIFO<Node*> fifo,int data)
{
    while(!fifo.isEmpty())
    {
        Node* item = fifo.dequeue();
        if(item.key == data)
            return item;
        
        for(Node* child : item.childs())
            fifo.queue(child);
    }
}

3. 排序

   • 参考：http://blog.sina.com.cn/s/blog_714cb3040102vexf.html

   • 计数排序

   • 快排

int quick_sort_part(int data[], int start, int end)
{
       int i = start;
       int j = start;
       int key = end;
       while (i <= end)
       {
              if (data[i] < data[key])
              {
                     exchange(data[i], data[j]);
                     j++;
              }
              i++;
       }
       if (j != key)
       {
              exchange(data[j], data[key]);
       }
       return j;
}

//快速排序
void quick_sort(int data[], int start, int end)
{
       if (start < end)
       {
              int k = quick_sort_part(data, start, end);
              quick_sort(data, start, k - 1);
              quick_sort(data, k + 1, end);
       }
}

• 合并排序

• 堆排序

  • 最大堆

  • 最小堆

• 树

  • 二叉树

  • 二叉搜索树

  • b树

  • 红黑树