题目描述

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

解答

书p286，翻转字符串的困难版，要求空间复杂度O(1)

空间复杂度O(N)：

1
2
3
4
5
6
7
8
9
10

public String LeftRotateString(String str, int n) {
    if (n < 0 || str == null || str.length() == 0) {
        return "";
    }
    n = n % str.length();
    StringBuilder builder = new StringBuilder();
    builder.append(str.substring(n));
    builder.append(str, 0, n);
    return builder.toString();
}

题目描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

解答

暴力枚举会超时。根据丑数的定义，丑数一定是比它小的丑数乘2、3、5得到的。

维护一个数组nums[]，按照递增序列存储着已得到的丑数。已有丑数乘2、3、5得到的最小的超过已有最大丑数即为要找的下一个丑数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public int GetUglyNumber_Solution(int index) {
    if (index <= 0) {
        return 0;
    }
    int[] nums = new int[index];
    nums[0] = 1;
    int curMax = 1, s2 = 0, s3 = 0, s5 = 0;
    for (int i = 1; i < index; i++) {
        int t2, t3, t5;
        for (; nums[s2] * 2 <= curMax; s2++) {
        }
        t2 = nums[s2] * 2;
        for (; nums[s3] * 3 <= curMax; s3++) {
        }
        t3 = nums[s3] * 3;
        for (; nums[s5] * 5 <= curMax; s5++) {
        }
        t5 = nums[s5] * 5;

        nums[i] = Math.min(Math.min(t2, t3), t5);
        curMax = nums[i];
        
    }

    return nums[index - 1];
}

题目描述

求出113的整数中1出现的次数,并算出1001300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

解答

暴力解法，不推荐

1
2
3
4
5
6
7
8
9
10
11
12
13

public int NumberOf1Between1AndN_Solution(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        String s = i + "";
        char[] chars = s.toCharArray();
        for (char c : chars) {
            if (c == '1') {
                count++;
            }
        }
    }
    return count;
}

网上题解

链接：https://www.nowcoder.com/questionTerminal/bd7f978302044eee894445e244c7eee6?answerType=1&f=discussion
来源：牛客网

1
2
3
4
5
6
7
8

public int NumberOf1Between1AndN_Solution(int n) {
    int cnt = 0;
    for (int m = 1; m <= n; m *= 10) {
        int a = n / m, b = n % m;
        cnt += (a + 8) / 10 * m + (a % 10 == 1 ? b + 1 : 0);
    }
    return cnt;
}

思路是分别计算个位、十位、百位……..上出现 1 的个数。

以 n =216为例：

个位上： 1 ，11，21，31，…..211。个位上共出现（216/10）+ 1个 1 。因为除法取整，210~216间个位上的1取不到，所以我们加8进位。你可能说为什么不加9，n=211怎么办，这里把最后取到的个位数为1的单独考虑，先往下看。

十位上：1019，110119，210216. 十位上可看成 求（216/10）=21 个位上的1的个数然后乘10。这里再次把最后取到的十位数为1的单独拿出来，即210216要单独考虑 ，个数为（216%10）+1 .这里加8就避免了判断的过程。

后面以此类推。

时间复杂度 O(logN)

1. 定义

一种 表示静态属性的 关键字 / 修饰符

2. 作用

共用、共享

能有此作用的原因分析：

1. Java中，任何变量 / 代码存储时，都是 在编译时 由系统自动分配内存
2. 在静态变量编译后，所分配的内存会一直存在，直到程序退出内存才会释放这个空间
3. 类加载时，JVM会把静态变量放到 方法区，被本类 & 本类的所有实例所共用

3. 具体使用

• Static静态修饰符可应用于：类、代码块、方法 & 变量
• 下面，我将详细分析

3.1 静态类

• 定义
  使用 Static关键字 修饰、定义 为 静态的 内部类

即：

1. 静态类又名为：静态内部类
2. 该类独立存在，形式上与外部类有内外关系，实际上则没有，本质是为了隐藏自身

• 具体使用 & 相关规则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * 1. 静态类的方法 = 静态 / 非静态
 *    (静态方法可在外层通过静态类调用，而非静态方法必须要创建类的对象后才能调用)
 * 2. 只能引用外部类的静态变量（static，即类变量）
 * 3. 注：
 *       a. 默认不持有外部类引用、使用不依赖于外部类（与外层类无绑定）：即使无创建外层类的对象，它一样存在
 *       b. 若一个内部类不是被定义成静态内部类，那么其成员变量 / 方法不能被定义成静态
 *       c. 静态内部类 & 非静态内部类在创建时有区别，下面会详细说明
 */

// 外部类
public class A {  
    // 静态内部类
    public static class B{  
    }  
    // 非静态内部类（即 普通）
    class C{  
    }  
}  

// 静态内部类b & 非静态内部类c 创建时的区别：
A a=new A(); 
A.B b=new A.B(); 
A.C c=a.new C();

• 静态内部类 与 内部类的区别

