最近在家里修習(xí) Java 這項(xiàng)技能浆西，估計(jì)快點(diǎn)滿(mǎn)技能點(diǎn)兒了，很開(kāi)心顽腾。不過(guò)遇到了一個(gè)問(wèn)題近零，困擾了我一陣子。問(wèn)題是這樣的抄肖，我要寫(xiě) Android App久信，與服務(wù)器交互。大家都知道 Javascript 不知為什么占領(lǐng)了瀏覽器腳本的全部份額漓摩，緊接著 Json 成為了 Web 服務(wù)器與瀏覽器傳輸數(shù)據(jù)的事實(shí)標(biāo)準(zhǔn)裙士。大家也知道 Java 不知為什么成為了 Android App 開(kāi)發(fā)的推薦做法，而 Java 聽(tīng)上去就有著濃濃的“企業(yè)級(jí)”味道管毙，自有一個(gè)序列化和一大堆 RPC 標(biāo)準(zhǔn)腿椎。Json 跟 Java 聽(tīng)上去就格格不入，但我要把 Java 對(duì)象變成 Json 傳出去夭咬，再收到 Json 變回 Java 對(duì)象啃炸！

先展示一下我的工具叭：我使用 android.util.JsonWriter 和 android.util.JsonReader，它們是做什么的呢卓舵？簡(jiǎn)單說(shuō)南用，就是把 Json 字符串解析成 AST。比如我們可以用 reader.beginObject(), reader.nextName(), reader.nextInt() 去讀取 Json 字符串里的左大括號(hào)掏湾，屬性名和整型值裹虫，而不必考慮中間有幾個(gè)空格，整數(shù)怎么一位一位讀這些細(xì)節(jié)忘巧『憬纾或者說(shuō)這個(gè)就是可以造出來(lái)的最低級(jí)的工具了。值得注意的是砚嘴，我只會(huì)向同一個(gè)方向讀寫(xiě)十酣。

然后我先不想太多，先開(kāi)始寫(xiě)代碼际长。數(shù)組很好處理耸采，讀的時(shí)候先 beginArray() 讀左中括號(hào)，然后在 hasNext() 返回 true 的時(shí)候用 nextXxx() 讀下一個(gè)值（Xxx 可能是 Double, Int, Long, String 或 Null）工育，如果返回 false 了虾宇，就調(diào)用 endArray() 讀右中括號(hào)，保證狀態(tài)適合接著讀東西如绸。至于讀進(jìn)來(lái)的東西嘱朽，隨便找個(gè) Collection 扔進(jìn)去就好旭贬。寫(xiě)數(shù)組就更好寫(xiě)了，先 beginArray() 寫(xiě)左中括號(hào)搪泳，然后每次用 value(val) 寫(xiě)值稀轨，最后 endArray() 寫(xiě)右中括號(hào)就好了。
對(duì)象有點(diǎn)麻煩但也不難處理岸军，讀的時(shí)候先 beginObject() 讀左大括號(hào)奋刽，然后在 hasNext() 返回 true 的時(shí)候用 nextName() 讀下一個(gè)屬性名，然后用 switch ... case ... 判斷這個(gè)屬性應(yīng)該讀進(jìn)哪個(gè)變量艰赞，并用 nextXxx() 把值讀進(jìn)這個(gè)變量佣谐，最后不要忘記 default 情況要 skipValue()，不然下面操作讀取器的狀態(tài)就不對(duì)了方妖，直到 hasNext() 返回 false狭魂，用 endObject()讀右大括號(hào)。寫(xiě)的話(huà)比較好辦吁断，就先 beginObject() 寫(xiě)左大括號(hào)趁蕊，然后不停地 name(name) value(val) 寫(xiě)屬性，完了 endObject() 寫(xiě)右大括號(hào)仔役。一個(gè)對(duì)象有一個(gè)接收 JsonReader 的構(gòu)造函數(shù)和一個(gè)接收 JsonWriter 的方法來(lái)做這一套過(guò)程掷伙。

