学习 | 随记

io模型

2022年10月26日 14:17 周三

学习

复习, 复习-JavaGuide, 复习-JavaGuide-Io

I/O#

何为I/O#

I/O(Input/Output)，即输入/输出 从计算机结构的角度来解读一下I/O，根据冯诺依曼结构，计算机结构分为5大部分：运算器、控制器、存储器、输入设备、输出设备 其中，输入设备：键盘；输出设备：显示器网卡、硬盘既属于输入设备也属于输出设备
输入设备向计算机输入（内存）数据，输出设备接收计算机（内存）输出的数据，即I/O描述了计算机系统与外部设备之间通信的过程
从应用程序的角度解读I/O
- 为了保证系统稳定性和安全性，一个进程的地址空间划分为用户空间User space和内核空间Kernel space kernel 英[ˈkɜːnl]
- 平常运行的应用程序都运行在用户空间，只有内核空间才能进行系统态级别的资源有关操作—文件管理、进程通信、内存管理
- 如果要进行IO操作，就得依赖内核空间的能力，用户空间的程序不能直接访问内核空间
- 用户进程要想执行IO操作，必须通过系统调用来间接访问内核空间
对于磁盘IO（读写文件）和网络IO（网络请求和响应），从应用程序视角来看，应用程序对操作系统的内核发起IO调用（系统调用），操作系统负责的内核执行具体IO操作
- 应用程序只是发起了IO操作调用，而具体的IO执行则由操作系统内核完成
应用程序发起I/O后，经历两个步骤
- 内核等待I/O设备准备好数据
- 内核将数据从内核空间拷贝到用户空间

有哪些常见的IO模型#

UNIX系统下，包括5种：同步阻塞I/O，同步非阻塞I/O，I/O多路复用、信号驱动I/O和异步I/O

Java中3中常见I/O模型#

BIO (Blocking I/O )#

应用程序发起read调用后，会一直阻塞，直到内核把数据拷贝到用户空间

NIO (Non-blocking/New I/O)#

对于java.nio包，提供了Channel、Selector、Buffer等抽象概念，对于高负载高并发，应使用NIO
NIO是I/O多路复用模型，属于同步非阻塞IO模型
- 一般的同步非阻塞 IO 模型中，应用程序会一直发起 read 调用。
  等待数据从内核空间拷贝到用户空间的这段时间里，线程依然是阻塞的**，**直到在内核把数据拷贝到用户空间。
  相比于同步阻塞 IO 模型，同步非阻塞 IO 模型确实有了很大改进。通过轮询操作，避免了一直阻塞。
  但是，这种 IO 模型同样存在问题：应用程序不断进行 I/O 系统调用轮询数据是否已经准备好的过程是十分消耗 CPU 资源的。
  ★★ 也就是说，【准备数据，数据就绪】是不阻塞的。而【拷贝数据】是阻塞的
- I/O多路复用线程首先发起select调用，询问内核数据是否准备就绪，等准备好了，用户线程再发起read调用，r**ead调用的过程（数据从内核空间–>用户空间）**还是阻塞的
  IO 多路复用模型，通过减少无效的系统调用，减少了对 CPU 资源的消耗。

io设计模式

2022年10月24日 23:40 周一

学习

复习, 复习-JavaGuide, 复习-JavaGuide-Io

装饰器模式#

类图：
ly-20241212141951023

装饰器，Decorator，装饰器模式可以在不改变原有对象的情况下拓展其功能
★装饰器模式，通过组合替代继承来扩展原始类功能，在一些继承关系较复杂的场景（IO这一场景各种类的继承关系就比较复杂）下更加实用
对于字节流，FilterInputStream（对应输入流）和FilterOutputStream（对应输出流）是装饰器模式的核心，分别用于增强（继承了）InputStream和OutputStream子类对象的功能 Filter （过滤的意思），中间（Closeable）下面这两条虚线代表实现；最下面的实线代表继承
其中BufferedInputStream（字节缓冲输入流）、DataInputStream等等都是FilterInputStream的子类，对应的BufferedOutputStream和DataOutputStream都是FilterOutputStream的子类

例子，使用BufferedInputStream（字节缓冲输入流）来增强FileInputStream功能

BufferedInputStream源码（构造函数）