• 特别注意
  a. 加载一个类时，其内部类不会同时被加载。
  b. 一个类被加载时刻 = 当且仅当其某个静态成员被调用时（静态域、构造器、静态方法等）

3.2 静态代码块

• 定义
  类加载器加载类的最后1步（类初始化）时，执行类构造器()里需执行的一组语句

额外说明

1. 类初始化 = 真正开始执行类中定义Java程序代码 = 执行类构造器()
2. () = 由编译器自动收集类中所有类变量的赋值动作&静态语句块中的语句合并产生的
3. 与类构造函数（即实例构造器()）不同，()不需显式地调用父类构造器，虚拟机会保证子类的()执行前，父类的()已执行完毕

• 具体使用 & 相关规则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/**
 * 1. 代码块 使用 Static修饰
 * 2. 静态块只会在类加载到内存中时执行1次
 *    a. 若有多个static代码块，JVM将按照它们在类中出现的先后顺序依次执行
 *    b. 静态语句块中只能访问定义在静态语句块之前的变量，定义在它之后的变量可以赋值，但不能访问。如下实例所示
 */

 public class Test { 

 	 // 使用静态修饰的静态代码块
     static{ 
         i=0;  // 給变量赋值，可通过编译 
         System.out.print(i); // 非法， 提示：“非法向前引用” 
     } 

     static int i=1; 
  
 }

3.3 静态方法

• 定义
  使用 Static关键字 修饰、定义为静态的成员方法

也称：类方法

• 具体使用 & 相关规则

1
2
3
4
5
6
7
8
9
10
11
12

/**
 * 1. 可直接通过类名调用，也可通过对象实例调用
 *    （属于类，不属于实例）
 * 2. 任何的实例都可调用（方便共享、公用）
 * 3. 只能访问所属类的静态成员变量 & 方法、不能使用this、super关键字
 *   （this = 调用该函数的对象、但由于静态方法可以直接使用类名调用（即可能还没创建对象），所以不可使用this）
 */

// 静态方法的申明
public static void a(int param) {

}

3.4 静态变量

• 定义
  使用 Static关键字 修饰、定义为静态的成员变量

也称：类变量

• 具体使用 & 相关规则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

/**
 * 1. 静态变量在内存中只有1个拷贝：JVM只为静态分配1次内存
 *   a. 全部对象共用这个static关键字修饰的成员变量，方便对象间共享，节省内存
 *   b. 未被Static修饰的成员变量 = 实例变量：每创建1个实例，JVM就会为实例变量分配1次内存，实例变量在内存中可以有多个拷贝（但互相不影响，更加灵活）
 * 2. 可用类名直接访问：在加载类的过程中完成静态变量的内存分配，（也可通过对象实例访问）
 *  （属于类，不属于实例）
 * 3. 非线程安全：因静态变量被类的所有实例共用
 * 4. 局部变量也能被声明为static
 */

// 静态方法的申明
public class A {  

    private static int count = 0;  //静态变量的申明
   
}

• 静态变量与实例变量的区别

至此，关于Java中的静态 Static关键字讲解完毕。

4. 总结

• 本文主要讲解了Java中的静态 Static关键字，总结如下：

题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

输出描述:

1

对应每个测试案例，输出两个数，小的先输出。

解答

两层遍历，O(N^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
    ArrayList<Integer> ans = new ArrayList<>();
    for (int i = 0; i < array.length; i++) {

        for (int j = array.length - 1; j >= 0; j--) {
            if (array[i] + array[j] < sum) {
                break;
            } else if (array[i] + array[j] == sum) {
                ans.add(array[i]);
                ans.add(array[j]);
                return ans;
            }
        }
    }
    return ans;
}

更快的做法，O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
    ArrayList<Integer> ans = new ArrayList<>();
    int i = 0, j = array.length - 1;
    while (i != j && i < array.length && j > 0) {
        if (array[i] + array[j] < sum) {
            i++;
        } else if (array[i] + array[j] > sum) {
            j--;
        } else {
            ans.add(array[i]);
            ans.add(array[j]);
            break;
        }
    }
    return ans;

}

转载文章 原文地址

在很多技术中都使用到了零拷贝技术，比如javaNIO、kafka、Netty、Linux等等。作为一个非常重要的知识点，而且又是高频面试题，有必要从零开始好好地认识一下。

一、什么是零拷贝？

1、从一个案例说起

为了解释这个概念，我们先要从一个需求说起，说某天某领导给你下发了一个任务，完成一个从文件中读取数据，并传输到网络上的一个小程序。代码很简单：

首先我们在我们的操作系统中找到这个文件，然后把数据先读到缓冲区，最后把缓冲区的数据发送到网络上。

代码是很简单，现在我们考虑一下，这个数据从电脑到网络整个传输的过程：

现在我们可以看到1->2->3->4的整个过程一共经历了四次拷贝的方式， 但是真正消耗资源和浪费时间的是第二次和第三次，因为这两次都需要经过我们的CPU拷贝，而且还需要内核态和用户态之间的来回切换。 想想看，我们的CPU资源是多么宝贵，要处理大量的任务。还要去拷贝大量的数据。如果能把CPU的这两次拷贝给去除掉，岂不快哉！！！既能节省CPU资源，还可以避免内核态和用户态之间的切换。

