编码算法

共计 4036 个字符，预计需要花费 11 分钟才能阅读完成。

要学习编码算法，我们先来看一看什么是编码。

ASCII 码就是一种编码，字母 A 的编码是十六进制的 0x41，字母B 是0x42，以此类推：

字母	ASCII 编码
A	0x41
B	0x42
C	0x43
D	0x44
…	…

因为 ASCII 编码最多只能有 128 个字符，要想对更多的文字进行编码，就需要用 Unicode。而中文的中使用 Unicode 编码就是0x4e2d，使用 UTF- 8 则需要 3 个字节编码：

汉字	Unicode 编码	UTF- 8 编码
中	0x4e2d	0xe4b8ad
文	0x6587	0xe69687
编	0x7f16	0xe7bc96
码	0x7801	0xe7a081
…	…	…

因此，最简单的编码是直接给每个字符指定一个若干字节表示的整数，复杂一点的编码就需要根据一个已有的编码推算出来。

比如 UTF- 8 编码，它是一种不定长编码，但可以从给定字符的 Unicode 编码推算出来。

URL 编码是浏览器发送数据给服务器时使用的编码，它通常附加在 URL 的参数部分，例如：

https://www.baidu.com/s?wd=%E4%B8%AD%E6%96%87

之所以需要 URL 编码，是因为出于兼容性考虑，很多服务器只识别 ASCII 字符。但如果 URL 中包含中文、日文这些非 ASCII 字符怎么办？不要紧，URL 编码有一套规则：

如果字符是 A~Z，a~z，0~9 以及-、_、.、*，则保持不变；
如果是其他字符，先转换为 UTF- 8 编码，然后对每个字节以 %XX 表示。

例如：字符 中的 UTF- 8 编码是0xe4b8ad，因此，它的 URL 编码是%E4%B8%AD。URL 编码总是大写。

Java 标准库提供了一个 URLEncoder 类来对任意字符串进行 URL 编码：

import java.net.URLEncoder;
import java.nio.charset.StandardCharsets;

public class Main {public static void main(String[] args) {String encoded = URLEncoder.encode("中文!", StandardCharsets.UTF_8);
        System.out.println(encoded);
    }
}

上述代码的运行结果是 %E4%B8%AD%E6%96%87%21， 中的 URL 编码是 %E4%B8%AD， 文的 URL 编码是 %E6%96%87，! 虽然是 ASCII 字符，也要对其编码为%21。

和标准的 URL 编码稍有不同，URLEncoder 把空格字符编码成+，而现在的 URL 编码标准要求空格被编码为%20，不过，服务器都可以处理这两种情况。

如果服务器收到 URL 编码的字符串，就可以对其进行解码，还原成原始字符串。Java 标准库的 URLDecoder 就可以解码：

import java.net.URLDecoder;
import java.nio.charset.StandardCharsets;

public class Main {public static void main(String[] args) {String decoded = URLDecoder.decode("%E4%B8%AD%E6%96%87%21", StandardCharsets.UTF_8);
        System.out.println(decoded);
    }
}

要特别注意：URL 编码是编码算法，不是加密算法。URL 编码的目的是把任意文本数据编码为 % 前缀表示的文本，编码后的文本仅包含 A~Z，a~z，0~9，-，_，.，* 和%，便于浏览器和服务器处理。

URL 编码是对字符进行编码，表示成 %xx 的形式，而 Base64 编码是对二进制数据进行编码，表示成文本格式。

Base64 编码可以把任意长度的二进制数据变为纯文本，且只包含 A~Z、a~z、0~9、+、/、= 这些字符。它的原理是把 3 字节的二进制数据按 6bit 一组，用 4 个 int 整数表示，然后查表，把 int 整数用索引对应到字符，得到编码后的字符串。

举个例子：3 个 byte 数据分别是 e4、b8、ad，按 6bit 分组得到39、0b、22 和2d：

┌───────────────┬───────────────┬───────────────┐
│      e4       │      b8       │      ad       │
└───────────────┴───────────────┴───────────────┘
┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│1│1│1│0│0│1│0│0│1│0│1│1│1│0│0│0│1│0│1│0│1│1│0│1│
└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
┌───────────┬───────────┬───────────┬───────────┐
│    39     │    0b     │    22     │    2d     │
└───────────┴───────────┴───────────┴───────────┘

因为 6 位整数的范围总是 0~63，所以，能用 64 个字符表示：字符A~Z 对应索引 0~25，字符a~z 对应索引 26~51，字符0~9 对应索引 52~61，最后两个索引62、63 分别用字符 + 和/表示。

在 Java 中，二进制数据就是 byte[] 数组。Java 标准库提供了 Base64 来对 byte[] 数组进行编解码：

import java.util.*;

public class Main {public static void main(String[] args) {byte[] input = new byte[] { (byte) 0xe4, (byte) 0xb8, (byte) 0xad };
        String b64encoded = Base64.getEncoder().encodeToString(input);
        System.out.println(b64encoded);
    }
}

编码后得到 5Lit 4 个字符。要对Base64 解码，仍然用 Base64 这个类：

import java.util.*;

public class Main {public static void main(String[] args) {byte[] output = Base64.getDecoder().decode("5Lit");
        System.out.println(Arrays.toString(output)); // [-28, -72, -83]
    }
}

有的童鞋会问：如果输入的 byte[] 数组长度不是 3 的整数倍肿么办？这种情况下，需要对输入的末尾补一个或两个 0x00，编码后，在结尾加一个= 表示补充了 1 个 0x00，加两个= 表示补充了 2 个 0x00，解码的时候，去掉末尾补充的一个或两个0x00 即可。

实际上，因为编码后的长度加上 = 总是 4 的倍数，所以即使不加 = 也可以计算出原始输入的 byte[]。Base64 编码的时候可以用withoutPadding() 去掉=，解码出来的结果是一样的：

import java.util.*;

public class Main {public static void main(String[] args) {byte[] input = new byte[] { (byte) 0xe4, (byte) 0xb8, (byte) 0xad, 0x21 };
        String b64encoded = Base64.getEncoder().encodeToString(input);
        String b64encoded2 = Base64.getEncoder().withoutPadding().encodeToString(input);
        System.out.println(b64encoded);
        System.out.println(b64encoded2);
        byte[] output = Base64.getDecoder().decode(b64encoded2);
        System.out.println(Arrays.toString(output));
    }
}

因为标准的 Base64 编码会出现 +、/ 和=，所以不适合把 Base64 编码后的字符串放到 URL 中。一种针对 URL 的 Base64 编码可以在 URL 中使用的 Base64 编码，它仅仅是把 + 变成 -，/ 变成_：

import java.util.*;

public class Main {public static void main(String[] args) {byte[] input = new byte[] { 0x01, 0x02, 0x7f, 0x00 };
        String b64encoded = Base64.getUrlEncoder().encodeToString(input);
        System.out.println(b64encoded);
        byte[] output = Base64.getUrlDecoder().decode(b64encoded);
        System.out.println(Arrays.toString(output));
    }
}