Eric's Blogs

题目描述

将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0

输入描述:

1

输入一个字符串,包括数字字母符号,可以为空

输出描述:

1

如果是合法的数值表达则返回该数字，否则返回0

示例1

输入

1
2

+2147483647
1a33

输出

1
2

2147483647
0

解答

不用库函数的版本待补充

1
2
3
4
5
6
7
8
9

public int StrToInt(String str) {
    int x=0;
    try {
         x=Integer.valueOf(str);
    }catch (Exception e){
        return 0;
    }
    return x;
}

官方题解

题目意思很明确，这道题难就难在边界的考察。如果对于一般规则的数字“字符串”转化为数字都很容易，比如：

对于“123456”可以利用如下代码进行转化：

1
2
3
4

int ans = 0;
for (int i=0; i<str.size(); ++i) {
    ans = ans * 10 + (str[i] - '0');
}

int的范围为
如果超过了这两个范围该怎么办？
其实也很简单，首先判断这个数的正负，如果正数，超过了INT_MAX，就设置为INT_MAX，如果是负数，首先我们不考虑负号，如果超过了INT_MAX+1, 则就置为INT_MAX+1, 最后再根据正负号，来加负号。
代码如下：

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

bool neg = str[i]=='-' ? true : false;
i = isdigit(str[i]) ? i : i+1;
long long ans = 0L; // 因为INT_MAX+1超过了int的范围

while (i < len && isdigit(str[i])) {
    ans = ans * 10 + (str[i++]-'0');

    if (!neg && ans > INT_MAX) {
        ans = INT_MAX;
        break; //因为此处以为最大值，所以直接break
    }
    if (neg && ans > 1L + INT_MAX) {
        ans = 1L + INT_MAX;
        break;
    }
}

最后再考虑一些特殊情况即可。
代码如下：

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

class Solution {
public:
    int StrToInt(string str) {
        const int len = str.length();
        if (len == 0) return 0;
        int i = 0;
        while (i < len && str[i] == ' ') { ++i; } // 排除开头的空格
        if (i == len) return 0;
        if (!isdigit(str[i]) && str[i] != '+' && str[i] != '-') return 0;
        bool neg = str[i]=='-' ? true : false;
        i = isdigit(str[i]) ? i : i+1;
        long long ans = 0L;

        while (i < len && isdigit(str[i])) {
            ans = ans * 10 + (str[i++]-'0');

            if (!neg && ans > INT_MAX) {
                ans = INT_MAX;
                break;
            }
            if (neg && ans > 1L + INT_MAX) {
                ans = 1L + INT_MAX;
                break;
            }
        }
        if (i != len) return 0; // 不要此处，就是atoi()库函数的实现
        return !neg ? static_cast<int>(ans) : static_cast<int>(-ans);
    }
};

但是本题有个样例：

感觉很无语。
时间复杂度：O(N)
空间复杂度：O(1)

题目描述

给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…A[i-1]*A[i+1]…*A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2];）

解答

不能用除法,只能尽量减少乘法次数

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

public int[] multiply(int[] A) {
    int[] B = new int[A.length];
    int[] D = new int[A.length];
    D[D.length - 1] = 1;
    for (int i = D.length - 2; i >= 0; i--) {
        D[i] = D[i + 1] * A[i + 1];
    }
    int C = 1;
    for (int i = 0; i < B.length; i++) {
        B[i] = C * D[i];
        C *= A[i];
    }
    return B;
}

官方题解

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

方法：

根据题目描述，如果可以使用除法，就很简单。但是要求不能使用。

假设：
left[i] = A[0]*...*A[i-1]
right[i] = A[i+1]*...*A[n-1]
所以：
B[i] = left[i] * right[i]

这样就避免使用了除法。但是如果对每个B[i], 0<=i<n,都这么求，显然时间复杂度太高。

我们把整个结果画到下面图：

可知：
left[i+1] = A[0]*...A[i-1]*A[i]
right[i+1] = A{i+2]*...*A[n-1]

于是，
left[i+1] = left[i] * A[i]
right[i] = right[i+1] * A[i+1]

所以，我们可以先把所有的left[i]求出，right[i]求出。

代码如下：

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

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> B(A.size(), 1);
        for (int i=1; i<A.size(); ++i) {
            B[i] = B[i-1] * A[i-1]; // left[i]用B[i]代替
        }
        int tmp = 1;
        for (int j=A.size()-2; j>=0; --j) {
            tmp *= A[j+1]; // right[i]用tmp代替
            B[j] *= tmp;
        }
        return B;
    }
};

时间复杂度：O(N)
空间复杂度: O(1)

转载 原文链接

什么是hashcode,hashcode的作用是什么

hashcode并不是java中独有的。设想一下，如果让你设计一个算法，根据关键码去得到一个集合中的某个值或者这个关键码所在的位置。普通的做法就是挨个比较，高级一点的使用二分检索或者树形检索等算法。但是以上的检索算法都跟集合的长度N有关，当问题规模N很大时，这些检索的效率可能十分低下。

理想的情况是，根据关键码，我们就可以定位记录所在的位置，而不用去挨个进行比较。也就是说，在关键码与记录存放的位置之间做一种映射。这个映射的方法就是hash(哈希)函数，或者叫散列函数，也就是java中的hashCode()方法，他所返回的值就是hashcode，根据hashcode可以找到记录的位置。

按照散列的存储方式构造的存储结构叫做散列表。散列表中的一个位置称之为一个槽。

hashCode()方法存在于java.lang.Object类当中，任何类都可以继承修改这个方法。hashCode()方法返回调用它的实例的hashCode值，是个int值。

注：以下代码均来自jdk1.7

String中hashCode()方法的实现：

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

public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
}

什么是equals(Object obj)方法

equals(Object obj)方法同样来自Object类。在Object类中，他是这样实现的：

1
2
3

public boolean equals(Object obj) {
        return (this == obj);
}

也就是说，默认的equals(Object obj)方法直接将要比较的两个对象的内存地址进行了比较，一致则返回true。

这个方法主要用来实现两个对象间的比较，确认他们在逻辑上是否相等。我们同样可以实现自己的equals(Object obj)方法。

String中equals(Object obj)方法的实现：

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

public boolean equals(Object anObject) {
        if (this == anObject) {
            return true;
        }
        if (anObject instanceof String) {
            String anotherString = (String) anObject;
            int n = value.length;
            if (n == anotherString.value.length) {
                char v1[] = value;
                char v2[] = anotherString.value;
                int i = 0;
                while (n-- != 0) {
                    if (v1[i] != v2[i])
                            return false;
                    i++;
                }
                return true;
            }
        }
        return false;
}