啊聽(tīng)起來(lái)非常好，不過(guò)麻煩事兒是有繼承又兵。有繼承后有兩個(gè)問(wèn)題任柜，一是繼承的對(duì)象 Json 數(shù)據(jù)該長(zhǎng)成什么樣子，二是這個(gè)數(shù)據(jù)該怎么解析沛厨。對(duì)問(wèn)題一我思考一段時(shí)間（腦殘兒童 QAQ）決定答案是 Json 的結(jié)構(gòu)應(yīng)該和 Java 保持一致宙地，或者說(shuō)就是如果 Java 里用了繼承，那么新增的屬性應(yīng)該和原來(lái)的屬性放在同一個(gè)對(duì)象里逆皮，如果 Java 用了委托宅粥，新增的屬性就應(yīng)該放在一個(gè)新的對(duì)象里作為原來(lái)對(duì)象的屬性。對(duì)問(wèn)題二我又思考了一段時(shí)間（TAT 腦殘兒童不許笑）發(fā)現(xiàn)所謂 Json 就是一個(gè)序列化機(jī)制罷了电谣。那看看前輩是怎么寫(xiě)序列化的秽梅，于是我拿來(lái)了 Parcelable，發(fā)現(xiàn)它們的做法是先寫(xiě)祖宗的屬性剿牺，然后寫(xiě)自己的屬性企垦，讀的時(shí)侯先在構(gòu)造函數(shù)里調(diào)祖宗的構(gòu)造函數(shù)讀祖宗的屬性，然后讀自己的屬性晒来。我試圖把這個(gè)辦法搬到 Json 上钞诡。果然碰到問(wèn)題了：祖宗構(gòu)造函數(shù)和自己構(gòu)造函數(shù)都要讀大括號(hào)，然而我沒(méi)有帶那么多大括號(hào)可以讀。不過(guò)我很快想到了解決辦法：構(gòu)造函數(shù)永遠(yuǎn)永遠(yuǎn)不讀大括號(hào)荧降，把大括號(hào)留給調(diào)用構(gòu)造函數(shù)的人讀接箫，這樣就好啦（嗯大括號(hào)熟么的在這種不需要數(shù)據(jù)結(jié)構(gòu)自描述的情況下就是冗余米有錯(cuò)）√芘祝可是這樣子以后我會(huì)被人抽的列牺，因?yàn)?Json 對(duì)象不保證順序，要是逼著寫(xiě) Javascript 的在 Json 化時(shí)候必須保證順序的話(huà)我相信它會(huì)毫不猶豫去跳樓的拗窃。

于是我想到了一個(gè)辦法，就是給基類(lèi)寫(xiě)一個(gè)接口泌辫，里面有一個(gè)方法随夸。當(dāng)基類(lèi)讀 Json 讀到一個(gè)屬性自己不認(rèn)識(shí)的時(shí)候，就把屬性名和 JsonReader 對(duì)象傳給這個(gè)方法震放。這樣宾毒，子類(lèi)只要寫(xiě)一個(gè)內(nèi)部類(lèi)實(shí)現(xiàn)這個(gè)接口，在方法中看看這個(gè)屬性認(rèn)識(shí)不認(rèn)識(shí)殿遂，認(rèn)識(shí)就讀進(jìn)來(lái)诈铛，不認(rèn)識(shí)就遞歸地給自己的子類(lèi)的這個(gè)接口處理。

