Hadoop對(duì)于long、int （化成long進(jìn)行編碼）的編碼設(shè)計(jì)了自己的一套編碼方式，這是一個(gè)zero-compressed encoded的變長(zhǎng)編碼方式，有利于大大壓縮冗余數(shù)據(jù)。具體算法其實(shí)很簡(jiǎn)單，具體來說有如下幾點(diǎn)：

1、對(duì)于-112 <= i <= 127的整數(shù)，只用1個(gè)字節(jié)byte來表示；如果超過上述范圍時(shí)，編碼***個(gè)字節(jié)則會(huì)用來表示i的總字節(jié)數(shù)，后面則跟著 i 的字節(jié)；

2、如果i大于0，則編碼的***個(gè)字節(jié) b 范圍在-113和-120之間，則 i 會(huì)有 (-112 - b)個(gè)字節(jié)，所以可以表示有1-8個(gè)字節(jié)；

3、如果i小于0，則編碼***個(gè)字節(jié) b 范圍在 -121 和 -128之間，則 i 會(huì)有 (-120 - b)個(gè)字節(jié)，同樣也可以表示有1-8個(gè)字節(jié)。（Hadoop的實(shí)現(xiàn)里，當(dāng)i為負(fù)數(shù)被編碼的是 i 補(bǔ)碼）。

算法看上去比較容易理解，具體要點(diǎn)就是利用***個(gè)字節(jié)表示 i 的長(zhǎng)度，以及 i 的符號(hào)，不過其實(shí)，如果深入源碼后，發(fā)現(xiàn)Hadoop的實(shí)現(xiàn)有點(diǎn)小巧妙的地方，我們先看代碼的實(shí)現(xiàn)：

首先是變長(zhǎng)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' //關(guān)鍵部分！ 替換做法是 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)); } }

為了方便，我這里也貼上自己稍微簡(jiǎn)化了Hadoop實(shí)現(xiàn)的解碼變長(zhǎng)long的實(shí)現(xiàn)：

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; } 算法的具體實(shí)現(xiàn)部分，參照之前概括的描述很容易了解大致框架，但有一個(gè)很關(guān)鍵的部分，就是在添加了注釋的編碼和解碼的部分，對(duì)于算法第3個(gè)條件里，如果 i 為負(fù)數(shù)的時(shí)候，Hadoop的默認(rèn)實(shí)現(xiàn)里會(huì)把 i 進(jìn)行補(bǔ)碼運(yùn)算，然后再繼續(xù)執(zhí)行編碼，而因此，在解碼的時(shí)候，***部分也要重新取一個(gè)補(bǔ)碼操作。

算法思想分析

為什么要這樣呢？其實(shí)分析一下整個(gè)算法的原理。首先如果我們簡(jiǎn)單的把***個(gè)字節(jié)表示 i 的字節(jié)數(shù)，不分為正、負(fù)兩個(gè)部分來額外表示符號(hào)的話，這樣會(huì)出現(xiàn)一個(gè)問題：那就是會(huì)沒辦法通過變長(zhǎng)編碼簡(jiǎn)單實(shí)現(xiàn)正負(fù)判斷，舉個(gè)簡(jiǎn)單的例子，對(duì)于 i = 128和 i = -128，這兩個(gè)數(shù)的編碼對(duì)于1個(gè)字節(jié)來說，都是0x80！為什么會(huì)這樣呢？如果想到負(fù)數(shù)的二進(jìn)制編碼是正數(shù)取反后加1（加1是為了避免直接取反對(duì)0進(jìn)行 兩次編碼，這樣負(fù)數(shù)能夠多表示1個(gè)數(shù)），因此，對(duì)于給定的字節(jié)，負(fù)數(shù)總是會(huì)比正數(shù)多表示1個(gè)數(shù)，對(duì)于1個(gè)字節(jié)，能表示-128~127。因此對(duì)于 i = 128的時(shí)候，沒辦法分辨出正負(fù)，必須要靠***個(gè)字節(jié)添加符號(hào)信息。

當(dāng)給***個(gè)字節(jié)多分8個(gè)數(shù)出來表示符號(hào)的時(shí)候，為了要計(jì)算 i 的位數(shù)，如果 i 為負(fù)數(shù)的時(shí)候，i 的高位則全為1， 因此必須要對(duì) i 為負(fù)數(shù)的情況取反，然后再不斷循環(huán)計(jì)算 i 的長(zhǎng)度，但事實(shí)上，我們同樣也可以對(duì) i 取反后加1，也就是對(duì) i = -i；轉(zhuǎn)為絕對(duì)值，而事實(shí)上，經(jīng)過本人的測(cè)試，無論是取反或者是做絕對(duì)值操作，兩者均可以正常進(jìn)行編碼解碼，但事實(shí)上，取反有一個(gè)好處，對(duì)于i = -256的時(shí)候，如果將 i 取反，則會(huì)編碼輸出的兩個(gè)字節(jié)為：-121，-1。如果將 i 取絕對(duì)值，則編碼輸出的兩個(gè)字節(jié)為：-122，1，0?？梢?，對(duì)于這種的時(shí)候，取反能夠比取絕對(duì)值少用1個(gè)字節(jié)。