这里还要先说一下用户态和内核态的区别：

• 处于用户态执行时，进程所能访问的内存空间和对象受到限制，其所处于占有的处理器是可被抢占的
• 处于内核态执行时，则能访问所有的内存空间和对象，且所占有的处理器是不允许被抢占的。

2、优化方案

要去除第二次和第三次之间的拷贝，Linux开发人员也早就注意到了这个问题，于是在linux 2.1内核中，添加了 “ 数据被copy到socket buffer”的动作，于是我们的javaNIO，可以直接调用transferTo()的方法，就可以实现这种现象。

现在一看，感觉性能资源都得到了很大的提升，不过现在还不并不是完美的。因为这三次拷贝还用到了CPU的拷贝技术，就是第二次。不过不要担心。Linux开发人员比我们更加深谋远虑。

3、零拷贝优化方案

在Linux2.4 内核做了优化，取而代之的是只包含关于数据的位置和长度的信息的描述符被追加到了socket buffer 缓冲区中。 DMA引擎直接把数据从内核缓冲区传输到协议引擎 （protocol engine），从而消除了最后一次CPU copy。经过上述过程，数据只经过了2次copy就从磁盘传送出去了。这个才是真正的Zero-Copy

注意：这里的零拷贝其实是根据内核状态划分的，在这里没有经过CPU的拷贝，数据在用户态的状态下，经历了零次拷贝，所以才叫做零拷贝，但不是说不拷贝。

OK。 现在我们已经了解了什么是零拷贝技术，下面我们再说一下那些数据结构会用到零拷贝技术。

二、哪些地方会用到零拷贝技术

1、java的NIO

先说java，是因为要给下面的netty做铺垫，在 Java NIO 中的通道（Channel）就相当于操作系统的内核空间（kernel space）的缓冲区，而缓冲区（Buffer）相当于操作系统的用户空间（user space）中的用户缓冲区（user buffer）。

堆外内存（DirectBuffer）在使用后需要应用程序手动回收，而堆内存（HeapBuffer）的数据在 GC 时可能会被自动回收。因此，在使用 HeapBuffer 读写数据时，为了避免缓冲区数据因为 GC 而丢失，NIO 会先把 HeapBuffer 内部的数据拷贝到一个临时的 DirectBuffer 中的本地内存（native memory），这个拷贝涉及到 sun.misc.Unsafe.copyMemory() 的调用，背后的实现原理与 memcpy() 类似。最后，将临时生成的 DirectBuffer 内部的数据的内存地址传给 I/O 调用函数，这样就避免了再去访问 Java 对象处理 I/O 读写。

（1）MappedByteBuffer

MappedByteBuffer是 NIO 基于内存映射（mmap）这种零拷贝方式的提供的一种实现，意思是把一个文件从 position 位置开始的 size 大小的区域映射为内存映像文件。这样之添加地址映射，而不进行拷贝。

（2）DirectByteBuffer

DirectByteBuffer 的对象引用位于 Java 内存模型的堆里面，JVM 可以对 DirectByteBuffer 的对象进行内存分配和回收管理，是 MappedByteBuffer 的具体实现类。因此同样具有零拷贝技术。

（3）FileChannel

FileChannel 定义了 transferFrom() 和 transferTo() 两个抽象方法，它通过在通道和通道之间建立连接实现数据传输的。

我们直接看Linux2.4的版本，socket缓冲区做了调整，DMA带收集功能。

（1）DMA从硬盘（外部设备）拷贝至内核缓冲区

（2）将数据的位置和长度的信息的描述符增加至socket缓冲区（位于内核空间）

（3）DMA将数据从内核缓冲区拷贝至socket协议引擎

这个复制过程是零拷贝过程。

2、Netty

Netty 中的零拷贝和上面提到的操作系统层面上的零拷贝不太一样, 我们所说的 Netty 零拷贝完全是基于（Java 层面）用户态的。

（1）Netty 通过 DefaultFileRegion 类对FileChannel的 tranferTo()方法进行包装，相当于是间接的通过java进行零拷贝。

（2）我们的数据传输一般都是通过TCP/IP协议实现的，在实际应用中，很有可能 一条完整的消息被分割为多个数据包进行网络传输，而单个的数据包对你而言是没有意义的，只有当这些数据包组成一条完整的消息时你才能做出正确的处理 ，而Netty可以通过零拷贝的方式将这些数据包组合成一条完整的消息供你来使用。

此时零拷贝的作用范围仅在用户空间中。那Netty是如何实现的呢？为此我们就要找到Netty进行数据传输的接口，这个接口一定包含了可以实现零拷贝的功能，这个接口就是ChannelBuffer。

既然有接口肯定就有实现类，一个最主要的实现类是CompositeChannelBuffer，这个类的主要作用是将多个ChannelBuffer组成一个虚拟的ChannelBuffer来进行操作