在java中hashcode方法与equals方法的作用

首先看一下HashMap中的put方法：

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

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);//得到hash值
        int i = indexFor(hash, table.length);//找到槽
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

我们从 int hash = hash(key); 这一行看起，这行起才是put方法的核心。

首先 int hash = hash(key); key就是我们之前提到的关键码，我们看看HashMap中的这个hash方法做了些什么：

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

final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        // 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);
}

可以看到，这个方法里调用了key本身的hashCode方法，得到了key的hashcode，然后对该hashcode进行了一些移位操作，最终返回操作后的int值。返回的这个值就是HashMap要用到的hashcode值，通过他可以找到记录所在的位置。那么现在有一个问题：为什么要专门调用这个hash(Onject key)方法来对key的hashcode进行包装然后再使用呢？可以直接使用key的hashcode的呀，这样做看起来不是多此一举吗？

其实这样做的目的是为下面的函数做准备的，我们看接下来要执行的代码：

int i = indexFor(hash, table.length);找到所谓的槽，也就是记录存在的位置。

1
2
3
4
5
6
7

/**
  * Returns index for hash code h.
  */
static int indexFor(int h, int length) {
     // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

可以看到，indexFor(int h, int length)如何通过hashcode得到记录的位置。indexFor方法内部是一个取模运算，h是我们通过上面的hash方法得到的，length是散列表的长度。HashMap中的散列表是一个数组，通过取模运算能保证indexFor方法的返回值(记录的位置)一定在这个数组内，没有超过其长度。因为h往往是一个很大的数字(int可以表示40亿这么大的数字)，而散列表的初始长度是可以由我们指定的(默认是16),另一方面，就算给他这么大的数组，内存也是放不下的。所以取模运算是必须的。经过取模运算得到的才是真正的槽值。

回到上一个问题，为什么要专门调用这个hash(Onject key)方法来对key的hashcode进行包装然后再使用呢？而不是直接使用key的hashcode的？

想明白这个问题，参考JDK 源码中 HashMap 的 hash 方法原理是什么？。我们上面也说了这样做的目的是为indexFor方法做准备的，总的来说就是为了让取模运算不会出现一种极端情况：大量的不同的h经过取模后返回同样的槽值。这样会带来严重的性能问题，也就是严重的冲突情况导致性能下降。关于冲突，看下文。

要理解接下来的代码，我们就需要知道哈希算法的另一个概念：冲突。

散列函数可能对于不相等的关键码计算出相同的hashcode，该现象称为冲突。怎么理解呢？

比如我们有这样一个串abcd，我们给出这样一个散列函数：将每一个字符的ascii值加起来除以字符的个数，得到他们的平均值就是这个串的hashcode。那么，可以保证没有其他的串经过这样的算法得到相同的hashcode吗？也就是说，无限多的元素通过散列函数映射到有穷集合上，一定会产生冲突。这也是我们理解hashcode的一个重要的点：不同的对象(equals返回false)可以有相同的hashcode。

那么，产生冲突怎么办呢？产生冲突之后，不同的对象在散列表中找到了相同的位置，为了解决这个问题，我们将这个槽中的内容设计成一个链表，当产生冲突的时候，就将新的元素放到链表中，他看起来是这样的：

其中：A，B，C分别为三条记录，他们就是产生冲突的三条记录。1,2,3….为散列表的索引位置。

接下来的代码 for (Entry e = table[i]; e != null; e = e.next)就容易理解了。找到记录所对应的槽之后，遍历这个链表直到找到与关键码相同的位置(可能之前已经有以这个关键码为key的value插入)。如果遍历完链表还没有找到这样的值，说明还不存在此关键码对应的记录，直接插入即可：addEntry(hash, key, value, i);.

那么，怎么判断两个关键码在逻辑上是否相同呢？

1

if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

可以看到，首先判断关键码的hashcode与链表记录的关键码hashcode是否相同：·e.hash == hash。为什么要加这样的判断？回头看看indexFor方法，经过取模运算后，不同的hashcode可以被散列在同一个槽中。通过这句代码可以将那些因为取模运算散列到同一个槽里的不同对象排除。

我们知道不同的对象(equals返回false)可以有相同的hashcode。相同的对象hashcode也必须相等吗？试想一下，如果两个对象相同，但是他们的hashcode不同，那么这两个对象很有可能被散列在不同的槽里，造成了同一个对象重复存储的问题。所以，我们又得出一个重要结论：相同的对象(equals返回true)hashcode一定相等。

e.hash == hash && ((k = e.key) == key：这段代码首先判断hashcode是否相等，然后判断关键码是否相等。注意，是判断关键码是否相等，直接比较内存地址，如果满足以上条件，那么可以断定两个关键码相同，是我们要找的记录。

key.equals(k)：如果上述两个条件没有满足，并不能够断定这两个关键码相等，此刻要使用equals方法判断这两个关键码是否相同。如果相同，说明是我们要找的记录。

if (e.hash == hash && ((k = e.key) == key || key.equals(k)))这句代码中其实包含了一种短路思想，|| 之前的判断如果生效，那么之后的key.equals(k)就不会再执行。很明显内存地址的比较要比equals方法高效的多。这也是Hashmap提高查找效率的一个重要手段。

至此，我们应该对equals和hashcode有了一个相对清晰的认识：hashcode提高了查找指定对象的效率。euqals定义了两个对象之间是否在逻辑上相同。hashcode只在HashMap，HashSet等这样使用了散列思想的地方用到，而equals在判断两个对象之间是否相同时需要用到，比如排序等。

总结

通过上面的分析，我们知道了hashcode与equals的几个关键：

1.不同的对象(equals返回false)可以有相同的hashcode

2.相同的对象(equals返回true)hashcode一定相等

3.若重新定义了上面两种方法中的一种，那么另一种方法也需要重新定义（对1、2的遵守）

关于如何重写equals方法与hashCode方法

equals与==

“==” 比较的是两个对象的内存地址，是物理意义上的相等

equals比较的是两个对象逻辑意义上的相等，是逻辑意义上的相等

两个对象进行比较：

== 返回true，则equals一定返回true；

equals返回true，== 不一定返回true。

sleep()

​ sleep()方法需要指定等待的时间，它可以让当前正在执行的线程在指定的时间内暂停执行，进入阻塞状态.

​ 该方法既可以让其他同优先级或者高优先级的线程得到执行的机会，也可以让低优先级的线程得到执行机会。但是sleep()方法不会释放“锁标志”，也就是说如果有synchronized同步块，其他线程仍然不能访问共享数据。 　　

wait()

　　wait()方法需要和notify()及notifyAll()两个方法一起介绍，这三个方法用于协调多个线程对共享数据的存取，所以必须在synchronized语句块内使用，也就是说，调用wait()，notify()和notifyAll()的任务在调用这些方法前必须拥有对象的锁。注意，它们都是Object类的方法，而不是Thread类的方法。
　　wait()方法与sleep()方法的不同之处在于，wait()方法会释放对象的“锁标志”。当调用某一对象的wait()方法后，会使当前线程暂停执行，并将当前线程放入对象等待池中，直到调用了notify()方法后，将从对象等待池中移出任意一个线程并放入锁标志等待池中，只有锁标志等待池中的线程可以获取锁标志，它们随时准备争夺锁的拥有权。当调用了某个对象的notifyAll()方法，会将对象等待池中的所有线程都移动到该对象的锁标志等待池。
　　除了使用notify()和notifyAll()方法，还可以使用带毫秒参数的wait(long timeout)方法，效果是在延迟timeout毫秒后，被暂停的线程将被恢复到锁标志等待池。
　　此外，wait()，notify()及notifyAll()只能在synchronized语句中使用，但是如果使用的是ReenTrantLock实现同步，该如何达到这三个方法的效果呢？解决方法是使用ReenTrantLock.newCondition()获取一个Condition类对象，然后Condition的await()，signal()以及signalAll()分别对应上面的三个方法。

yield()

　　yield()方法和sleep()方法类似，也不会释放“锁标志”，区别在于，它没有参数，即yield()方法只是使当前线程重新回到可执行状态，所以执行yield()的线程有可能在进入到可执行状态后马上又被执行，另外yield()方法只能使同优先级或者高优先级的线程得到执行机会，这也和sleep()方法不同。

join()

　　join()方法会使当前线程等待调用join()方法的线程结束后才能继续执行

Object有几种方法呢？

Java语言是一种单继承结构语言，Java中所有的类都有一个共同的祖先。这个祖先就是Object类。

如果一个类没有用extends明确指出继承于某个类，那么它默认继承Object类。

分析

Object类是Java中所有类的基类。位于java.lang包中，一共有13个方法。如下图：

具体解答

1.Object()

这个没什么可说的，Object类的构造方法。(非重点)

2.registerNatives()

为了使JVM发现本机功能，他们被一定的方式命名。例如，对于java.lang.Object.registerNatives，对应的C函数命名为Java_java_lang_Object_registerNatives。

通过使用registerNatives（或者更确切地说，JNI函数RegisterNatives），可以命名任何你想要你的C函数。(非重点)

3.clone()

clone()函数的用途是用来另存一个当前存在的对象。只有实现了Cloneable接口才可以调用该方法，否则抛出CloneNotSupportedException异常。（注意：回答这里时可能会引出设计模式的提问）

4.getClass()

final方法，用于获得运行时的类型。该方法返回的是此Object对象的类对象/运行时类对象Class。效果与Object.class相同。（注意：回答这里时可能会引出类加载，反射等知识点的提问）

5.equals()

equals用来比较两个对象的内容是否相等。默认情况下(继承自Object类)，equals和==是一样的，除非被覆写(override)了。（注意：这里可能引出更常问的“equals与==的区别”及hashmap实现原理的提问）

6.hashCode()

该方法用来返回其所在对象的物理地址（哈希码值），常会和equals方法同时重写，确保相等的两个对象拥有相等的hashCode。（同样，可能引出hashmap实现原理的提问）

7.toString()

toString()方法返回该对象的字符串表示，这个方法没什么可说的。

8.wait()

导致当前的线程等待，直到其他线程调用此对象的 notify() 方法或 notifyAll() 方法。（引出线程通信及“wait和sleep的区别”的提问）

9.wait(long timeout)

导致当前的线程等待，直到其他线程调用此对象的 notify() 方法或 notifyAll() 方法，或者超过指定的时间量。（引出线程通信及“wait和sleep的区别”的提问）

10.wait(long timeout, int nanos)

导致当前的线程等待，直到其他线程调用此对象的 notify() 方法或 notifyAll() 方法，或者其他某个线程中断当前线程，或者已超过某个实际时间量。（引出线程通信及“wait和sleep的区别”的提问）

11.notify()

唤醒在此对象监视器上等待的单个线程。（引出线程通信的提问）

12. notifyAll()

唤醒在此对象监视器上等待的所有线程。（引出线程通信的提问）

13.finalize()

当垃圾回收器确定不存在对该对象的更多引用时，由对象的垃圾回收器调用此方法。（非重点，但小心引出垃圾回收的提问）

引申常见问题

• equals() 与 == 的区别是什么？
• hashCode() 和 equals() 之间有什么联系？
• wait()方法与sleep()方法的区别
• 为什么重写了equals就必须重写hashCode
• HashMap的实现原理
• 谈谈类加载机制

转载 原文地址

理解零拷贝

零拷贝是Netty的重要特性之一，而究竟什么是零拷贝呢？ WIKI中对其有如下定义：

“Zero-copy” describes computer operations in which the CPU does not perform the task of copying data from one memory area to another.

从WIKI的定义中，我们看到“零拷贝”是指计算机操作的过程中，CPU不需要为数据在内存之间的拷贝消耗资源。而它通常是指计算机在网络上发送文件时，不需要将文件内容拷贝到用户空间（User Space）而直接在内核空间（Kernel Space）中传输到网络的方式。

Non-Zero Copy方式：

Zero Copy方式：

从上图中可以清楚的看到，Zero Copy的模式中，避免了数据在用户空间和内存空间之间的拷贝，从而提高了系统的整体性能。Linux中的sendfile()以及Java NIO中的FileChannel.transferTo()方法都实现了零拷贝的功能，而在Netty中也通过在FileRegion中包装了NIO的FileChannel.transferTo()方法实现了零拷贝。

而在Netty中还有另一种形式的零拷贝，即Netty允许我们将多段数据合并为一整段虚拟数据供用户使用，而过程中不需要对数据进行拷贝操作，这也是我们今天要讲的重点。我们都知道在stream-based transport（如TCP/IP）的传输过程中，数据包有可能会被重新封装在不同的数据包中，例如当你发送如下数据时：

有可能实际收到的数据如下：

因此在实际应用中，很有可能一条完整的消息被分割为多个数据包进行网络传输，而单个的数据包对你而言是没有意义的，只有当这些数据包组成一条完整的消息时你才能做出正确的处理，而Netty可以通过零拷贝的方式将这些数据包组合成一条完整的消息供你来使用。而此时，零拷贝的作用范围仅在用户空间中。

##Netty3中零拷贝的实现机制 以下以Netty 3.8.0.Final的源代码来进行说明

ChannelBuffer接口

Netty为需要传输的数据制定了统一的ChannelBuffer接口。该接口的主要设计思路如下：

• 使用getByte(int index)方法来实现随机访问
• 使用双指针的方式实现顺序访问
  • 每个Buffer都有一个读指针（readIndex）和写指针（writeIndex）
  • 在读取数据时读指针后移，在写入数据时写指针后移

定义了统一的接口之后，就是来做各种实现了。Netty主要实现了HeapChannelBuffer,ByteBufferBackedChannelBuffer等等，下面我们就来讲讲与Zero Copy直接相关的CompositeChannelBuffer类。

CompositeChannelBuffer类

CompositeChannelBuffer类的作用是将多个ChannelBuffer组成一个虚拟的ChannelBuffer来进行操作。为什么说是虚拟的呢，因为CompositeChannelBuffer并没有将多个ChannelBuffer真正的组合起来，而只是保存了他们的引用，这样就避免了数据的拷贝，实现了Zero Copy。 下面我们来看看具体的代码实现，首先是成员变量

1
2
3
4
5

private int readerIndex;
private int writerIndex;
private ChannelBuffer[] components;
private int[] indices;
private int lastAccessedComponentId;

以上这里列出了几个比较重要的成员变量。其中readerIndex既读指针和writerIndex既写指针是从AbstractChannelBuffer继承而来的；然后components是一个ChannelBuffer的数组，他保存了组成这个虚拟Buffer的所有子Buffer，indices是一个int类型的数组，它保存的是各个Buffer的索引值；最后的lastAccessedComponentId是一个int值，它记录了最后一次访问时的子Buffer ID。从这个数据结构，我们不难发现所谓的CompositeChannelBuffer实际上就是将一系列的Buffer通过数组保存起来，然后实现了ChannelBuffer 的接口，使得在上层看来，操作这些Buffer就像是操作一个单独的Buffer一样。

创建

接下来，我们再看一下CompositeChannelBuffer.setComponents方法，它会在初始化CompositeChannelBuffer时被调用。

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
30
31
32
33
34

/**
 * Setup this ChannelBuffer from the list
 */
private void setComponents(List<ChannelBuffer> newComponents) {
    assert !newComponents.isEmpty();

    // Clear the cache.
    lastAccessedComponentId = 0;

    // Build the component array.
    components = new ChannelBuffer[newComponents.size()];
    for (int i = 0; i < components.length; i ++) {
        ChannelBuffer c = newComponents.get(i);
        if (c.order() != order()) {
            throw new IllegalArgumentException(
                    "All buffers must have the same endianness.");
        }

        assert c.readerIndex() == 0;
        assert c.writerIndex() == c.capacity();

        components[i] = c;
    }

    // Build the component lookup table.
    indices = new int[components.length + 1];
    indices[0] = 0;
    for (int i = 1; i <= components.length; i ++) {
        indices[i] = indices[i - 1] + components[i - 1].capacity();
    }

    // Reset the indexes.
    setIndex(0, capacity());
}

通过代码可以看到该方法的功能就是将一个ChannelBuffer的List给组合起来。它首先将List中得元素放入到components数组中，然后创建indices用于数据的查找，最后使用setIndex来重置指针。这里需要注意的是setIndex(0, capacity())会将读指针设置为0，写指针设置为当前Buffer的长度，这也就是前面需要做assert c.readerIndex() == 0和assert c.writerIndex() == c.capacity()这两个判断的原因，否则很容易会造成数据重复读写的问题，所以Netty推荐我们使用ChannelBuffers.wrappedBuffer方法来进行Buffer的合并，因为在该方法中Netty会通过slice()方法来确保构建CompositeChannelBuffer是传入的所有子Buffer都是符合要求的。

数据访问

CompositeChannelBuffer.getByte(int index)的实现如下：

1
2
3
4

public byte getByte(int index) {
    int componentId = componentId(index);
    return components[componentId].getByte(index - indices[componentId]);
}

从代码我们可以看到，在随机查找时会首先通过index获取这个字节所在的componentId既字节所在的子Buffer序列，然后通过index - indices[componentId]计算出它在这个子Buffer中的第几个字节，然后返回结果。

下面再来看一下componentId(int index)的实现：

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

private int componentId(int index) {
    int lastComponentId = lastAccessedComponentId;
    if (index >= indices[lastComponentId]) {
        if (index < indices[lastComponentId + 1]) {
            return lastComponentId;
        }

        // Search right
        for (int i = lastComponentId + 1; i < components.length; i ++) {
            if (index < indices[i + 1]) {
                lastAccessedComponentId = i;
                return i;
            }
        }
    } else {
        // Search left
        for (int i = lastComponentId - 1; i >= 0; i --) {
            if (index >= indices[i]) {
                lastAccessedComponentId = i;
                return i;
            }
        }
    }

    throw new IndexOutOfBoundsException("Invalid index: " + index + ", maximum: " + indices.length);
}

从代码中我们发现，Netty以lastComponentId既上次访问的子Buffer序号为中心，向左右两边进行搜索，这样做的目的是，当我们两次随机查找的字符序列相近时（大部分情况下都是这样），可以最快的搜索到目标索引的componentId。

参考资料

1. http://my.oschina.net/flashsword/blog/164237
2. http://en.wikipedia.org/wiki/Zero-copy
3. http://stackoverflow.com/questions/20727615/is-nettys-zero-copy-different-from-os-level-zero-copy
4. http://www-old.itm.uni-luebeck.de/teaching/ws1112/vs/Uebung/GrossUebungNetty/VS-WS1112-xx-Zero-Copy_Event-Driven_Servers_with_Netty.pdf?lang=de

转载 原文地址

以前学习强软弱虚引用的时候，只是走马观花看看博客，并没有自己写代码去实践、去证明，导致每次看完后，过不了多久就忘了，后来下定决心，一定要自己敲敲代码，这样才能让印象更加深刻，古人云：纸上得来终觉浅，绝知此事要躬行。

Java中的四种引用

Java中有四种引用类型：强引用、软引用、弱引用、虚引用。

Java为什么要设计这四种引用

Java的内存分配和内存回收，都不需要程序员负责，都是由伟大的JVM去负责，一个对象是否可以被回收，主要看是否有引用指向此对象，说的专业点，叫可达性分析。

Java设计这四种引用的主要目的有两个：

• 可以让程序员通过代码的方式来决定某个对象的生命周期；
• 有利用垃圾回收。

强引用

强引用是最普遍的一种引用，我们写的代码，99.9999%都是强引用：

1

Object o = new Object();

这种就是强引用了，是不是在代码中随处可见，最亲切。

只要某个对象有强引用与之关联，这个对象永远不会被回收，即使内存不足，JVM宁愿抛出OOM，也不会去回收。

那么什么时候才可以被回收呢？当强引用和对象之间的关联被中断了，就可以被回收了。

我们可以手动把关联给中断了，方法也特别简单：

1

o = null;

我们可以手动调用GC，看看如果强引用和对象之间的关联被中断了，资源会不会被回收，为了更方便、更清楚的观察到回收的情况，我们需要新写一个类，然后重写finalize方法，下面我们来进行这个实验：

1
2
3
4
5
6

public class Student {
    @Override
    protected void finalize() throws Throwable {
        System.out.println("Student 被回收了");
    }
}

1
2
3
4
5

public static void main(String[] args) {
        Student student = new Student();
        student = null;
        System.gc();
}

运行结果：

1

Student 被回收了

可以很清楚的看到资源被回收了。

当然，在实际开发中，千万不要重写finalize方法

在实际的开发中，看到有一些对象被手动赋值为NULL，很大可能就是为了“特意提醒”JVM这块资源可以进行垃圾回收了。

软引用

软引用用来描述一些还有用,但非必须的对象.下面先来看看如何创建一个软引用：

1

SoftReference<Student> studentSoftReference = new SoftReference<Student>(new Student());

软引用就是把对象用SoftReference包裹一下，当我们需要从软引用对象获得包裹的对象，只要get一下就可以了：

1
2
3

SoftReference<Student>studentSoftReference=new SoftReference<Student>(new Student());
Student student = studentSoftReference.get();
System.out.println(student);

软引用有什么特点呢：当内存不足，会触发JVM的GC，如果GC后，内存还是不足，就会把软引用的包裹的对象给干掉，也就是只有在内存不足，JVM才会回收该对象。

还是一样的，必须做实验，才能加深印象：

1
2
3
4
5
6
7

SoftReference<byte[]> softReference = new SoftReference<byte[]>(new byte[1024*1024*10]);
System.out.println(softReference.get());
System.gc();
System.out.println(softReference.get());

byte[] bytes = new byte[1024 * 1024 * 10];
System.out.println(softReference.get());

我定义了一个软引用对象，里面包裹了byte[]，byte[]占用了10M，然后又创建了10Mbyte[]。

运行程序，需要带上一个参数：

1

-Xmx20M

代表最大堆内存是20M。

运行结果：

1
2
3

[B@11d7fff
[B@11d7fff
null

可以很清楚的看到手动完成GC后，软引用对象包裹的byte[]还活的好好的，但是当我们创建了一个10M的byte[]后，最大堆内存不够了，所以把软引用对象包裹的byte[]给干掉了，如果不干掉，就会抛出OOM。

软引用到底有什么用呢？比较适合用作缓存，当内存足够，可以正常的拿到缓存，当内存不够，就会先干掉缓存，不至于马上抛出OOM。比如Mybatis的二级缓存回收策略为Soft时,其实现类SoftCache就是一个软引用类型.

弱引用

弱引用和软引用类似,都是用来描述非必须对象的,但它只能生存到下一次GC前，关键字为WeakReference：

1
2

WeakReference<byte[]> weakReference = new WeakReference<byte[]>(new byte[1024*1024*10]);
System.out.println(weakReference.get());

根据JDK文档,弱引用常用来实现规范化映射,特点是不管内存是否足够，只要发生GC，都会被回收：

1
2
3
4

WeakReference<byte[]> weakReference = new WeakReference<byte[]>(new byte[1]);
System.out.println(weakReference.get());
System.gc();
System.out.println(weakReference.get());

运行结果：

1
2

[B@11d7fff
null

可以很清楚的看到明明内存还很充足，但是触发了GC，资源还是被回收了。弱引用在很多地方都有用到，比如ThreadLocal、WeakHashMap。

ThreadLocal通过使用弱引用Entry来避免内存泄漏，我们知道ThreadLocal变量在不同的线程中有不同的值，原理是每个线程都有一个ThreadLocalMap，用来存放ThreadLocal变量表.ThreadLocal 本身并不存储值，它只是作为一个 key 来让线程从 ThreadLocalMap 获取 value。结构如下：

图中的虚线表示 ThreadLocalMap 是使用 ThreadLocal 的弱引用作为 Key 的，当ThreadLocalRef使用完毕释放以后,仅有弱引用的对象ThreadLocal在 GC 时会被回收。

1
2
3
4
5
6
7
8
9

static class Entry extends WeakReference<ThreadLocal<?>> {
    /** The value associated with this ThreadLocal. */
    Object value;

    Entry(ThreadLocal<?> k, Object v) {
        super(k);
        value = v;
    }
}

这里为什么要使用弱引用呢？

如果不使用弱引用，当持有value的强引用释放掉后，而且线程没有结束(回收释放)时，threadLocalMap会一直持有ThreadLocal以及value的强引用，导致value不能够被回收，从而造成内存泄漏。

通过使用弱引用，当ThreadLocal的强引用释放掉后，通过一次系统gc检查，发现ThreadLocal对象只有threadLocalMap中Entry的若引用持有，此时根据弱引用的机制就会回收ThreadLocal对象，从而避免了内存泄露。

虚引用

虚引用又被称为幻影引用，我们来看看它的使用：

1
2
3

ReferenceQueue queue = new ReferenceQueue();
PhantomReference<byte[]> reference = new PhantomReference<byte[]>(new byte[1], queue);
System.out.println(reference.get());

虚引用的使用和上面说的软引用、弱引用的区别还是挺大的，我们先不管ReferenceQueue 是个什么鬼，直接来运行：

1

null

竟然打印出了null，我们来看看get方法的源码：

1
2
3

public T get() {
    return null;
}

这是几个意思，竟然直接返回了null。

这就是虚引用特点之一了：无法通过虚引用来获取对一个对象的真实引用。

那虚引用存在的意义是什么呢？这就要回到我们上面的代码了，我们把代码复制下，以免大家再次往上翻：

1
2
3

ReferenceQueue queue = new ReferenceQueue();
PhantomReference<byte[]> reference = new PhantomReference<byte[]>(new byte[1], queue);
System.out.println(reference.get());

创建虚引用对象，我们除了把包裹的对象传了进去，还传了一个ReferenceQueue，从名字就可以看出它是一个队列。

虚引用的特点之二就是 虚引用必须与ReferenceQueue一起使用，当GC准备回收一个对象，如果发现它还有虚引用，就会在回收之前，把这个虚引用加入到与之关联的ReferenceQueue中。

我们来用代码实践下吧：

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

    ReferenceQueue queue = new ReferenceQueue();
    List<byte[]> bytes = new ArrayList<>();
    PhantomReference<Student> reference = new PhantomReference<Student>(new Student(),queue);
    new Thread(() -> {
        for (int i = 0; i < 100;i++ ) {
            bytes.add(new byte[1024 * 1024]);
        }
    }).start();

    new Thread(() -> {
        while (true) {
            Reference poll = queue.poll();
            if (poll != null) {
                System.out.println("虚引用被回收了：" + poll);
            }
        }
    }).start();
    Scanner scanner = new Scanner(System.in);
    scanner.hasNext();
}

运行结果：

1
2

Student 被回收了
虚引用被回收了：java.lang.ref.PhantomReference@1ade6f1

我们简单的分析下代码：

第一个线程往集合里面塞数据，随着数据越来越多，肯定会发生GC。
第二个线程死循环，从queue里面拿数据，如果拿出来的数据不是null，就打印出来。

从运行结果可以看到：当发生GC，虚引用就会被回收，并且会把回收的通知放到ReferenceQueue中。

虚引用有什么用呢？在NIO中，就运用了虚引用管理堆外内存。

跳表(skip list) 对标的是平衡树(AVL Tree)，是一种 插入/删除/搜索 都是 O(log n) 的数据结构。它最大的优势是原理简单、容易实现、方便扩展、效率更高。因此在一些热门的项目里用来替代平衡树，如 redis, leveldb 等。

跳表的基本思想

首先，跳表处理的是有序的链表（一般是双向链表，下图未表示双向），如下：

这个链表中，如果要搜索一个数，需要从头到尾比较每个元素是否匹配，直到找到匹配的数为止，即时间复杂度是 O(n)O(n)。同理，插入一个数并保持链表有序，需要先找到合适的插入位置，再执行插入，总计也是 O(n)O(n) 的时间。

那么如何提高搜索的速度呢？很简单，做个索引：

如上图，我们新创建一个链表，它包含的元素为前一个链表的偶数个元素。这样在搜索一个元素时，我们先在上层链表进行搜索，当元素未找到时再到下层链表中搜索。例如搜索数字 19 时的路径如下图：

先在上层中搜索，到达节点 17 时发现下一个节点为 21，已经大于 19，于是转到下一层搜索，找到的目标数字 19。

我们知道上层的节点数目为 n/2n/2，因此，有了这层索引，我们搜索的时间复杂度降为了：O(n/2)O(n/2)。同理，我们可以不断地增加层数，来减少搜索的时间：

在上面的 4 层链表中搜索 25，在最上层搜索时就可以直接跳过 21 之前的所有节点，因此十分高效。

更一般地，如果有 kk 层，我们需要的搜索次数会小于 ⌈n2k⌉+k⌈n2k⌉+k ，这样当层数 kk 增加到 ⌈log2n⌉⌈log2⁡n⌉ 时，搜索的时间复杂度就变成了 lognlog⁡n。其实这背后的原理和二叉搜索树或二分查找很类似，通过索引来跳过大量的节点，从而提高搜索效率。

跳表

上节的结构是“静态”的，即我们先拥有了一个链表，再在之上建了多层的索引。但是在实际使用中，我们的链表是通过多次插入/删除形成的，换句话说是“动态”的。上节的结构要求上层相邻节点与对应下层节点间的个数比是 1:2，随意插入/删除一个节点，这个要求就被被破坏了。

因此跳表（skip list）表示，我们就不强制要求 1:2 了，一个节点要不要被索引，建几层的索引，都在节点插入时由抛硬币决定。当然，虽然索引的节点、索引的层数是随机的，为了保证搜索的效率，要大致保证每层的节点数目与上节的结构相当。下面是一个随机生成的跳表：

可以看到它每层的节点数还和上节的结构差不多，但是上下层的节点的对应关系已经完全被打破了。

现在假设节点 17 是最后插入的，在插入之前，我们需要搜索得到插入的位置：

接着，抛硬币决定要建立几层的索引，伪代码如下：

1
2
3
4
5
6

randomLevel()
    lvl := 1
    -- random() that returns a random value in [0...1)
    while random() < p and lvl < MaxLevel do
        lvl := lvl + 1
    return lvl

上面的伪代码相当于抛硬币，如果是正面（random() < p）则层数加一，直到抛出反面为止。其中的 MaxLevel 是防止如果运气太好，层数就会太高，而太高的层数往往并不会提供额外的性能，一般 MaxLevel=log1/pnMaxLevel=log1/p⁡n。现在假设 randomLevel 返回的结果是 2，那么就得到下面的结果。

如果要删除节点，则把节点和对应的所有索引节点全部删除即可。当然，要删除节点时需要先搜索得到该节点，搜索过程中可以把路径记录下来，这样删除索引层节点的时候就不需要多次搜索了。

显然，在最坏的情况下，所有节点都没有创建索引，时间复杂度为O(n)O(n)，但在平均情况下，搜索的时间复杂度却是 O(logn)O(log⁡n)，为什么呢？

简单的性能分析

一些严格的证明会涉及到比较复杂的概率统计学知识，所以这里只是简单地说明。

搜索的时间复杂度

为了计算搜索的时间复杂度，我们可以将查找的过程倒过来，从搜索最后的节点开始，一直向左或向上，直到最顶层。如下图，在路径上的每一点，都可能有两种情况：

1. 节点有上一层的节点，向上。这种情况出现的概率是 p。
2. 节点没有上一层的节点，向左。出现的概率是 1-p。

于是，设 C(k) 为反向搜索爬到第 k 层的平均路径长度，则有：

1
2

C(0) = 0
C(k) = p * (情况1) + (1-p) * (情况2)

将两种情况也用 C 代入，有：

1
2
3

C(k) = p*(1 + C(k–1)) + (1–p)*(1 + C(k))
C(k) = C(k–1) + 1/p
C(k) = k/p

上式表明，搜索时，平均在每层上需要搜索的路径长度为 1/p1/p，从平均的角度上和我们第一小节构造的“静态”结构相同（p 取 1/2）。

又注意到，上小节我们知道跳表的最大层数为 O(logn)O(log⁡n)，因此，搜索的复杂度 O(logn)/p=O(logn)O(log⁡n)/p=O(log⁡n)。

P.S. 这里我们用到的是最大层数，原论文证明时用到的是 L(n)L(n)，然后再考虑从 L(n)L(n) 层到最高层的平均节点个数。这里为了理解方便不再详细证明。

小结

1. 各种搜索结构提高效率的方式都是通过空间换时间得到的。
2. 跳表最终形成的结构和搜索树很相似。
3. 跳表通过随机的方式来决定新插入节点来决定索引的层数。
4. 跳表搜索的时间复杂度是 O(logn)O(log⁡n)，插入/删除也是。

想到快排(quick sort)与其它排序算法（如归并排序/堆排序）虽然时间复杂度是一样的，但复杂度的常数项较小；跳表的原论文也说跳表能提供一个常数项的速度提升，因此想着常数项小是不是随机算法的一个特点？这也它们大放异彩的重要因素吧。

参考

• ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf 原论文
• https://ticki.github.io/blog/skip-lists-done-right/ skip list 的一些变种、优化
• https://eugene-eeo.github.io/blog/skip-lists.html skip list 的一些相关复杂度分析
• http://cglab.ca/~morin/teaching/5408/refs/p90b.pdf skip list cookbook，算是 skip list 各方面的汇总
• 一个可以在有序元素中实现快速查询的数据结构 包含 skip list 的 C++ 实现
• Redis内部数据结构详解(6)——skiplist 图文并茂讲解 skip list，可与本文交叉对照
• https://www.youtube.com/watch?v=2g9OSRKJuzM MIT 关于 skip list 的课程
• https://courses.csail.mit.edu/6.046/spring04/handouts/skiplists.pdf MIT 课程讲义https://lotabout.me/2018/skip-list/#fnref:1)

转载 原文作者： 阮一峰

JSON Web Token（缩写 JWT）是目前最流行的跨域认证解决方案，本文介绍它的原理和用法。

一、跨域认证的问题

互联网服务离不开用户认证。一般流程是下面这样。

1、用户向服务器发送用户名和密码。

2、服务器验证通过后，在当前对话（session）里面保存相关数据，比如用户角色、登录时间等等。

3、服务器向用户返回一个 session_id，写入用户的 Cookie。

4、用户随后的每一次请求，都会通过 Cookie，将 session_id 传回服务器。

5、服务器收到 session_id，找到前期保存的数据，由此得知用户的身份。

这种模式的问题在于，扩展性（scaling）不好。单机当然没有问题，如果是服务器集群，或者是跨域的服务导向架构，就要求 session 数据共享，每台服务器都能够读取 session。

举例来说，A 网站和 B 网站是同一家公司的关联服务。现在要求，用户只要在其中一个网站登录，再访问另一个网站就会自动登录，请问怎么实现？

一种解决方案是 session 数据持久化，写入数据库或别的持久层。各种服务收到请求后，都向持久层请求数据。这种方案的优点是架构清晰，缺点是工程量比较大。另外，持久层万一挂了，就会单点失败。

另一种方案是服务器索性不保存 session 数据了，所有数据都保存在客户端，每次请求都发回服务器。JWT 就是这种方案的一个代表。

二、JWT 的原理

JWT 的原理是，服务器认证以后，生成一个 JSON 对象，发回给用户，就像下面这样。

1 2 3 4 5

{ "姓名": "张三", "角色": "管理员", "到期时间": "2018年7月1日0点0分" }

以后，用户与服务端通信的时候，都要发回这个 JSON 对象。服务器完全只靠这个对象认定用户身份。为了防止用户篡改数据，服务器在生成这个对象的时候，会加上签名（详见后文）。

服务器就不保存任何 session 数据了，也就是说，服务器变成无状态了，从而比较容易实现扩展。

三、JWT 的数据结构

实际的 JWT 大概就像下面这样。

它是一个很长的字符串，中间用点（.）分隔成三个部分。注意，JWT 内部是没有换行的，这里只是为了便于展示，将它写成了几行。

JWT 的三个部分依次如下。

• Header（头部）
• Payload（负载）
• Signature（签名）

写成一行，就是下面的样子。

1	Header.Payload.Signature

下面依次介绍这三个部分。

3.1 Header

Header 部分是一个 JSON 对象，描述 JWT 的元数据，通常是下面的样子。

1 2 3 4

{ "alg": "HS256", "typ": "JWT" }

上面代码中，alg属性表示签名的算法（algorithm），默认是 HMAC SHA256（写成 HS256）；typ属性表示这个令牌（token）的类型（type），JWT 令牌统一写为JWT。

最后，将上面的 JSON 对象使用 Base64URL 算法（详见后文）转成字符串。

3.2 Payload

Payload 部分也是一个 JSON 对象，用来存放实际需要传递的数据。JWT 规定了7个官方字段，供选用。

• iss (issuer)：签发人
• exp (expiration time)：过期时间
• sub (subject)：主题
• aud (audience)：受众
• nbf (Not Before)：生效时间
• iat (Issued At)：签发时间
• jti (JWT ID)：编号

除了官方字段，你还可以在这个部分定义私有字段，下面就是一个例子。

1 2 3 4 5

{ "sub": "1234567890", "name": "John Doe", "admin": true }

注意，JWT 默认是不加密的，任何人都可以读到，所以不要把秘密信息放在这个部分。

这个 JSON 对象也要使用 Base64URL 算法转成字符串。

3.3 Signature

Signature 部分是对前两部分的签名，防止数据篡改。

首先，需要指定一个密钥（secret）。这个密钥只有服务器才知道，不能泄露给用户。然后，使用 Header 里面指定的签名算法（默认是 HMAC SHA256），按照下面的公式产生签名。

1 2 3 4

HMACSHA256( base64UrlEncode(header) + "." + base64UrlEncode(payload), secret)

算出签名以后，把 Header、Payload、Signature 三个部分拼成一个字符串，每个部分之间用”点”（.）分隔，就可以返回给用户。

3.4 Base64URL

前面提到，Header 和 Payload 串型化的算法是 Base64URL。这个算法跟 Base64 算法基本类似，但有一些小的不同。

JWT 作为一个令牌（token），有些场合可能会放到 URL（比如 api.example.com/?token=xxx）。Base64 有三个字符+、/和=，在 URL 里面有特殊含义，所以要被替换掉：=被省略、+替换成-，/替换成_ 。这就是 Base64URL 算法。

四、JWT 的使用方式

客户端收到服务器返回的 JWT，可以储存在 Cookie 里面，也可以储存在 localStorage。

此后，客户端每次与服务器通信，都要带上这个 JWT。你可以把它放在 Cookie 里面自动发送，但是这样不能跨域，所以更好的做法是放在 HTTP 请求的头信息Authorization字段里面。

1	Authorization: Bearer <token>

另一种做法是，跨域的时候，JWT 就放在 POST 请求的数据体里面。

五、JWT 的几个特点

（1）JWT 默认是不加密，但也是可以加密的。生成原始 Token 以后，可以用密钥再加密一次。

（2）JWT 不加密的情况下，不能将秘密数据写入 JWT。

（3）JWT 不仅可以用于认证，也可以用于交换信息。有效使用 JWT，可以降低服务器查询数据库的次数。

（4）JWT 的最大缺点是，由于服务器不保存 session 状态，因此无法在使用过程中废止某个 token，或者更改 token 的权限。也就是说，一旦 JWT 签发了，在到期之前就会始终有效，除非服务器部署额外的逻辑。

（5）JWT 本身包含了认证信息，一旦泄露，任何人都可以获得该令牌的所有权限。为了减少盗用，JWT 的有效期应该设置得比较短。对于一些比较重要的权限，使用时应该再次对用户进行认证。

（6）为了减少盗用，JWT 不应该使用 HTTP 协议明码传输，要使用 HTTPS 协议传输。

六、参考链接

• Introduction to JSON Web Tokens， by Auth0
• Sessionless Authentication using JWTs (with Node + Express + Passport JS), by Bryan Manuele
• Learn how to use JSON Web Tokens, by dwyl

转载 原文作者： 阮一峰

1.

昨天的《MIME笔记》中提到，MIME主要使用两种编码转换方式—-Quoted-printable和Base64—-将8位的非英语字符转化为7位的ASCII字符。

虽然这样的初衷，是为了满足电子邮件中不能直接使用非ASCII码字符的规定，但是也有其他重要的意义：

a）所有的二进制文件，都可以因此转化为可打印的文本编码，使用文本软件进行编辑；

b）能够对文本进行简单的加密。

2.

首先，简单介绍一下Quoted-printable编码转换方式。它主要用于ACSII文本中夹杂少量非ASCII码字符的情况，不适合于转换纯二进制文件。

它规定将每一个8位的字节，转换为3个字符。

第一个字符是”=”号，这是固定不变的。

后面二个字符是二个十六进制数，分别代表了这个字节前四位和后四位的数值。

举例来说，ASCII码中”换页键”（form feed）是12，二进制形式是00001100，写成十六进制就是0C，因此它的编码值为”=0C”。”=”号的ASCII值是61，二进制形式是00111101，因为它的编码值是”=3D”。除了可打印的ASCII码以外，所有其他字符都必须用这种方式进行转换。

所有可打印的ASCII码字符（十进制值从33到126）都保持原样不变，”=”（十进制值61）除外。

3.

下面，详细介绍Base64的编码转换方式。

所谓Base64，就是说选出64个字符—-小写字母a-z、大写字母A-Z、数字0-9、符号”+”、”/“（再加上作为垫字的”=”，实际上是65个字符）—-作为一个基本字符集。然后，其他所有符号都转换成这个字符集中的字符。

具体来说，转换方式可以分为四步。

第一步，将每三个字节作为一组，一共是24个二进制位。

第二步，将这24个二进制位分为四组，每个组有6个二进制位。

第三步，在每组前面加两个00，扩展成32个二进制位，即四个字节。

第四步，根据下表，得到扩展后的每个字节的对应符号，这就是Base64的编码值。

　　0　A　　17　R　　　34　i　　　51　z

　　1　B　　18　S　　　35　j　　　52　0

　　2　C　　19　T　　　36　k　　　53　1

　　3　D　　20　U　　　37　l　　　54　2

　　4　E　　21　V　　　38　m　　　55　3

　　5　F　　22　W　　　39　n　　　56　4

　　6　G　　23　X　　　40　o　　　57　5

　　7　H　　24　Y　　　41　p　　　58　6

　　8　I　　　25　Z　　　42　q　　　59　7

　　9　J　　26　a　　　43　r　　　60　8

　　10　K　　27　b　　　44　s　　　61　9

　　11　L　　28　c　　　45　t　　　62　+

　　12　M　　29　d　　　46　u　　　63　/

　　13　N　　30　e　　　47　v

　　14　O　　31　f　　　48　w　　　

　　15　P　　32　g　　　49　x

　　16　Q　　33　h　　　50　y

因为，Base64将三个字节转化成四个字节，因此Base64编码后的文本，会比原文本大出三分之一左右。

4.

举一个具体的实例，演示英语单词Man如何转成Base64编码。

第一步，”M”、”a”、”n”的ASCII值分别是77、97、110，对应的二进制值是01001101、01100001、01101110，将它们连成一个24位的二进制字符串010011010110000101101110。

第二步，将这个24位的二进制字符串分成4组，每组6个二进制位：010011、010110、000101、101110。

第三步，在每组前面加两个00，扩展成32个二进制位，即四个字节：00010011、00010110、00000101、00101110。它们的十进制值分别是19、22、5、46。

第四步，根据上表，得到每个值对应Base64编码，即T、W、F、u。

因此，Man的Base64编码就是TWFu。

5.

如果字节数不足三，则这样处理：

a）二个字节的情况：将这二个字节的一共16个二进制位，按照上面的规则，转成三组，最后一组除了前面加两个0以外，后面也要加两个0。这样得到一个三位的Base64编码，再在末尾补上一个”=”号。

比如，”Ma”这个字符串是两个字节，可以转化成三组00010011、00010110、00010000以后，对应Base64值分别为T、W、E，再补上一个”=”号，因此”Ma”的Base64编码就是TWE=。

b）一个字节的情况：将这一个字节的8个二进制位，按照上面的规则转成二组，最后一组除了前面加二个0以外，后面再加4个0。这样得到一个二位的Base64编码，再在末尾补上两个”=”号。

比如，”M”这个字母是一个字节，可以转化为二组00010011、00010000，对应的Base64值分别为T、Q，再补上二个”=”号，因此”M”的Base64编码就是TQ==。

6.

再举一个中文的例子，汉字”严”如何转化成Base64编码？

这里需要注意，汉字本身可以有多种编码，比如gb2312、utf-8、gbk等等，每一种编码的Base64对应值都不一样。下面的例子以utf-8为例。

首先，”严”的utf-8编码为E4B8A5，写成二进制就是三字节的”11100100 10111000 10100101”。将这个24位的二进制字符串，按照第3节中的规则，转换成四组一共32位的二进制值”00111001 00001011 00100010 00100101”，相应的十进制数为57、11、34、37，它们对应的Base64值就为5、L、i、l。

所以，汉字”严”（utf-8编码）的Base64值就是5Lil。

7.

在PHP语言中，有一对专门的函数用于Base64转换：base64_encode()用于编码、base64_decode()用于解码。

这对函数的特点是，它们不管输入文本的编码是什么，都会按照规则进行Base64编码。因此，如果你想得到utf-8编码下的Base64对应值，你就必须自己保证，输入的文本是utf-8编码的。