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