Hadoop的一个变长long编码剖析 本文作者：佚名 来源：51CTO
Hadoop对于long、int （化成long进行编码）的编码设计了自己的一套编码方式，这是一个zero-compressed encoded的变长编码方式，有利于大大压缩冗余数据。具体算法其实很简单，具体来说有如下几点：
1、对于-112 <= i <= 127的整数，只用1个字节byte来表示；如果超过上述范围时，编码第一个字节则会用来表示i的总字节数，后面则跟着 i 的字节；
2、如果i大于0，则编码的第一个字节 b 范围在-113和-120之间，则 i 会有 (-112 - b)个字节，所以可以表示有1-8个字节；
3、如果i小于0，则编码第一个字节 b 范围在 -121 和 -128之间，则 i 会有 (-120 - b)个字节，同样也可以表示有1-8个字节。（Hadoop的实现里，当i为负数被编码的是 i 补码）。
算法看上去比较容易理解，具体要点就是利用第一个字节表示 i 的长度，以及 i 的符号，不过其实，如果深入源码后，发现Hadoop的实现有点小巧妙的地方，我们先看代码的实现：
首先是变长long的编码：
public static void writeVLong(DataOutput stream, long i) throws IOException { if (i >= -112 && i <= 127) { stream.writeByte((byte)i); return; } int len = -112; if (i < 0) { i ^= -1L; // take one's complement' //关键部分！ 替换做法是 i = -i; len = -120; } long tmp = i; while (tmp != 0) { tmp = tmp >> 8; len--; } stream.writeByte((byte)len); len = (len < -120) ? -(len + 120) : -(len + 112); for (int idx = len; idx != 0; idx--) { int shiftbits = (idx - 1) * 8; long mask = 0xFFL << shiftbits; stream.writeByte((byte)((i & mask) >> shiftbits)); } }
为了方便，我这里也贴上自己稍微简化了Hadoop实现的解码变长long的实现：
public static long readVLong(DataInputStream input) throws IOException { byte firstByte = input.readByte; int len = -112; boolean isNegative = false; if (firstByte >= -112 && firstByte <= 127) { return firstByte; } else if (firstByte <= -121) { len = -120; isNegative = true; } len = len - firstByte; long res = 0; for (int i = 0; i < len; ++i) { res <<= 8; byte b = input.readByte; res = (b & 0xFF) | res; } //如果编码是i = -i; 则这里是return isNegative ? (-res) : res; return isNegative ? (res ^ -1L) : res; } 算法的具体实现部分，参照之前概括的描述很容易了解大致框架，但有一个很关键的部分，就是在添加了注释的编码和解码的部分，对于算法第3个条件里，如果 i 为负数的时候，Hadoop的默认实现里会把 i 进行补码运算，然后再继续执行编码，而因此，在解码的时候，最后部分也要重新取一个补码操作。
算法思想分析
为什么要这样呢？其实分析一下整个算法的原理。首先如果我们简单的把第一个字节表示 i 的字节数，不分为正、负两个部分来额外表示符号的话，这样会出现一个问题：那就是会没办法通过变长编码简单实现正负判断，举个简单的例子，对于 i = 128和 i = -128，这两个数的编码对于1个字节来说，都是0x80！为什么会这样呢？如果想到负数的二进制编码是正数取反后加1（加1是为了避免直接取反对0进行 两次编码，这样负数能够多表示1个数），因此，对于给定的字节，负数总是会比正数多表示1个数，对于1个字节，能表示-128~127。因此对于 i = 128的时候，没办法分辨出正负，必须要靠第一个字节添加符号信息。
当给第一个字节多分8个数出来表示符号的时候，为了要计算 i 的位数，如果 i 为负数的时候，i 的高位则全为1， 因此必须要对 i 为负数的情况取反，然后再不断循环计算 i 的长度，但事实上，我们同样也可以对 i 取反后加1，也就是对 i = -i；转为绝对值，而事实上，经过本人的测试，无论是取反或者是做绝对值操作，两者均可以正常进行编码解码，但事实上，取反有一个好处，对于i = -256的时候，如果将 i 取反，则会编码输出的两个字节为：-121，-1。如果将 i 取绝对值，则编码输出的两个字节为：-122，1，0。可见，对于这种的时候，取反能够比取绝对值少用1个字节。
本文作者：佚名
来源：51CTO