不過(guò)這么做還是有問(wèn)題墨礁。問(wèn)題是基類(lèi)的部分控制代碼每次寫(xiě)個(gè)基類(lèi)都得寫(xiě)一遍幢竹，得抽出來(lái)。然后我又想了好長(zhǎng)時(shí)間恩静，發(fā)現(xiàn)其實(shí)根本問(wèn)題是我有一堆屬性焕毫，我得給每個(gè)屬性在繼承樹(shù)上找到它應(yīng)該在的位置。這樣說(shuō)來(lái)驶乾，每次讀取屬性名的操作就不應(yīng)該由基類(lèi)來(lái)做了邑飒，應(yīng)該由外面的函數(shù)來(lái)做。這些類(lèi)們只實(shí)現(xiàn)一個(gè)方法 readProperty：接收一個(gè)屬性名和一個(gè) JsonReader级乐，要是自己認(rèn)得疙咸，就讀出屬性值，否則把屬性名和 JsonReader 照樣傳給父類(lèi)（如果有的話(huà)）或跳過(guò)值（如果父類(lèi)沒(méi)有 readProperty）风科。然后再寫(xiě)一個(gè)工廠方法叫 newInstanceFromJson撒轮，接收 JsonReader 返回新對(duì)象，它每次新建一個(gè)該對(duì)象的空白實(shí)例丐重，不停地讀屬性名并喂給接收屬性名那個(gè)方法腔召，直到所有屬性都讀完了，這時(shí)看看對(duì)象需要知道的屬性是不是都讀進(jìn)來(lái)了扮惦，要是沒(méi)有就返回空或報(bào)異常臀蛛，要是都讀進(jìn)來(lái)了就返回這個(gè)實(shí)例。考慮到上一篇文章所述和方便重用浊仆，我把工廠方法寫(xiě)在一個(gè)內(nèi)部類(lèi)里客峭，并要求它們繼承自 JsonCreator。JsonCreator 是個(gè)類(lèi)舔琅，里面寫(xiě)著上述工廠方法的代碼，并要求繼承者實(shí)現(xiàn) newBlankInstance 和 isComplete洲劣，前者是返回空白實(shí)例的方法备蚓，后者是判斷是否讀了所有要知道的屬性的方法。readProperty 不寫(xiě)在 JsonCreator 里的原因是否則需要實(shí)現(xiàn)者手工維護(hù) this 指針囱稽。然后我寫(xiě)一個(gè)接口 Jsonable郊尝，要求實(shí)現(xiàn)者實(shí)現(xiàn) writeToJson 和 readProperty 方法。接口定義中包含一個(gè)內(nèi)部類(lèi)叫 JsonCreator 的定義战惊，然后在文檔中要求所有實(shí)現(xiàn) Jsonable 的類(lèi)都要定義一個(gè)靜態(tài)成員叫 JsonCREATOR流昏，它是 JsonCreator 的一個(gè)子類(lèi)，其中實(shí)現(xiàn)了 newBlankInstance吞获。

嗯其實(shí)我知道 Gson 可以很隨意地把這件事做掉况凉，但是我沒(méi)有用 Gson，原因有兩個(gè)各拷。一個(gè)是我喜歡造輪子刁绒，另外一個(gè)是 Gson 這種東西一定會(huì)用一些反射，我不想用反射撤逢，我想只用語(yǔ)言的靜態(tài)特性（比如找父類(lèi)不用反射膛锭，用 super）。

但是這樣子又有點(diǎn)兒?jiǎn)栴}蚊荣，每一個(gè) readProperty 里其實(shí)是一個(gè)拿字符串做的 switch...case... 語(yǔ)句初狰，而 Java 里它的實(shí)現(xiàn)可以認(rèn)為是查一次哈希表。這樣一個(gè)屬性如果一個(gè)類(lèi)不認(rèn)識(shí)互例，那么它就會(huì)去問(wèn)它父類(lèi)奢入，父類(lèi)要再不認(rèn)識(shí)就會(huì)問(wèn)父類(lèi)的父類(lèi)……這樣問(wèn)下去可能一直要查掉整個(gè)繼承鏈的長(zhǎng)度，好慢的感覺(jué)媳叨。