为什么说是虚拟的呢，因为CompositeChannelBuffer并没有将多个ChannelBuffer真正的组合起来，而只是保存了他们的引用，这样就避免了数据的拷贝，实现了Zero Copy。

（3）ByteBuf 可以通过 wrap 操作把byte[]、ByteBuf、ByteBuffer 包装成一个ByteBuf 对象, 进而避免了拷贝操作

（4）ByteBuf支持 slice 分片操作, 因此可以将 ByteBuf 分解为多个共享同一个存储区域的ByteBuf，避免了内存的拷贝

3、kafka

Kafka 的索引文件使用的是 mmap + write 方式，数据文件使用的是sendfile方式。适用于系统日志消息这种高吞吐量的大块文件的数据持久化和传输。

如果有10个消费者，传统方式下，数据复制次数为4*10=40次，而使用“零拷贝技术”只需要1+10=11次，一次为从磁盘复制到页面缓存，10次表示10个消费者各自读取一次页面缓存。

[原文地址]（https://blog.csdn.net/cringkong/article/details/80274148）

一.Linux操作系统中的零拷贝

1.1 先从Linux的普通I/O过程说起

这是一个从磁盘文件中读取并且通过Socket写出的过程，对应的系统调用如下。

1
2

read(file, tmp_buf, len);
write(socket, tmp_buf, len);

1. 程序使用read()系统调用，系统由用户态转换为内核态，磁盘中的数据由DMA（Direct memory access）的方式读取到内核读缓冲区（kernel buffer）。DMA过程中CPU不需要参与数据的读写，而是DMA处理器直接将硬盘数据通过总线传输到内存中。
2. 系统由内核态转为用户态，当程序要读的数据已经完全存入内核读缓冲区以后，程序会将数据由内核读缓冲区，写入到用户缓冲区，这个过程需要CPU参与数据的读写。
3. 程序使用write()系统调用，系统由用户态切换到内核态，数据从用户缓冲区写入到网络缓冲区（Socket Buffer），这个过程需要CPU参与数据的读写。
4. 系统由内核态切换到用户态，网络缓冲区的数据通过DMA的方式传输到网卡的驱动（存储缓冲区）中（protocol engine）
   可以看到，普通的拷贝过程经历了四次内核态和用户态的切换（上下文切换），两次CPU从内存中进行数据的读写过程，这种拷贝过程相对来说比较消耗系统资源。

程序使用read()系统调用，系统由用户态转换为内核态，磁盘中的数据由DMA（Direct memory access）的方式读取到内核读缓冲区（kernel buffer）。DMA过程中CPU不需要参与数据的读写，而是DMA处理器直接将硬盘数据通过总线传输到内存中。
系统由内核态转为用户态，当程序要读的数据已经完全存入内核读缓冲区以后，程序会将数据由内核读缓冲区，写入到用户缓冲区，这个过程需要CPU参与数据的读写。
程序使用write()系统调用，系统由用户态切换到内核态，数据从用户缓冲区写入到网络缓冲区（Socket Buffer），这个过程需要CPU参与数据的读写。
系统由内核态切换到用户态，网络缓冲区的数据通过DMA的方式传输到网卡的驱动（存储缓冲区）中（protocol engine）
可以看到，普通的拷贝过程经历了四次内核态和用户态的切换（上下文切换），两次CPU从内存中进行数据的读写过程，这种拷贝过程相对来说比较消耗系统资源。

1.2 内存映射方式I/O

1
2

tmp_buf = mmap(file, len);
write(socket, tmp_buf, len);

这是使用的系统调用方法，这种方式的I/O原理就是将用户缓冲区(user buffer)的内存地址和内核缓冲区(kernel buffer) 的内存地址做一个映射，也就是说系统在用户态可以直接读取并操作内核空间的数据。

1. mmap()系统调用首先会使用DMA的方式将磁盘数据读取到内核缓冲区，然后通过内存映射的方式，使用户缓冲区和内核读缓冲区的内存地址为同一内存地址，也就是说不需要CPU再讲数据从内核读缓冲区复制到用户缓冲区。
2. 当使用write()系统调用的时候，cpu将内核缓冲区（等同于用户缓冲区）的数据直接写入到网络发送缓冲区（socket buffer），然后通过DMA的方式将数据传入到网卡驱动程序中准备发送。

可以看到这种内存映射的方式减少了CPU的读写次数，但是用户态到内核态的切换（上下文切换）依旧有四次，这种方式可以让应用程序对数据进行相应的读写操作。

1.3 内核空间内部传输I/O

1

sendfile(socket, file, len);

通过sendfile()系统调用，可以做到内核空间内部直接进行I/O传输。

1. sendfile()系统调用也会引起用户态到内核态的切换，与内存映射方式不同的是，用户空间此时是无法看到或修改数据内容，也就是说这是一次完全意义上的数据传输过程。
2. 从磁盘读取到内存是DMA的方式，从内核读缓冲区读取到网络发送缓冲区，依旧需要CPU参与拷贝，而从网络发送缓冲区到网卡中的缓冲区依旧是DMA方式。