private static int DEFAULT_BUFFER_SIZE = 8192;
public BufferedInputStream(InputStream in) {
    this(in, DEFAULT_BUFFER_SIZE);
}

public BufferedInputStream(InputStream in, int size) {
    super(in);
    if (size <= 0) {
        throw new IllegalArgumentException("Buffer size <= 0");
    }
    buf = new byte[size];
}

使用

try (BufferedInputStream bis = new BufferedInputStream(new FileInputStream("input.txt"))) {
    int content;
    long skip = bis.skip(2);
    while ((content = bis.read()) != -1) {
        System.out.print((char) content);
    }
} catch (IOException e) {
    e.printStackTrace();
}

ZipInputStream和ZipOutputStream还可以用来增强BufferedInputStream和BufferedOutputStream的能力

io基础

2022年10月23日 12:21 周日

学习

复习, 复习-JavaGuide, 复习-JavaGuide-Io

简介#

IO，即Input/Output，输入和输出，输入就是数据输入到计算机内存；输出则是输出到外部存储（如数据库、文件、远程主机）
根据数据处理方式，又分为字节流和字符流
基类
- 字节输入流 InputStream，字符输入流 Reader
- 字节输出流 OutputStream, 字符输出流 Writer

字节流#

字节输入流 InputStream InputStream用于从源头（通常是文件）读取数据（字节信息）到内存中，java.io.InputStream抽象类是所有字节输入流的父类
- 常用方法
  - read() ：返回输入流中下一个字节的数据。返回的值介于 0 到 255 之间。如果未读取任何字节，则代码返回 -1 ，表示文件结束。
  - read(byte b[ ]) : 从输入流中读取一些字节存储到数组 b 中。如果数组 b 的长度为零，则不读取。如果没有可用字节读取，返回 -1。如果有可用字节读取，则最多读取的字节数最多等于 b.length ，返回读取的字节数。这个方法等价于 read(b, 0, b.length)。
  - read(byte b[], int off, int len) ：在read(byte b[ ]) 方法的基础上增加了 off 参数（偏移量）和 len 参数（要读取的最大字节数）。
  - skip(long n) ：忽略输入流中的 n 个字节 ,返回实际忽略的字节数。
  - available() ：返回输入流中可以读取的字节数。
  - close() ：关闭输入流释放相关的系统资源。
- Java9 新增了多个实用方法

ConcurrentHashMap源码

2022年10月22日 18:26 周六

学习

复习, 复习-JavaGuide, 复习-JavaGuide-集合

总结#

Java7 中 ConcurrentHashMap 使用的分段锁，也就是每一个 Segment 上同时只有一个线程可以操作，每一个 Segment 都是一个类似 HashMap 数组的结构，每一个HashMap可以扩容，它的冲突会转化为链表。但是 Segment 的个数一但初始化就不能改变。

Java8 中的 ConcurrentHashMap 使用的 Synchronized 锁加 CAS 的机制。结构也由 Java7 中的 Segment 数组 + HashEntry 数组 + 链表 进化成了 Node 数组 + 链表 / 红黑树，Node 是类似于一个 HashEntry 的结构。它的冲突再达到一定大小时会转化成红黑树，在冲突小于一定数量时又退回链表。

源码（略过）#

ConcurrentHashMap1.7#

存储结构
- Segment数组（该数组用来加锁，每个数组元素是一个HashEntry数组（该数组可能包含链表）
- 如图，ConcurrentHashMap由多个Segment组合，每一个Segment是一个类似HashMap的结构，每一个HashMap内部可以扩容，但是Segment个数初始化后不能改变，默认16个（即默认支持16个线程并发）

ConcurrentHashMap1.8#

存储结构可以发现 Java8 的 ConcurrentHashMap 相对于 Java7 来说变化比较大，不再是之前的 Segment 数组 + HashEntry 数组 + 链表，而是 Node 数组 + 链表 / 红黑树。当冲突链表达到一定长度时，链表会转换成红黑树。

HashMap源码

2022年10月21日 15:30 周五

学习

复习, 复习-JavaGuide, 复习-JavaGuide-集合

HashMap简介#