不過(guò)這個(gè)問(wèn)題是沒(méi)辦法的事兒腥光，我們可以把它抽象一下：有 N 個(gè)類(lèi)，它們組成一個(gè)有根森林（邊代表繼承關(guān)系）糊秆；有 M 個(gè)屬性武福，每個(gè)屬性可以被某些類(lèi)擁有；現(xiàn)在每次給一個(gè)類(lèi)和一個(gè)屬性痘番，查詢(xún)從該類(lèi)到根的路徑上捉片，距該類(lèi)最近的有該屬性的類(lèi)平痰。這個(gè)問(wèn)題還有兩個(gè)版本，就是可不可以動(dòng)態(tài)添加類(lèi)和屬性伍纫，動(dòng)態(tài)語(yǔ)言對(duì)應(yīng)著可以動(dòng)態(tài)添加類(lèi)和屬性的版本宗雇，靜態(tài)語(yǔ)言則相反。這個(gè)問(wèn)題里預(yù)處理對(duì)應(yīng)著編譯時(shí)莹规，而查詢(xún)處理對(duì)應(yīng)著運(yùn)行時(shí)赔蒲。

暴力的方法有兩個(gè)。一是給每個(gè)節(jié)點(diǎn)存它擁有的屬性良漱，然后每次查詢(xún)從某個(gè)類(lèi)開(kāi)始逐個(gè)查父節(jié)點(diǎn)一直到根舞虱，預(yù)處理復(fù)雜度 O(M + N)，查詢(xún)復(fù)雜度 O(N) （最壞情況深度等于類(lèi)的個(gè)數(shù)母市，并且認(rèn)為判斷表里是否有一個(gè)屬性是 O(1) 的）砾嫉。另一個(gè)是給每個(gè)節(jié)點(diǎn)存一個(gè)表，里面存著它擁有每個(gè)屬性的最近祖先是誰(shuí)窒篱，查詢(xún)時(shí)直接查表即可，預(yù)處理復(fù)雜度 O(MN)舶沿，查詢(xún)復(fù)雜度 O(1)墙杯。而且前一個(gè)方法動(dòng)態(tài)添加刪除類(lèi)和屬性效率較高。

OI 里很流行 log 記號(hào)括荡，帶 log 的算法我只想了一個(gè)高镐。先考慮每個(gè)屬性只被一個(gè)類(lèi)擁有的情況，這時(shí)我們可以預(yù)處理每個(gè)類(lèi)的深度和它的 1, 2, 4, 8, ... 輩祖宗是誰(shuí)畸冲，這樣可以在 O(log N) 時(shí)間內(nèi)找到它的 N 輩祖宗嫉髓。查詢(xún)時(shí)我們找到這個(gè)類(lèi)，找到擁有這個(gè)屬性的那個(gè)類(lèi)邑闲，如果“這個(gè)類(lèi)”比“那個(gè)類(lèi)”深度更淺算行，那就找不到，否則求它們的深度差苫耸，找“這個(gè)類(lèi)”的“深度差”輩祖宗州邢，看是不是“那個(gè)類(lèi)”。然后考慮每個(gè)屬性被多個(gè)類(lèi)擁有的情況褪子，先找到這個(gè)類(lèi)量淌，然后找到擁有這個(gè)屬性的 DFS 序恰小于這個(gè)類(lèi)的那個(gè)類(lèi)。然后把“那個(gè)類(lèi)”到根路徑上所有有這個(gè)屬性的類(lèi)做成一個(gè)表嫌褪，在這個(gè)表里找到深度最深的是“這個(gè)類(lèi)”的祖宗的類(lèi)呀枢。尋找可以用二分的辦法，因?yàn)槿绻粋€(gè)類(lèi)是“這個(gè)類(lèi)”的祖宗笼痛，那么它的祖宗也是“這個(gè)類(lèi)”的祖宗裙秋。二分法做起來(lái)可以這么辦：預(yù)處理出“那個(gè)類(lèi)”到根的路徑里距它 1, 2, 4, 8, ... 近的有該屬性的類(lèi)琅拌，然后就可以折半了。二分后的判斷就用之前簡(jiǎn)單情況的辦法残吩，這樣整個(gè)方法财忽，預(yù)處理的復(fù)雜度是 O((N + M) log N)，查詢(xún)的復(fù)雜度是 O(log N * log M)泣侮。不過(guò)這個(gè)方法不支持動(dòng)態(tài)添加刪除類(lèi)和屬性即彪，要支持的的話(huà)應(yīng)該要?jiǎng)討B(tài)樹(shù)什么的我不會(huì) T_T。