依旧有一次CPU进行数据拷贝，两次用户态和内核态的切换操作，相比较于内存映射的方式有了很大的进步，但问题是程序不能对数据进行修改，而只是单纯地进行了一次数据的传输过程。

1.4 升级版-内核空间内部传输I/O

依旧是系统调用sendfile()

1

sendfile(socket, file, len);

在 Linux 内核 2.4 及后期版本中，针对套接字缓冲区描述符做了相应调整，支持了DMA自带了收集功能，对于用户方面，用法还是一样的，但是内部操作已经发生了改变。

可以看到，这是真正意义上的零拷贝，因为其间CPU已经不参与数据的拷贝过程，当然这样的过程需要硬件的支持才能实现。

借助于硬件上的帮助，我们是可以办到的。之前我们是把页缓存的数据拷贝到socket缓存中，实际上，我们仅仅需要把缓冲区描述符传到socket缓冲区，再把数据长度传过去，这样DMA控制器直接将页缓存中的数据打包发送到网络中就可以了。

系统调用sendfile()发起后，磁盘数据通过DMA方式读取到内核缓冲区，内核缓冲区中的数据通过DMA聚合网络缓冲区，然后一齐发送到网卡中。
可以看到在这种模式下，是没有一次CPU进行数据拷贝的，所以就做到了真正意义上的零拷贝

1.5 后续优化-splice()系统调用

splice() 系统调用和 sendfile() 非常类似，用户应用程序必须拥有两个已经打开的文件描述符，一个用于表示输入设备，一个用于表示输出设备。与 sendfile() 不同的是，splice() 允许任意两个文件之间互相连接，而并不只是文件到 socket 进行数据传输。对于从一个文件描述符发送数据到 socket 这种特例来说，一直都是使用 sendfile() 这个系统调用，而 splice 一直以来就只是一种机制，它并不仅限于 sendfile() 的功能。也就是说，sendfile() 只是 splice() 的一个子集，在 Linux 2.6.23 中，sendfile() 这种机制的实现已经没有了，但是这个 API 以及相应的功能还存在，只不过 API 以及相应的功能是利用了 splice() 这种机制来实现的。

总体来讲splice()是Linux 2.6.23 内核版本中替换sendfile()系统调用的一个方法，它不仅支持文件到Socket的直接传输，也支持文件到文件的直接传输I/O，但是其底层的传输过程和sendfile()并无区别，也就是上面那两张图。

二.JavaNIO中的零拷贝

真是没想到对于操作系统中的零拷贝技术要占这么多内容，但是不说又不行，因为Java中的零拷贝也是通过操作系统的系统调用来实现的。

2.1 NIO中内存映射方式I/O

操作系统的读写缓冲区和JavaNIO没有关系任何关系，操作系统的读写缓冲区（Linux中就是PageCache）是内核中直接和IO设备驱动交互的内存区域，程序员平时是接触不到的

我们来看一段代码：

1
2
3
4

File file = new File("test.zip");
RandomAccessFile raf = new RandomAccessFile(file, "rw");
FileChannel fileChannel = raf.getChannel();
MappedByteBuffer buffer = fileChannel.map(FileChannel.MapMode.READ_ONLY, 0, fileChannel.size());

NIO中的FileChannel.map()方法其实就是采用了操作系统中的内存映射方式。

内存地址映射其实是操作系统将内存地址和磁盘文件做一个映射，读写这块内存，相当于直接对磁盘文件进行读写，但是实际上的读还是要经过OS读取到内存PageCache中，写过程也需要OS自动进行脏页置换到磁盘中。

这种方式适合读取大文件，同时也能对文件内容进行更改，但是如果其后要通过SocketChannel发送，还是需要CPU进行数据的拷贝。

1
2
3
4
5

processData();
// 数据处理完成以后，打卡一个SocketChannel
SocketChannel socketChannel = SocketChannel.open(new InetSocketAddress("", 1234));
// 这时依旧需要CPU将内核缓冲区的内容拷贝到网络缓冲区
socketChannel.write(buffer);

2.2 NIO中的零拷贝

1
2
3
4
5
6

File file = new File("test.zip");
RandomAccessFile raf = new RandomAccessFile(file, "rw");
FileChannel fileChannel = raf.getChannel();
SocketChannel socketChannel = SocketChannel.open(new InetSocketAddress("", 1234));
// 直接使用了transferTo()进行通道间的数据传输
fileChannel.transferTo(0, fileChannel.size(), socketChannel);

这种方式就是NIO中的零拷贝，我们来分析一下其中原理：

1. NIO中的Buffer都在用户空间中，包括DirectBuffer，也是C语言malloc出来的一块内存。

2. transferTo()的实现方式就是通过系统调用sendfile()（当然这是Linux中的系统调用，Windows中系统调用有所不同），根据我们上面所写说这个过程是效率远高于从内核缓冲区到用户缓冲区的读写的。

