來到周末，小匹夫終于有精力和時間來更新下部落格了。前段時間小匹夫讀過一份代碼，對其中各種資料結構靈活的使用贊不絕口，同時也大大激發了小匹夫對各種資料結構進行梳理和總結的欲望。正好最近也拜讀了若幹大神的文章，覺得總結下常用的資料結構以供自己也能靈活的使用變得刻不容緩。那麼還是從小匹夫的工作内容入手，就談談在平時使用U3D時經常用到的資料結構和各種資料結構的應用場景吧。
1.幾種常見的資料結構
這裡主要總結下小匹夫在工作中常碰到的幾種資料結構：Array，ArrayList，List<T>，LinkedList<T>，Queue<T>，Stack<T>，Dictionary<K,T>
數組Array：
數組是最簡單的資料結構。其具有如下特點：
- 數組存儲在連續的記憶體上。
- 數組的内容都是相同類型。
- 數組可以直接通過下标通路。
數組Array的建立：
1 int size = 5;
2 int[] test = new int[size]; 建立一個新的數組時将在 CLR 托管堆中配置設定一塊連續的記憶體空間，來盛放數量為size，類型為所聲明類型的數組元素。如果類型為值類型，則将會有size個未裝箱的該類型的值被建立。如果類型為引用類型，則将會有size個相應類型的引用被建立。
由于是在連續記憶體上存儲的，是以它的索引速度非常快，通路一個元素的時間是恒定的也就是說與數組的元素數量無關，而且指派與修改元素也很簡單。
string[] test2 = new string[3];
//指派
test2[0] = "chen";
test2[1] = "j";
test2[2] = "d";
//修改
test2[0] = "chenjd"; 但是有優點，那麼就一定會伴随着缺點。由于是連續存儲，是以在兩個元素之間插入新的元素就變得不友善。而且就像上面的代碼所顯示的那樣，聲明一個新的數組時，必須指定其長度，這就會存在一個潛在的問題，那就是當我們聲明的長度過長時，顯然會浪費記憶體，當我們聲明長度過短的時候，則面臨這溢出的風險。這就使得寫代碼像是投機，小匹夫很厭惡這樣的行為！針對這種缺點，下面隆重推出ArrayList。
ArrayList：
為了解決數組建立時必須指定長度以及隻能存放相同類型的缺點而推出的資料結構。ArrayList是System.Collections命名空間下的一部分，是以若要使用則必須引入System.Collections。正如上文所說，ArrayList解決了數組的一些缺點。
- 不必在聲明ArrayList時指定它的長度，這是由于ArrayList對象的長度是按照其中存儲的資料來動态增長與縮減的。
- ArrayList可以存儲不同類型的元素。這是由于ArrayList會把它的元素都當做Object來處理。因而，加入不同類型的元素是允許的。
ArrayList的操作：
ArrayList test3 = new ArrayList();
//新增資料
test3.Add("chen");
test3.Add("j");
test3.Add("d");
test3.Add("is");
test3.Add(25);
//修改資料
test3[4] = 26;
//删除資料
test3.RemoveAt(4); 說了那麼一堆”優點“，也該說說缺點了吧。為什麼要給”優點”打上引号呢？那是因為ArrayList可以存儲不同類型資料的原因是由于把所有的類型都當做Object來做處理，也就是說ArrayList的元素其實都是Object類型的，辣麼問題就來了。
- ArrayList不是類型安全的。因為把不同的類型都當做Object來做處理，很有可能會在使用ArrayList時發生類型不比對的情況。
- 如上文所訴，數組存儲值類型時并未發生裝箱，但是ArrayList由于把所有類型都當做了Object，是以不可避免的當插入值類型時會發生裝箱操作，在索引取值時會發生拆箱操作。這能忍嗎？
注：為何說頻繁的沒有必要的裝箱和拆箱不能忍呢？且聽小匹夫慢慢道來：所謂裝箱 (boxing)：就是值類型執行個體到對象的轉換(百度百科)。那麼拆箱：就是将引用類型轉換為值類型咯（還是來自百度百科）。下面舉個栗子~
//裝箱，将String類型的值FanyoyChenjd指派給對象。
int info = 1989;
object obj=(object)info;
//拆箱，從Obj中提取值給info
object obj = 1;
int info = (int)obj; 那麼結論呢？好吧，請允許小匹夫很low再次引用百度百科。顯然，從原理上可以看出，裝箱時，生成的是全新的引用對象，這會有時間損耗，也就是造成效率降低。
List<T>泛型List
為了解決ArrayList不安全類型與裝箱拆箱的缺點，是以出現了泛型的概念，作為一種新的數組類型引入。也是工作中經常用到的數組類型。和ArrayList很相似，長度都可以靈活的改變，最大的不同在于在聲明List集合時，我們同時需要為其聲明List集合内資料的對象類型，這點又和Array很相似，其實List<T>内部使用了Array來實作。
List<string> test4 = new List<string>();
//新增資料
test4.Add(“Fanyoy”);
test4.Add(“Chenjd”);
//修改資料
test4[1] = “murongxiaopifu”;
//移除資料
test4.RemoveAt(0); 這麼做最大的好處就是
- 即確定了類型安全。
- 也取消了裝箱和拆箱的操作。
- 它融合了Array可以快速通路的優點以及ArrayList長度可以靈活變化的優點。
LinkedList<T>
也就是連結清單了。和上述的數組最大的不同之處就是在于連結清單在記憶體存儲的排序上可能是不連續的。這是由于連結清單是通過上一個元素指向下一個元素來排列的，是以可能不能通過下标來通路。如圖
既然連結清單最大的特點就是存儲在記憶體的空間不一定連續，那麼連結清單相對于數組最大優勢和劣勢就顯而易見了。
- 向連結清單中插入或删除節點無需調整結構的容量。因為本身不是連續存儲而是靠各對象的指針所決定，是以添加元素和删除元素都要比數組要有優勢。
- 連結清單适合在需要有序的排序的情境下增加新的元素，這裡還拿數組做對比，例如要在數組中間某個位置增加新的元素，則可能需要移動移動很多元素，而對于連結清單而言可能隻是若幹元素的指向發生變化而已。
- 有優點就有缺點，由于其在記憶體空間中不一定是連續排列，是以通路時候無法利用下标，而是必須從頭結點開始，逐次周遊下一個節點直到尋找到目标。是以當需要快速通路對象時，數組無疑更有優勢。
綜上，連結清單适合元素數量不固定，需要經常增減節點的情況。
關于連結清單的使用，MSDN上有詳細的例子。
Queue<T>
在Queue<T>這種資料結構中，最先插入在元素将是最先被删除；反之最後插入的元素将最後被删除，是以隊列又稱為“先進先出”（FIFO—first in first out）的線性表。通過使用Enqueue和Dequeue這兩個方法來實作對 Queue<T> 的存取。
一些需要注意的地方：
- 先進先出的情景。
- 預設情況下，Queue<T>的初始容量為32， 增長因子為2.0。
- 當使用Enqueue時，會判斷隊列的長度是否足夠，若不足，則依據增長因子來增加容量，例如當為初始的2.0時，則隊列容量增長2倍。
- 乏善可陳。
關于Queue<T>的使用方法，MSDN上也有相應的例子。
Stack<T>
與Queue<T>相對，當需要使用後進先出順序（LIFO）的資料結構時，我們就需要用到Stack<T>了。
- 後進先出的情景。
- 預設容量為10。
- 使用pop和push來操作。
同樣，在這裡你也可以看到大量Stack<T>的例子。
Dictionary<K,T>
字典這東西，小匹夫可是喜歡的不得了。看官們自己也可以想想字典是不是很招人喜歡，建立一個字典之後就可以往裡面扔東西，增加、删除、通路那叫一個快字了得。但是直到小匹夫日前看了一個大神的文章，才又想起了那句話“啥好事咋能讓你都占了呢”。那麼字典背後到底隐藏着什麼迷霧，撥開重重迷霧之後，是否才是真相？且聽下回分。。。等等，應該是下面就讓我們來分析一下字典吧。
提到字典就不得不說Hashtable哈希表以及Hashing（哈希，也有叫散列的），因為字典的實作方式就是哈希表的實作方式，隻不過字典是類型安全的，也就是說當建立字典時，必須聲明key和item的類型，這是第一條字典與哈希表的差別。關于哈希表的内容推薦看下這篇部落格哈希表。關于哈希，簡單的說就是一種将任意長度的消息壓縮到某一固定長度，比如某學校的學生學号範圍從00000~99999，總共5位數字，若每個數字都對應一個索引的話，那麼就是100000個索引，但是如果我們使用後3位作為索引，那麼索引的範圍就變成了000~999了，當然會沖突的情況，這種情況就是哈希沖突(Hash Collisions)了。扯遠了，關于具體的實作原理還是去看小匹夫推薦的那篇部落格吧，當然那篇部落格上面那個大大的轉字也是蠻刺眼的。。。
回到Dictionary<K,T>，我們在對字典的操作中各種時間上的優勢都享受到了，那麼它的劣勢到底在哪呢？對嘞，就是空間。以空間換時間，通過更多的記憶體開銷來滿足我們對速度的追求。在建立字典時，我們可以傳入一個容量值，但實際使用的容量并非該值。而是使用“不小于該值的最小質數來作為它使用的實際容量，最小是3。”（老趙），當有了實際容量之後，并非直接實作索引，而是通過建立額外的2個數組來實作間接的索引，即int[] buckets和Entry[] entries兩個數組（即buckets中儲存的其實是entries數組的下标），這裡就是第二條字典與哈希表的差別，還記得哈希沖突嗎？對，第二個差別就是處理哈希沖突的政策是不同的！字典會采用額外的資料結構來處理哈希沖突，這就是剛才提到的數組之一buckets桶了，buckets的長度就是字典的真實長度，因為buckets就是字典每個位置的映射，然後buckets中的每個元素都是一個連結清單，用來存儲相同哈希的元素，然後再配置設定存儲空間。
是以，我們面臨的情況就是，即便我們建立了一個空的字典，那麼伴随而來的是2個長度為3的數組。是以當處理的資料不多時，還是慎重使用字典為好，很多情況下使用數組也是可以接受的。
2.幾種常見資料結構的使用情景
Array | 需要處理的元素數量确定并且需要使用下标時可以考慮，不過建議使用List<T> |
ArrayList | 不推薦使用，建議用List<T> |
List<T>泛型List | 需要處理的元素數量不确定時 通常建議使用 |
LinkedList<T> | 連結清單适合元素數量不固定，需要經常增減節點的情況，2端都可以增減 |
Queue<T> | 先進先出的情況 |
Stack<T> | 後進先出的情況 |
Dictionary<K,T> | 需要鍵值對，快速操作 |
裝模作樣的聲明一下：本博文章若非特殊注明皆為原創，若需轉載請保留原文連結及作者資訊慕容小匹夫
本作品采用知識共享署名-非商業性使用-相同方式共享 2.5 中國大陸許可協定進行許可，我的部落格歡迎複制共享，但在同時，希望保留我的署名權陳嘉棟（慕容小匹夫），并且，不得用于商業用途。如您有任何疑問或者授權方面的協商，請給我留言。
知乎專欄：
Runtime
聯系方式：
Email：[email protected]