Scala不可變集合
Scala不可變集合的設(shè)計目標(biāo)是提供高效又安全的實現(xiàn)。這些集合中的大部分都是用高級技巧來在集合的不同版本之間“共享”內(nèi)存。其中較長使用到的是Vector和List。
在一般的編程任務(wù)中，不可變集合有很多超出可變集合的優(yōu)點。尤其重要的一點是不可變集合可以在多線程之中共享而無需加鎖。
Vector內(nèi)部結(jié)構(gòu)
Scala的Vector實現(xiàn)為一組嵌套數(shù)組，在分割和連接時非常有效率。適用于大部分通用算法，因為它有高效的下標(biāo)計算能力，以及能夠在使用像+:和++方法時共享大部分內(nèi)部結(jié)構(gòu)的能力。
Vector采用分支系數(shù)為32的樹狀數(shù)據(jù)結(jié)構(gòu)，分支因子是每個父節(jié)點允許擁有的最大子節(jié)點的數(shù)目。其隨機(jī)訪問（搜索或修改）復(fù)雜度是log_32(N)，使用32位整數(shù)下標(biāo)時在JVM上是個效率不錯的小常量，即使對很大的N來說都近似一個常量。
Vector是個由元素的下標(biāo)組成的前綴樹（trie），前綴樹是給定路徑上的所有子節(jié)點功用某種形式的公共鍵值。我們可以根據(jù)任何下標(biāo)的二進(jìn)制形式得到查找路徑，實現(xiàn)高效的元素查找。
Vector復(fù)制過程中的結(jié)構(gòu)共享原理
在實際應(yīng)用中，為了保持變量的不可變性，對有用的集合進(jìn)行復(fù)制通常是必要的。假設(shè)有一個包含100 000個元素的Vector，需要得到一個副本，并替換掉原Vector的第8個元素，此時如果構(gòu)造一個全新的100 000個元素的Vector將會是極其低效的。
為了兼顧高效和不可變性，可以通過共享原始Vector中的不變部分，而以某種方式表示變化部分，那么就可以高效地“創(chuàng)建”新Vector了。這種思想稱之為結(jié)構(gòu)共享。
如果其他線程中的代碼正在對原始Vector做其他不同的操作，對原始的Vector的復(fù)制不會影響該操作，因為原Vector沒有被修改。這樣，只要對舊版本有一個或多個引用，就可以創(chuàng)建一個Vector的“歷史”版本。直到對舊版本的引用消失為止，舊版本才會被垃圾回收。
下面的圖示解釋了創(chuàng)建并修改副本過程中結(jié)構(gòu)共享的原理：
使用#1來引用原樹的根節(jié)點：
現(xiàn)在假設(shè)要在2和3之間插入2.5，要創(chuàng)建一個新的副本，我們并不需要修改原來的樹結(jié)構(gòu)，而是創(chuàng)建新樹。
值得注意的是，原來的樹（#1）仍然存在，但我們又創(chuàng)建了新的根（#2）和新的節(jié)點。創(chuàng)建新的樹共享重用了原來的大部分節(jié)點，這樣有助于降低修改集合的開銷。
Vector查找原理
Scala的Vector集合非常類似于一個分支系數(shù)為32的下標(biāo)前綴樹。關(guān)鍵區(qū)別在于Vector用一個數(shù)組來表示分支。這使整個結(jié)構(gòu)變成數(shù)組的數(shù)組（嵌套數(shù)組）。
下圖是分支系數(shù)為2的二進(jìn)制Vector：
其中有三個基本素組：display0、display1和display2.這些數(shù)組代表原始前綴樹的深度。每個顯示元素（display element）都是一個更深一層的的嵌套數(shù)組（display0是元素的數(shù)組，display1是數(shù)組的數(shù)組，display2是數(shù)組的數(shù)組的數(shù)組）。查找集合元素的步驟是先判斷其深度，然后用跟前綴樹一樣的方式確定元素所在的數(shù)組。比如找數(shù)字4，其深度為2，所以先選擇display2數(shù)組，4的二進(jìn)制形式100，所以外層數(shù)組是下標(biāo)為1的位置上，中層數(shù)組下標(biāo)為0，最后4就位于結(jié)果數(shù)組的下標(biāo)0的位置上。
二進(jìn)制前綴樹根據(jù)下標(biāo)隨機(jī)取值的復(fù)雜度是log_2(n)，Scala的Vector的分支系數(shù)為32，那么訪問任何元素的時間復(fù)雜度是log_32(n)，對32位的下標(biāo)也就大約是7，對64位大約是13.而對于較小的集合，排序的開銷也會降低，所以訪問速度會更快。所以隨機(jī)訪問的時間復(fù)雜度與前綴樹的大小成正比。
小結(jié)
Scala的Vector為32分支，這除了帶來查找時間和修改時間可以隨集合大小伸縮外，它還提供了不錯的緩存一致性，因為集合里相近的元素有很大可能位于同一個內(nèi)存數(shù)組里。其高效結(jié)合不可變所帶來的線程安全使之成為庫里最強(qiáng)大的有序集合。
Scala的序列類型中Vector和List數(shù)據(jù)結(jié)構(gòu)都是很常用的，Vector的所有操作都是O(1)（常數(shù)時間），而List對于那些需要訪問頭部以為元素的操作都需要O(n)操作，所以只在頻繁執(zhí)行頭尾分解的情況下，推薦使用List。
轉(zhuǎn)載請注明作者Jason Ding及其出處
jasonding.top
Github博客主頁(http://blog.jasonding.top/)
CSDN博客(http://blog.csdn.net/jasonding1354)
簡書主頁(http://www.itdecent.cn/users/2bd9b48f6ea8/latest_articles)
Google搜索jasonding1354進(jìn)入我的博客主頁