同理transferFrom()也是这种实现方式。

三. 补充内容

这篇文章写的时间已经有一年多了，在这一年里我学习了更多中间件的知识，也认识到了更多现实，首先就是Java语言得IO效率比起C和C++是远远不如的，因为有JVM的存在就导致了Java的IO永远要比其他语言多一层内存交换，但是Java在中间件方面还是大有可为的，比如说消息队列，kafka就是Java写的，吞吐量和稳定性都达到了令人满意的效果。

————————————————
版权声明：本文为CSDN博主「CringKong」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/cringkong/article/details/80274148

转载，原文地址 作者： 阮一峰

今天中午，我突然想搞清楚 Unicode 和 UTF-8 之间的关系，就开始查资料。

这个问题比我想象的复杂，午饭后一直看到晚上9点，才算初步搞清楚。

下面就是我的笔记，主要用来整理自己的思路。我尽量写得通俗易懂，希望能对其他朋友有用。毕竟，字符编码是计算机技术的基石，想要熟练使用计算机，就必须懂得一点字符编码的知识。

一、ASCII 码

我们知道，计算机内部，所有信息最终都是一个二进制值。每一个二进制位（bit）有0和1两种状态，因此八个二进制位就可以组合出256种状态，这被称为一个字节（byte）。也就是说，一个字节一共可以用来表示256种不同的状态，每一个状态对应一个符号，就是256个符号，从00000000到11111111。

上个世纪60年代，美国制定了一套字符编码，对英语字符与二进制位之间的关系，做了统一规定。这被称为 ASCII 码，一直沿用至今。

ASCII 码一共规定了128个字符的编码，比如空格SPACE是32（二进制00100000），大写的字母A是65（二进制01000001）。这128个符号（包括32个不能打印出来的控制符号），只占用了一个字节的后面7位，最前面的一位统一规定为0。

二、非 ASCII 编码

英语用128个符号编码就够了，但是用来表示其他语言，128个符号是不够的。比如，在法语中，字母上方有注音符号，它就无法用 ASCII 码表示。于是，一些欧洲国家就决定，利用字节中闲置的最高位编入新的符号。比如，法语中的é的编码为130（二进制10000010）。这样一来，这些欧洲国家使用的编码体系，可以表示最多256个符号。

但是，这里又出现了新的问题。不同的国家有不同的字母，因此，哪怕它们都使用256个符号的编码方式，代表的字母却不一样。比如，130在法语编码中代表了é，在希伯来语编码中却代表了字母Gimel (ג)，在俄语编码中又会代表另一个符号。但是不管怎样，所有这些编码方式中，0–127表示的符号是一样的，不一样的只是128–255的这一段。

至于亚洲国家的文字，使用的符号就更多了，汉字就多达10万左右。一个字节只能表示256种符号，肯定是不够的，就必须使用多个字节表达一个符号。比如，简体中文常见的编码方式是 GB2312，使用两个字节表示一个汉字，所以理论上最多可以表示 256 x 256 = 65536 个符号。

中文编码的问题需要专文讨论，这篇笔记不涉及。这里只指出，虽然都是用多个字节表示一个符号，但是GB类的汉字编码与后文的 Unicode 和 UTF-8 是毫无关系的。

三. Unicode

正如上一节所说，世界上存在着多种编码方式，同一个二进制数字可以被解释成不同的符号。因此，要想打开一个文本文件，就必须知道它的编码方式，否则用错误的编码方式解读，就会出现乱码。为什么电子邮件常常出现乱码？就是因为发信人和收信人使用的编码方式不一样。

可以想象，如果有一种编码，将世界上所有的符号都纳入其中。每一个符号都给予一个独一无二的编码，那么乱码问题就会消失。这就是 Unicode，就像它的名字都表示的，这是一种所有符号的编码。

Unicode 当然是一个很大的集合，现在的规模可以容纳100多万个符号。每个符号的编码都不一样，比如，U+0639表示阿拉伯字母Ain，U+0041表示英语的大写字母A，U+4E25表示汉字严。具体的符号对应表，可以查询unicode.org，或者专门的汉字对应表。

四、Unicode 的问题

需要注意的是，Unicode 只是一个符号集，它只规定了符号的二进制代码，却没有规定这个二进制代码应该如何存储。

比如，汉字严的 Unicode 是十六进制数4E25，转换成二进制数足足有15位（100111000100101），也就是说，这个符号的表示至少需要2个字节。表示其他更大的符号，可能需要3个字节或者4个字节，甚至更多。

这里就有两个严重的问题，第一个问题是，如何才能区别 Unicode 和 ASCII ？计算机怎么知道三个字节表示一个符号，而不是分别表示三个符号呢？第二个问题是，我们已经知道，英文字母只用一个字节表示就够了，如果 Unicode 统一规定，每个符号用三个或四个字节表示，那么每个英文字母前都必然有二到三个字节是0，这对于存储来说是极大的浪费，文本文件的大小会因此大出二三倍，这是无法接受的。

