Scala不可變集合
Scala不可變集合的設(shè)計(jì)目標(biāo)是提供高效又安全的實(shí)現(xiàn)。這些集合中的大部分都是用高級(jí)技巧來在集合的不同版本之間“共享”內(nèi)存量淌。其中較長(zhǎng)使用到的是Vector和List骗村。
在一般的編程任務(wù)中，不可變集合有很多超出可變集合的優(yōu)點(diǎn)类少。尤其重要的一點(diǎn)是不可變集合可以在多線程之中共享而無需加鎖叙身。
Vector內(nèi)部結(jié)構(gòu)
Scala的Vector實(shí)現(xiàn)為一組嵌套數(shù)組，在分割和連接時(shí)非常有效率硫狞。適用于大部分通用算法信轿，因?yàn)樗懈咝У南聵?biāo)計(jì)算能力，以及能夠在使用像+:和++方法時(shí)共享大部分內(nèi)部結(jié)構(gòu)的能力残吩。
Vector采用分支系數(shù)為32的樹狀數(shù)據(jù)結(jié)構(gòu)财忽，分支因子是每個(gè)父節(jié)點(diǎn)允許擁有的最大子節(jié)點(diǎn)的數(shù)目。其隨機(jī)訪問（搜索或修改）復(fù)雜度是log_32(N)泣侮，使用32位整數(shù)下標(biāo)時(shí)在JVM上是個(gè)效率不錯(cuò)的小常量即彪，即使對(duì)很大的N來說都近似一個(gè)常量。
Vector是個(gè)由元素的下標(biāo)組成的前綴樹（trie），前綴樹是給定路徑上的所有子節(jié)點(diǎn)功用某種形式的公共鍵值隶校。我們可以根據(jù)任何下標(biāo)的二進(jìn)制形式得到查找路徑漏益，實(shí)現(xiàn)高效的元素查找。
Vector復(fù)制過程中的結(jié)構(gòu)共享原理
在實(shí)際應(yīng)用中深胳，為了保持變量的不可變性绰疤，對(duì)有用的集合進(jìn)行復(fù)制通常是必要的。假設(shè)有一個(gè)包含100 000個(gè)元素的Vector舞终，需要得到一個(gè)副本轻庆，并替換掉原Vector的第8個(gè)元素，此時(shí)如果構(gòu)造一個(gè)全新的100 000個(gè)元素的Vector將會(huì)是極其低效的敛劝。
為了兼顧高效和不可變性余爆，可以通過共享原始Vector中的不變部分，而以某種方式表示變化部分夸盟，那么就可以高效地“創(chuàng)建”新Vector了蛾方。這種思想稱之為結(jié)構(gòu)共享。
如果其他線程中的代碼正在對(duì)原始Vector做其他不同的操作满俗，對(duì)原始的Vector的復(fù)制不會(huì)影響該操作转捕，因?yàn)樵璙ector沒有被修改。這樣唆垃，只要對(duì)舊版本有一個(gè)或多個(gè)引用，就可以創(chuàng)建一個(gè)Vector的“歷史”版本痘儡。直到對(duì)舊版本的引用消失為止辕万，舊版本才會(huì)被垃圾回收。
下面的圖示解釋了創(chuàng)建并修改副本過程中結(jié)構(gòu)共享的原理：
使用#1來引用原樹的根節(jié)點(diǎn)：
現(xiàn)在假設(shè)要在2和3之間插入2.5沉删，要?jiǎng)?chuàng)建一個(gè)新的副本渐尿，我們并不需要修改原來的樹結(jié)構(gòu)，而是創(chuàng)建新樹矾瑰。
值得注意的是砖茸，原來的樹（#1）仍然存在，但我們又創(chuàng)建了新的根（#2）和新的節(jié)點(diǎn)殴穴。創(chuàng)建新的樹共享重用了原來的大部分節(jié)點(diǎn)凉夯，這樣有助于降低修改集合的開銷。
Vector查找原理
Scala的Vector集合非常類似于一個(gè)分支系數(shù)為32的下標(biāo)前綴樹采幌。關(guān)鍵區(qū)別在于Vector用一個(gè)數(shù)組來表示分支劲够。這使整個(gè)結(jié)構(gòu)變成數(shù)組的數(shù)組（嵌套數(shù)組）。
下圖是分支系數(shù)為2的二進(jìn)制Vector：
其中有三個(gè)基本素組：display0休傍、display1和display2.這些數(shù)組代表原始前綴樹的深度征绎。每個(gè)顯示元素（display element）都是一個(gè)更深一層的的嵌套數(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，那么訪問任何元素的時(shí)間復(fù)雜度是log_32(n)犀农，對(duì)32位的下標(biāo)也就大約是7惰赋，對(duì)64位大約是13.而對(duì)于較小的集合，排序的開銷也會(huì)降低呵哨，所以訪問速度會(huì)更快赁濒。所以隨機(jī)訪問的時(shí)間復(fù)雜度與前綴樹的大小成正比孟害。
小結(jié)
Scala的Vector為32分支，這除了帶來查找時(shí)間和修改時(shí)間可以隨集合大小伸縮外挨务，它還提供了不錯(cuò)的緩存一致性，因?yàn)榧侠锵嘟脑赜泻艽罂赡芪挥谕粋€(gè)內(nèi)存數(shù)組里丁侄。其高效結(jié)合不可變所帶來的線程安全使之成為庫(kù)里最強(qiáng)大的有序集合朝巫。
Scala的序列類型中Vector和List數(shù)據(jù)結(jié)構(gòu)都是很常用的，Vector的所有操作都是O(1)（常數(shù)時(shí)間）劈猿，而List對(duì)于那些需要訪問頭部以為元素的操作都需要O(n)操作，所以只在頻繁執(zhí)行頭尾分解的情況下庐镐，推薦使用List变逃。
轉(zhuǎn)載請(qǐng)注明作者Jason Ding及其出處
jasonding.top
Github博客主頁(yè)(http://blog.jasonding.top/)
CSDN博客(http://blog.csdn.net/jasonding1354)
簡(jiǎn)書主頁(yè)(http://www.reibang.com/users/2bd9b48f6ea8/latest_articles)
Google搜索jasonding1354進(jìn)入我的博客主頁(yè)