HashMap用来存放键值对，基于哈希表的Map接口实现，是非线程安全的
可以存储null的key和value，但null作为键只能有一个
JDK8之前，HashMap由数组和链表组成，链表是为了解决哈希冲突而存在；JDK8之后，当链表大于阈值（默认8），则会选择转为红黑树（当数组长度大于64则进行转换，否则只是扩容），以减少搜索时间
HashMap默认初始化大小为16，每次扩容为原容量2倍，且总是使用2的幂作为哈希表的大小

底层数据结构分析#

JDK8之前，HashMap底层是数组和链表，即链表散列；通过key的hashCode，经过扰动函数，获得hash值，然后再通过(n-1) & hash 判断当前元素存放位置（n指的是数组长度），如果当前位置存在元素，就判断元素与要存入的元素的hash值以及key是否相同，相同则覆盖，否则通过拉链法解决
ly-20241212141931350

扰动函数，即hash(Object key)方法

//JDK1.8  
static final int hash(Object key) {
      int h;
      // key.hashCode()：返回散列值也就是hashcode
      // ^ ：按位异或
      // >>>:无符号右移，忽略符号位，空位都以0补齐
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

JDK1.7

//JDK1.7 , 则扰动了4次，性能较差
static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).

    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

JDK1.8之后，当链表长度大于阈值（默认为 8）时，会首先调用 treeifyBin()方法。这个方法会根据 HashMap 数组来决定是否转换为红黑树。只有当数组长度大于或者等于 64 的情况下，才会执行转换红黑树操作，以减少搜索时间。否则，就是只是执行 resize() 方法对数组扩容。相关源码这里就不贴了，重点关注 treeifyBin()方法即可！

ArrayList源码

2022年10月20日 17:01 周四

学习

复习, 复习-JavaGuide, 复习-JavaGuide-集合

简介#

底层是数组队列，相当于动态数组，能动态增长，可以在添加大量元素前先使用ensureCapacity来增加ArrayList容量，减少递增式再分配的数量 源码：
```
public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable{ }
```
1. Random Access，标志接口，表明这个接口的List集合支持快速随机访问，这里是指可通过元素序号快速访问
2. 实现Cloneable接口，能被克隆
3. 实现java.io.Serializable，支持序列化
ArrayList和Vector区别
- ArrayList和Vector都是List的实现类，Vector出现的比较早，底层都是Object[] 存储
- ArrayList线程不安全（适合频繁查找，线程不安全）
- Vector 线程安全的
ArrayList与LinkedList区别
- 都是不同步的，即不保证线程安全
- ArrayList底层为Object数组；LinkedList底层使用双向链表数据结构(1.6之前为循环链表，1.7取消了循环)
- 插入和删除是否受元素位置影响
  - ArrayList采用数组存储，所以插入和删除元素的时间复杂度受元素位置影响[ 默认增加到末尾，O(1) ; 在指定位置，则O(n) , 要往后移动]
  - LinkedList采用链表存储，所以对于add(E e)方法，还是O(1)；如果是在指定位置插入和删除，则为O(n) 因为需要遍历将指针移动到指定位置
```
//LinkedList默认添加到最后
public boolean add(E e) {
        linkLast(e);
        return true;
}
```
  - LinkedList不支持高效随机元素访问，而ArrayList支持（通过get(int index))
  - 内存空间占用 ArrayList的空间浪费主要体现在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费在，每个元素都需要比ArrayList更多空间（要存放直接前驱和直接后继以及(当前)数据)

3. 扩容机制分析 ( JDK8 )#

ArrayList的构造函数