它们造成的结果是：1）出现了 Unicode 的多种存储方式，也就是说有许多种不同的二进制格式，可以用来表示 Unicode。2）Unicode 在很长一段时间内无法推广，直到互联网的出现。

五、UTF-8

互联网的普及，强烈要求出现一种统一的编码方式。UTF-8 就是在互联网上使用最广的一种 Unicode 的实现方式。其他实现方式还包括 UTF-16（字符用两个字节或四个字节表示）和 UTF-32（字符用四个字节表示），不过在互联网上基本不用。重复一遍，这里的关系是，UTF-8 是 Unicode 的实现方式之一。

UTF-8 最大的一个特点，就是它是一种变长的编码方式。它可以使用1~4个字节表示一个符号，根据不同的符号而变化字节长度。

UTF-8 的编码规则很简单，只有二条：

1）对于单字节的符号，字节的第一位设为0，后面7位为这个符号的 Unicode 码。因此对于英语字母，UTF-8 编码和 ASCII 码是相同的。

2）对于n字节的符号（n > 1），第一个字节的前n位都设为1，第n + 1位设为0，后面字节的前两位一律设为10。剩下的没有提及的二进制位，全部为这个符号的 Unicode 码。

下表总结了编码规则，字母x表示可用编码的位。

1 2 3 4 5 6 7

Unicode符号范围 | UTF-8编码方式 (十六进制) | （二进制） ----------------------+--------------------------------------------- 0000 0000-0000 007F | 0xxxxxxx 0000 0080-0000 07FF | 110xxxxx 10xxxxxx 0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx 0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

跟据上表，解读 UTF-8 编码非常简单。如果一个字节的第一位是0，则这个字节单独就是一个字符；如果第一位是1，则连续有多少个1，就表示当前字符占用多少个字节。

下面，还是以汉字严为例，演示如何实现 UTF-8 编码。

严的 Unicode 是4E25（100111000100101），根据上表，可以发现4E25处在第三行的范围内（0000 0800 - 0000 FFFF），因此严的 UTF-8 编码需要三个字节，即格式是1110xxxx 10xxxxxx 10xxxxxx。然后，从严的最后一个二进制位开始，依次从后向前填入格式中的x，多出的位补0。这样就得到了，严的 UTF-8 编码是11100100 10111000 10100101，转换成十六进制就是E4B8A5。

六、Unicode 与 UTF-8 之间的转换

通过上一节的例子，可以看到严的 Unicode码 是4E25，UTF-8 编码是E4B8A5，两者是不一样的。它们之间的转换可以通过程序实现。

Windows平台，有一个最简单的转化方法，就是使用内置的记事本小程序notepad.exe。打开文件后，点击文件菜单中的另存为命令，会跳出一个对话框，在最底部有一个编码的下拉条。

里面有四个选项：ANSI，Unicode，Unicode big endian和UTF-8。

1）ANSI是默认的编码方式。对于英文文件是ASCII编码，对于简体中文文件是GB2312编码（只针对 Windows 简体中文版，如果是繁体中文版会采用 Big5 码）。

2）Unicode编码这里指的是notepad.exe使用的 UCS-2 编码方式，即直接用两个字节存入字符的 Unicode 码，这个选项用的 little endian 格式。

3）Unicode big endian编码与上一个选项相对应。我在下一节会解释 little endian 和 big endian 的涵义。

4）UTF-8编码，也就是上一节谈到的编码方法。

选择完”编码方式”后，点击”保存”按钮，文件的编码方式就立刻转换好了。

七、Little endian 和 Big endian

上一节已经提到，UCS-2 格式可以存储 Unicode 码（码点不超过0xFFFF）。以汉字严为例，Unicode 码是4E25，需要用两个字节存储，一个字节是4E，另一个字节是25。存储的时候，4E在前，25在后，这就是 Big endian 方式；25在前，4E在后，这是 Little endian 方式。

这两个古怪的名称来自英国作家斯威夫特的《格列佛游记》。在该书中，小人国里爆发了内战，战争起因是人们争论，吃鸡蛋时究竟是从大头(Big-endian)敲开还是从小头(Little-endian)敲开。为了这件事情，前后爆发了六次战争，一个皇帝送了命，另一个皇帝丢了王位。

第一个字节在前，就是”大头方式”（Big endian），第二个字节在前就是”小头方式”（Little endian）。

那么很自然的，就会出现一个问题：计算机怎么知道某一个文件到底采用哪一种方式编码？

Unicode 规范定义，每一个文件的最前面分别加入一个表示编码顺序的字符，这个字符的名字叫做”零宽度非换行空格”（zero width no-break space），用FEFF表示。这正好是两个字节，而且FF比FE大1。

如果一个文本文件的头两个字节是FE FF，就表示该文件采用大头方式；如果头两个字节是FF FE，就表示该文件采用小头方式。

八、实例

下面，举一个实例。

打开”记事本”程序notepad.exe，新建一个文本文件，内容就是一个严字，依次采用ANSI，Unicode，Unicode big endian和UTF-8编码方式保存。

