Trie樹(shù)用來(lái)給字符串排序的時(shí)候有一個(gè)好處：邊讀邊排序，但是讀完之后要輸出的時(shí)候麻煩來(lái)了。經(jīng)過(guò)測(cè)試，用26W個(gè)word建立的Trie中，空白位是使用位的20倍左右，那么在Trie比較大的時(shí)候當(dāng)然也就比較慢了。這篇文章討論的優(yōu)化主要是去避免訪(fǎng)問(wèn)這些空白位，實(shí)現(xiàn)方式無(wú)關(guān)（數(shù)組或指針？）。
首先想到的一個(gè)方法是：在insert的時(shí)候順便標(biāo)記這個(gè)節(jié)點(diǎn)有哪些子節(jié)點(diǎn)。因?yàn)榭偣仓挥?6種可能性，那么自然也就想到了用一個(gè)int作為flag，如果0位置1則表示有‘a(chǎn)’這個(gè)子節(jié)點(diǎn)。
第一步（記錄）完成了，下面我們來(lái)看如何來(lái)使用該記錄？熟悉位移的同學(xué)可能已經(jīng)想到：可以使用x&-x來(lái)計(jì)算出最低位為1的數(shù)。但是遺憾的是這個(gè)并不是我們想要的結(jié)果，因?yàn)榈玫降氖?^N，我們想要的是這個(gè)N。好的，最笨的一種方法出來(lái)了：
int t[] = new int[1<<26];
t[1<<0] = 0.....
非常遺憾的是我們申請(qǐng)不了這么大的空間。那么，問(wèn)題就是將一些離散的數(shù)通過(guò)數(shù)組建立映射關(guān)系，很自然地就會(huì)聯(lián)想到Hash。怎么使用Hash呢？我嘗試了一下，從2^0到2^26對(duì)29取余數(shù)為：
1.2.4.8.16.3.6.12.24.19.9.18.7.14.28.27.25.21.13.26.23.17.5.10.20.11
沒(méi)有看錯(cuò)，沒(méi)有一個(gè)是相同的！這樣的話(huà)就可以?xún)H僅使用一個(gè)大小不到30的數(shù)組就可以搞定。同樣遺憾的時(shí)候，這里用到了取余數(shù)的操作，要知道這個(gè)還算比較大的，可能一不小心就把我們辛辛苦苦省下來(lái)的時(shí)間又葬送掉了。那么有沒(méi)有其他的方法呢？還是回到最笨的方法的思路上：
如果我們申請(qǐng)不了int[1<<26]，那申請(qǐng)int[1<<13]總是可以的吧？
為什么這么做呢？因?yàn)樯暾?qǐng)不了這么大的空間！這時(shí)候就把這個(gè)問(wèn)題換成兩半了，比如在節(jié)點(diǎn)I出的標(biāo)志位flag：
int lowHalf = flag&((1<<14)-1);
int highHalf = (flag>>13)&((1<<14)-1);
while(lowHalf > 0){
int i = lowHalf&-lowHalf;
int j = t[i];
// do someting
}
while(highHalf > 0){
int i = highHalf&-highHalf;
int j = t[i]+13;
// do someting
}
和最笨的那種方法相比，只是多了一次操作而已。
好了現(xiàn)在來(lái)看最后一種方法，就不多寫(xiě)了：
switch(flag&-flag){
case 1<<0:
case 1<<1:
case 1<<2:
.....
}
PS：直接用一個(gè)整數(shù)來(lái)表示：
沒(méi)有子節(jié)點(diǎn)為:0
a節(jié)點(diǎn)為:1 << 0
b節(jié)點(diǎn)為：1 << 1
......
z節(jié)點(diǎn)為: 1 << 25
最后還需一位來(lái)表示是否單詞 1 << 26,當(dāng)然，如果沒(méi)有子節(jié)點(diǎn)，自然是單詞了。
判斷是否有z節(jié)點(diǎn)只要 &(1<<25)就好
如果遍歷，可以先 | 0 一下減少是最終節(jié)點(diǎn)的操作
喜歡 
頂
難過(guò)
囧
圍觀(guān)
無(wú)聊
