• Index

关注公众号不定期领红包:

加入知识星球社群:

关注微博获取实时动态:

编码算法

Last updated: ... / Reads: 1963670 Edit

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

ASCII码就是一种编码,字母A的编码是十六进制的0x41,字母B0x42,以此类推:

字母ASCII编码
A0x41
B0x42
C0x43
D0x44

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

汉字Unicode编码UTF-8编码
0x4e2d0xe4b8ad
0x65870xe69687
0x7f160xe7bc96
0x78010xe7a081

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

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

URL编码

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

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

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

  • 如果字符是A~Za~z0~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~Za~z0~9-_.*%,便于浏览器和服务器处理。

Base64编码

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

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

举个例子:3个byte数据分别是e4b8ad,按6bit分组得到390b222d

┌───────────────┬───────────────┬───────────────┐
│      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,最后两个索引6263分别用字符+/表示。

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

编码后得到5Lit4个字符。要对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));
    }
}

Base64编码的目的是把二进制数据变成文本格式,这样在很多文本中就可以处理二进制数据。例如,电子邮件协议就是文本协议,如果要在电子邮件中添加一个二进制文件,就可以用Base64编码,然后以文本的形式传送。

Base64编码的缺点是传输效率会降低,因为它把原始数据的长度增加了1/3。

和URL编码一样,Base64编码是一种编码算法,不是加密算法。

如果把Base64的64个字符编码表换成32个、48个或者58个,就可以使用Base32编码,Base48编码和Base58编码。字符越少,编码的效率就会越低。

小结

URL编码和Base64编码都是编码算法,它们不是加密算法;

URL编码的目的是把任意文本数据编码为%前缀表示的文本,便于浏览器和服务器处理;

Base64编码的目的是把任意二进制数据编码为文本,但编码后数据量会增加1/3。


Comments

Make a comment

  • Index