然后，用文本编辑软件UltraEdit 中的”十六进制功能”，观察该文件的内部编码方式。

1）ANSI：文件的编码就是两个字节D1 CF，这正是严的 GB2312 编码，这也暗示 GB2312 是采用大头方式存储的。

2）Unicode：编码是四个字节FF FE 25 4E，其中FF FE表明是小头方式存储，真正的编码是4E25。

3）Unicode big endian：编码是四个字节FE FF 4E 25，其中FE FF表明是大头方式存储。

4）UTF-8：编码是六个字节EF BB BF E4 B8 A5，前三个字节EF BB BF表示这是UTF-8编码，后三个E4B8A5就是严的具体编码，它的存储顺序与编码顺序是一致的。

九、延伸阅读

• The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets（关于字符集的最基本知识）
• 谈谈Unicode编码
• RFC3629：UTF-8, a transformation format of ISO 10646（如果实现UTF-8的规定）

（完）

题目描述

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

解答

排序规则：比较两个字符串s1, s2大小的时候，先将它们拼接起来，比较s1+s2,和s2+s1哪个大，如果s1+s2大，那说明s2应该放前面，所以按这个规则，s2就应该排在s1前面。

TODO优化：冒泡排序可以改为快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public String PrintMinNumber(int[] numbers) {
    String[] strings = new String[numbers.length];
    for (int i = 0; i < numbers.length; i++) {
        strings[i] = String.valueOf(numbers[i]);
    }
    sort(strings);
    StringBuilder builder = new StringBuilder();
    for (String string : strings) {
        builder.append(string);
    }
    return builder.toString();
}

private void sort(String[] strings) {
    for (int i = strings.length - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (cmp(strings[j], strings[j + 1])) {
                String tmp = strings[j];
                strings[j] = strings[j + 1];
                strings[j + 1] = tmp;
            }
        }
    }
}

private boolean cmp(String str1, String str2) {
    String s1 = str1 + str2, s2 = str2 + str1;
    return s1.compareTo(s2) > 0;
}

题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

解答

使用HashMap的话空间复杂度为O(N)，这里使用异或抵消两个相同的数，空间复杂度可降为O(1)

时间复杂度都为O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
    int nor = 0;
    for (int i : array) {
        nor = nor ^ i;
    }
    int lastN = 0;//nor中1出现的最低位
    for (; (nor & 1) == 0; nor = nor >> 1) {
        lastN++;
    }
    /** 将array分为两个子数组分别异或 */
    int ans1 = 0, ans2 = 0;
    for (int i : array) {
        if (((i >> lastN) & 1) == 0) {
            ans1 ^= i;
        } else {
            ans2 ^= i;
        }
    }
    num1[0] = ans1;
    num2[0] = ans2;
}

网上题解

链接：https://www.nowcoder.com/questionTerminal/e02fdb54d7524710a7d664d082bb7811?answerType=1&f=discussion
来源：牛客网

简单方法

可以先用最简单的HashMap的方法来做，这样主要是为了练习Map的用法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import java.util.HashMap;
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        //哈希算法
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i=0; i < array.length; i++){
            if(map.containsKey(array[i]))
                map.put(array[i],2);
            else
                map.put(array[i],1);
        }
        int count = 0;
        for(int i=0; i < array.length; i++){
            if(map.get(array[i]) == 1){
                if(count == 0){
                    num1[0] =  array[i];
                    count++;
                }else
                    num2[0] =  array[i];
            }
        }

    }
}

比较考验智商的做法

比较好用的剑指offer的做法：
首先：位运算中异或的性质：两个相同数字异或=0，一个数和0异或还是它本身。
当只有一个数出现一次时，我们把数组中所有的数，依次异或运算，最后剩下的就是落单的数，因为成对儿出现的都抵消了。

依照这个思路，我们来看两个数（我们假设是AB）出现一次的数组。我们首先还是先异或，剩下的数字肯定是A、B异或的结果，这个结果的二进制中的1，表现的是A和B的不同的位。我们就取第一个1所在的位数，假设是第3位，接着把原数组分成两组，分组标准是第3位是否为1。如此，相同的数肯定在一个组，因为相同数字所有位都相同，而不同的数，肯定不在一组。然后把这两个组按照最开始的思路，依次异或，剩余的两个结果就是这两个只出现一次的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {

        int xor1 = 0;
        for(int i=0; i < array.length; i++)
            xor1 = xor1^array[i];
        //在xor1中找到第一个不同的位对数据进行分类，分类为两个队列对数据进行异或求和找到我们想要的结果
        int index = 1;
        while((index & xor1)==0)
            index = index <<1;//因为可能有多个位为1所以需要求一下位置
        int result1 = 0;
        int result2 = 0;
        for(int i=0; i < array.length; i++){
            if((index & array[i]) == 0)
                result1 = result1^array[i];
            else
                result2 = result2^array[i];
        }
        num1[0] = result1;
        num2[0] = result2;
}