三种方式初始化，构造方法源码
空参，指定大小，指定集合（如果集合类型非Object[].class，则使用Arrays.copyOf转为Object[].class)
以无参构造方式创建ArrayList时，实际上初始化赋值的是空数组；当真正操作时才分配容量，即添加第一个元素时扩容为10


 /**
     * 默认初始容量大小
     */
    private static final int DEFAULT_CAPACITY = 10;


    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     *默认构造函数，使用初始容量10构造一个空列表(无参数构造)
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 带初始容量参数的构造函数。（用户自己指定容量）
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {//初始容量大于0
            //创建initialCapacity大小的数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {//初始容量等于0
            //创建空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {//初始容量小于0，抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }


   /**
    *构造包含指定collection元素的列表，这些元素利用该集合的迭代器按顺序返回
    *如果指定的集合为null，throws NullPointerException。
    */
     public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

以无参构造参数函数为例 先看下面的 add()方法扩容

集合使用注意事项

2022年10月19日 17:26 周三

学习

复习, 复习-JavaGuide, 复习-JavaGuide-集合

集合判空#

isEmpty()可读性更好，且绝大部分情况下时间复杂度为O(1)

有例外：ConcurrentHashMap的size()和isEmpty() 时间复杂度均不是O(1)

public int size() {
    long n = sumCount();
    return ((n < 0L) ? 0 :
            (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
            (int)n);
}
final long sumCount() {
    CounterCell[] as = counterCells; CounterCell a;
    long sum = baseCount;
    if (as != null) {
        for (int i = 0; i < as.length; ++i) {
            if ((a = as[i]) != null)
                sum += a.value;
        }
    }
    return sum;
}
public boolean isEmpty() {
    return sumCount() <= 0L; // ignore transient negative values
}

集合转Map#

集合_2

2022年10月18日 08:54 周二

学习

复习, 复习-JavaGuide, 复习-JavaGuide-集合

Map#

HashMap和Hashtable的区别

HashMap是非线程安全的，Hashtable是线程安全的，因为Hashtable内部方法都经过synchronized修饰（不过要保证线程安全一般用ConcurrentHashMap）
由于加了synchronized修饰，HashTable效率没有HashMap高
HashMap可以存储null的key和value，但null作为键只能有一个**；HashTable不允许有null键和null值**
初始容量及每次扩容
- Hashtable默认初始大小11，之后扩容为2n+1;HashMap初始大小16，之后扩容变为原来的2倍
- 如果指定初始大小，HashTable直接使用初始大小
  而HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的**tableSizeFor()**方法保证，下面给出了源代码）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小,后面会介绍到为什么是 2 的幂次方

底层数据结构

JDK1.8之后HashMap解决哈希冲突时，当链表大于阈值（默认8）时，将链表转为红黑树（转换前判断，如果当前数组长度小于64，则先进行数组扩容，而不转成红黑树），以减少搜索时间。
Hashtable没有上面的机制

/**
HashMap 中带有初始容量的构造函数：
*/
public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
     public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    } 

/*下面这个方法保证了 HashMap 总是使用 2 的幂作为哈希表的大小。*/
/**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

HashMap和hashSet区别

集合_1

2022年10月17日 08:55 周一

学习

复习, 复习-JavaGuide, 复习-JavaGuide-集合

集合包括`Collection`和`Map`，Collection 存放单一元素。Map 存放键值对#

ly-20241212141928129

List，Set，Queue，Map区别#

List(对付顺序的好帮手): 存储的元素是有序的、可重复的。
Set(注重独一无二的性质): 存储的元素是无序的、不可重复的。
Queue(实现排队功能的叫号机): 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。
Map(用 key 来搜索的专家): 使用键值对（key-value）存储，类似于数学上的函数 y=f(x)，“x” 代表 key，“y” 代表 value，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。

各种集合框架–底层数据结构#

List
- ArrayList、Vector —-> Object[] 数组
- LinkedList 双向链表 (jdk 1.6 之前为循环链表, 1.7 取消了循环)
Set
- HashSet （无序，唯一），且基于HashMap
- LinkedHashSet 是HashSet的子类，基于LinkedHashMap (LinkedHashMap内部基于HashMap实现)
- TreeSet(有序，唯一) ：红黑树（自平衡的排序二叉树）
Queue (队列)
- PriorityQueue：Object[] 数组来实现二叉堆
- ArrayQueue：Object[] 数组+ 双指针
Map
- HashMap： JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间
- LinkedHashMap： LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。

I/O#

何为I/O#

有哪些常见的IO模型#

Java中3中常见I/O模型#

BIO (Blocking I/O )#

NIO (Non-blocking/New I/O)#

装饰器模式#

简介#

字节流#

总结#

源码 （略过）#

ConcurrentHashMap1.7#

ConcurrentHashMap1.8#

HashMap简介#

底层数据结构分析#

简介#

3. 扩容机制分析 ( JDK8 )#

集合判空#

集合转Map#

Map#

集合包括Collection和Map，Collection 存放单一元素。Map 存放键值对#

List，Set，Queue，Map区别#

各种集合框架–底层数据结构#

源码（略过）#

集合包括`Collection`和`Map`，Collection 存放单一元素。Map 存放键值对#