新聞中心
| Data Structure | Add | Find | Delete | GetByIndex |
| Array (T[]) |
O(n)
創(chuàng)新互聯(lián)建站主要從事做網(wǎng)站、網(wǎng)站設(shè)計、網(wǎng)頁設(shè)計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)清鎮(zhèn),10多年網(wǎng)站建設(shè)經(jīng)驗,價格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):18980820575 |
O(n) |
O(n) |
O(1) |
| Linked list (LinkedList |
O(1) |
O(n) |
O(n) |
O(n) |
| Resizable array list (List |
O(1) |
O(n) |
O(n) |
O(1) |
| Stack (Stack |
O(1) |
- |
O(1) |
- |
| Queue (Queue |
O(1) |
- |
O(1) |
- |
| Hash table (Dictionary |
O(1) |
O(1) |
O(1) |
- |
Tree-based dictionary (SortedDictionary |
O(log n) |
O(log n) |
O(log n) |
- |
| Hash table based set (HashSet |
O(1) |
O(1) |
O(1) |
- |
| Tree based set (SortedSet |
O(log n) |
O(log n) |
O(log n) |
- |
如何選擇數(shù)據(jù)結(jié)構(gòu)
Array (T[])
- 當(dāng)元素的數(shù)量是固定的,并且需要使用下標(biāo)時。
Linked list (LinkedList
- 當(dāng)元素需要能夠在列表的兩端添加時。否則使用 List
。
Resizable array list (List
- 當(dāng)元素的數(shù)量不是固定的,并且需要使用下標(biāo)時。
Stack (Stack
- 當(dāng)需要實現(xiàn) LIFO(Last In First Out)時。
Queue (Queue
- 當(dāng)需要實現(xiàn) FIFO(First In First Out)時。
Hash table (Dictionary
- 當(dāng)需要使用鍵值對(Key-Value)來快速添加和查找,并且元素沒有特定的順序時。
Tree-based dictionary (SortedDictionary
- 當(dāng)需要使用價值對(Key-Value)來快速添加和查找,并且元素根據(jù) Key 來排序時。
Hash table based set (HashSet
- 當(dāng)需要保存一組唯一的值,并且元素沒有特定順序時。
Tree based set (SortedSet
- 當(dāng)需要保存一組唯一的值,并且元素需要排序時。
Array
在計算機程序設(shè)計中,數(shù)組(Array)是最簡單的而且應(yīng)用最廣泛的數(shù)據(jù)結(jié)構(gòu)之一。在任何編程語言中,數(shù)組都有一些共性:
- 數(shù)組中的內(nèi)容是使用連續(xù)的內(nèi)存(Contiguous Memory)來存儲的。
- 數(shù)組中的所有元素必須是相同的類型,或者類型的衍生類型。因此數(shù)組又被認(rèn)為是同質(zhì)數(shù)據(jù)結(jié)構(gòu)(Homegeneous Data Structures)。
- 數(shù)組的元素可以直接被訪問。比如你需要訪問數(shù)組的第 i 個元素,則可以直接使用 arrayName[i] 來訪問。
對于數(shù)組的常規(guī)操作包括:
- 分配空間(Allocation)
- 數(shù)據(jù)訪問(Accessing)
在 C# 中,可以通過如下的方式聲明數(shù)組變量。
1 int allocationSize = 10; 2 bool[] booleanArray = new bool[allocationSize]; 3 FileInfo[] fileInfoArray = new FileInfo[allocationSize];
上面的代碼將在 CLR 托管堆中分配一塊連續(xù)的內(nèi)存空間,用以容納數(shù)量為 allocationSize ,類型為 arrayType 的數(shù)組元素。如果 arrayType 為值類型,則將會有 allocationSize 個未封箱(unboxed)的 arrayType 值被創(chuàng)建。如果 arrayType 為引用類型,則將會有 allocationSize 個 arrayType 類型的引用被創(chuàng)建。
如果我們?yōu)?FileInfo[] 數(shù)組中的一些位置賦上值,則引用關(guān)系為下圖所示。
.NET 中的數(shù)組都支持對元素的直接讀寫操作。語法如下:
1 // 讀數(shù)組元素 2 bool b = booleanArray[7]; 3 4 // 寫數(shù)組元素 5 booleanArray[0] = false;
訪問一個數(shù)組元素的時間復(fù)雜度為 O(1),因此對數(shù)組的訪問時間是恒定的。也就是說,與數(shù)組中包含的元素數(shù)量沒有直接關(guān)系,訪問一個元素的時間是相同的。
#p#
ArrayList
由于數(shù)組是固定長度的,并且數(shù)組中只能存儲同一種類型或類型的衍生類型。這在使用中會受到一些限制。.NET 提供了一種數(shù)據(jù)結(jié)構(gòu) ArrayList 來解決這些問題。
1 ArrayList countDown = new ArrayList();
2 countDown.Add(3);
3 countDown.Add(2);
4 countDown.Add(1);
5 countDown.Add("blast off!");
6 countDown.Add(new ArrayList());ArrayList 是長度可變的數(shù)組,并且它可以存儲不同類型的元素。
但這些靈活性是以犧牲性能為代價的。在上面 Array 的描述中,我們知道 Array 在存儲值類型時是采用未裝箱(unboxed)的方式。由于 ArrayList 的 Add 方法接受 object 類型的參數(shù),導(dǎo)致如果添加值類型的值會發(fā)生裝箱(boxing)操作。這在頻繁讀寫 ArrayList 時會產(chǎn)生額外的開銷,導(dǎo)致性能下降。
List
當(dāng) .NET 中引入泛型功能后,上面 ArrayList 所帶來的性能代價可以使用泛型來消除。.NET 提供了新的數(shù)組類型 List
泛型允許開發(fā)人員在創(chuàng)建數(shù)據(jù)結(jié)構(gòu)時推遲數(shù)據(jù)類型的選擇,直到使用時才確定選擇哪種類型。泛型(Generics)的主要優(yōu)點包括:
- 類型安全(Type Safety):使用泛型定義的類型,在使用時僅能使用指定的類型或類型的衍生類型。
- 性能(Performance):泛型移除了運行時類型檢測,消除了裝箱和拆箱的開銷。
- 可重用(Reusability):泛型打破了數(shù)據(jù)結(jié)構(gòu)與存儲數(shù)據(jù)類型之間的緊耦合。這提高了數(shù)據(jù)結(jié)構(gòu)的可重用性。
List
1 // 創(chuàng)建 int 類型列表 2 ListmyFavoriteIntegers = new List (); 3 4 // 創(chuàng)建 string 類型列表 5 List friendsNames = new List ();
List
1 ListpowersOf2 = new List (); 2 3 powersOf2.Add(1); 4 powersOf2.Add(2); 5 6 powersOf2[1] = 10; 7 8 int sum = powersOf2[1] + powersOf2[2];
List
Queue
當(dāng)我們需要使用先進先出順序(FIFO)的數(shù)據(jù)結(jié)構(gòu)時,.NET 為我們提供了 Queue
Queue
默認(rèn)情況下,Queue
Enqueue 方法會判斷 Queue
默認(rèn)情況下,增長因子(growth factor)的值為 2.0,所以內(nèi)部數(shù)組的長度會增加一倍。也可以通過構(gòu)造函數(shù)中指定增長因子。Queue
Dequeue 方法根據(jù) head 索引返回當(dāng)前元素,之后將 head 索引指向 null,再遞增 head 的值。
#p#
Stack
當(dāng)需要使用后進先出順序(LIFO)的數(shù)據(jù)結(jié)構(gòu)時,.NET 為我們提供了 Stack
Stack
Stack
如果 Stack
Hashtable
現(xiàn)在我們要使用員工的社保號作為唯一標(biāo)識進行存儲。社保號的格式為 DDD-DD-DDDD(D 的范圍為數(shù)字 0-9)。
如果使用 Array 存儲員工信息,要查詢社保號為 111-22-3333 的員工,則將會嘗試遍歷數(shù)組的所有選擇,即執(zhí)行復(fù)雜度為 O(n) 的查詢操作。好一些的辦法是將社保號排序,以使查詢復(fù)雜度降低到 O(log(n))。但理想情況下,我們更希望查詢復(fù)雜度為 O(1)。
一種方案是建立一個大數(shù)組,范圍從 000-00-0000 到 999-99-9999 。
這種方案的缺點是浪費空間。如果我們僅需要存儲 1000 個員工的信息,那么僅利用了 0.0001% 的空間。
第二種方案就是用哈希函數(shù)(Hash Function)壓縮序列。
我們選擇使用社保號的后四位作為索引,以減少區(qū)間的跨度。這樣范圍將從 0000 到 9999。
在數(shù)學(xué)上,將這種從 9 位數(shù)轉(zhuǎn)換為 4 位數(shù)的方式稱為哈希轉(zhuǎn)換(Hashing)。可以將一個數(shù)組的索引空間(indexers space)壓縮至相應(yīng)的哈希表(Hash Table)。
在上面的例子中,哈希函數(shù)的輸入為 9 位數(shù)的社保號,輸出結(jié)果為后 4 位。
H(x) = last four digits of x
上圖中也說明在哈希函數(shù)計算中常見的一種行為:哈希沖突(Hash Collisions)。即有可能兩個社保號的后 4 位均為 0000。
當(dāng)要添加新元素到 Hashtable 中時,哈希沖突是導(dǎo)致操作被破壞的一個因素。如果沒有沖突發(fā)生,則元素被成功插入。如果發(fā)生了沖突,則需要判斷沖突的原因。因此,哈希沖突提高了操作的代價,Hashtable 的設(shè)計目標(biāo)就是要盡可能減低沖突的發(fā)生。
避免哈希沖突的一個方法就是選擇合適的哈希函數(shù)。哈希函數(shù)中的沖突發(fā)生的幾率與數(shù)據(jù)的分布有關(guān)。例如,如果社保號的后 4 位是隨即分布的,則使用后 4 位數(shù)字比較合適。但如果后 4 位是以員工的出生年份來分配的,則顯然出生年份不是均勻分布的,則選擇后 4 位會造成大量的沖突。
我們將選擇合適的哈希函數(shù)的方法稱為沖突避免機制(Collision Avoidance)。
在處理沖突時,有很多策略可以實施,這些策略稱為沖突解決機制(Collision Resolution)。其中一種方法就是將要插入的元素放到另外一個塊空間中,因為相同的哈希位置已經(jīng)被占用。
例如,最簡單的一種實現(xiàn)就是線性挖掘(Linear Probing),步驟如下:
- 當(dāng)插入新的元素時,使用哈希函數(shù)在哈希表中定位元素位置;
- 檢查哈希表中該位置是否已經(jīng)存在元素。如果該位置內(nèi)容為空,則插入并返回,否則轉(zhuǎn)向步驟 3。
- 如果該位置為 i,則檢查 i+1 是否為空,如果已被占用,則檢查 i+2,依此類推,直到找到一個內(nèi)容為空的位置。
現(xiàn)在如果我們要將五個員工的信息插入到哈希表中:
- Alice (333-33-1234)
- Bob (444-44-1234)
- Cal (555-55-1237)
- Danny (000-00-1235)
- Edward (111-00-1235)
則插入后的哈希表可能如下:
元素的插入過程:
- Alice 的社保號被哈希為 1234,因此存放在位置 1234。
- Bob 的社保號被哈希為 1234,但由于位置 1234 處已經(jīng)存放 Alice 的信息,則檢查下一個位置 1235,1235 為空,則 Bob 的信息就被放到 1235。
- Cal 的社保號被哈希為 1237,1237 位置為空,所以 Cal 就放到 1237 處。
- Danny 的社保號被哈希為 1235,1235 已被占用,則檢查 1236 位置是否為空,1236 為空,所以 Danny 就被放到 1236。
- Edward 的社保號被哈希為 1235,1235 已被占用,檢查1236,也被占用,再檢查1237,直到檢查到 1238時,該位置為空,于是 Edward 被放到了1238 位置。
線性挖掘(Linear Probing)方式雖然簡單,但并不是解決沖突的最好的策略,因為它會導(dǎo)致同類哈希的聚集。這導(dǎo)致搜索哈希表時,沖突依然存在。例如上面例子中的哈希表,如果我們要訪問 Edward 的信息,因為 Edward 的社保號 111-00-1235 哈希為 1235,然而我們在 1235 位置找到的是 Bob,所以再搜索 1236,找到的卻是 Danny,以此類推直到找到 Edward。
#p#
一種改進的方式為二次挖掘(Quadratic Probing),即每次檢查位置空間的步長為平方倍數(shù)。也就是說,如果位置 s 被占用,則首先檢查 s + 12 處,然后檢查s - 12,s + 22,s - 22,s + 32 依此類推,而不是象線性挖掘那樣以 s + 1,s + 2 ... 方式增長。盡管如此,二次挖掘同樣也會導(dǎo)致同類哈希聚集問題。
.NET 中的 Hashtable 的實現(xiàn),要求添加元素時不僅要提供元素(Item),還要為該元素提供一個鍵(Key)。例如,Key 為員工社保號,Item 為員工信息對象??梢酝ㄟ^ Key 作為索引來查找 Item。
1 Hashtable employees = new Hashtable();
2
3 // Add some values to the Hashtable, indexed by a string key
4 employees.Add("111-22-3333", "Scott");
5 employees.Add("222-33-4444", "Sam");
6 employees.Add("333-44-55555", "Jisun");
7
8 // Access a particular key
9 if (employees.ContainsKey("111-22-3333"))
10 {
11 string empName = (string)employees["111-22-3333"];
12 Console.WriteLine("Employee 111-22-3333's name is: " + empName);
13 }
14 else
15 Console.WriteLine("Employee 111-22-3333 is not in the hash table...");
Hashtable 類中的哈希函數(shù)比前面介紹的社保號的實現(xiàn)要更為復(fù)雜。哈希函數(shù)必須返回一個序數(shù)(Ordinal Value)。對于社保號的例子,通過截取后四位就可以實現(xiàn)。但實際上 Hashtable 類可以接受任意類型的值作為 Key,這都要歸功于 GetHashCode 方法,一個定義在 System.Object 中的方法。GetHashCode 的默認(rèn)實現(xiàn)將返回一個唯一的整數(shù),并且保證在對象的生命周期內(nèi)保持不變。
Hashtable 類中的哈希函數(shù)定義如下:
H(key) = [GetHash(key) + 1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1))] % hashsize
這里的 GetHash(key) 默認(rèn)是調(diào)用 key 的 GetHashCode 方法以獲取返回的哈希值。hashsize 指的是哈希表的長度。因為要進行求模,所以最后的結(jié)果 H(key) 的范圍在 0 至 hashsize - 1 之間。
當(dāng)在哈希表中添加或獲取一個元素時,會發(fā)生哈希沖突。前面我們簡單地介紹了兩種沖突解決策略:
- 線性挖掘(Linear Probing)
- 二次挖掘(Quadratic Probing)
在 Hashtable 類中則使用的是一種完全不同的技術(shù),稱為二度哈希(rehashing)(有些資料中也將其稱為雙精度哈希(double hashing))。
二度哈希的工作原理如下:
有一個包含一組哈希函數(shù) H1...Hn 的集合。當(dāng)需要從哈希表中添加或獲取元素時,首先使用哈希函數(shù) H1。如果導(dǎo)致沖突,則嘗試使用 H2,以此類推,直到 Hn。所有的哈希函數(shù)都與 H1 十分相似,不同的是它們選用的乘法因子(multiplicative factor)。
通常,哈希函數(shù) Hk 的定義如下:
Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize
當(dāng)使用二度哈希時,重要的是在執(zhí)行了 hashsize 次挖掘后,哈希表中的每一個位置都有且只有一次被訪問到。也就是說,對于給定的 key,對哈希表中的同一位置不會同時使用 Hi 和 Hj。在 Hashtable 類中使用二度哈希公式,其始終保持 (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)) 與 hashsize 互為素數(shù)(兩數(shù)互為素數(shù)表示兩者沒有共同的質(zhì)因子)。
二度哈希較前面介紹的線性挖掘(Linear Probing)和二次挖掘(Quadratic Probing)提供了更好的避免沖突的策略。
Hashtable 類中包含一個私有成員變量 loadFactor,loadFactor 指定了哈希表中元素數(shù)量與位置(slot)數(shù)量之間的最大比例。例如:如果 loadFactor 等于 0.5,則說明哈希表中只有一半的空間存放了元素值,其余一半都為空。
哈希表的構(gòu)造函數(shù)允許用戶指定 loadFactor 值,定義范圍為 0.1 到 1.0。然而,不管你提供的值是多少,范圍都不會超過 72%。即使你傳遞的值為 1.0,Hashtable 類的 loadFactor 值還是 0.72。微軟認(rèn)為loadFactor 的最佳值為 0.72,這平衡了速度與空間。因此雖然默認(rèn)的 loadFactor 為 1.0,但系統(tǒng)內(nèi)部卻自動地將其改變?yōu)?0.72。所以,建議你使用缺省值1.0(但實際上是 0.72)。
向 Hashtable 中添加新元素時,需要檢查以保證元素與空間大小的比例不會超過最大比例。如果超過了,哈希表空間將被擴充。步驟如下:
- 哈希表的位置空間幾乎被翻倍。準(zhǔn)確地說,位置空間值從當(dāng)前的素數(shù)值增加到下一個最大的素數(shù)值。
- 因為二度哈希時,哈希表中的所有元素值將依賴于哈希表的位置空間值,所以表中所有值也需要重新二度哈希。
由此看出,對哈希表的擴充將是以性能損耗為代價。因此,我們應(yīng)該預(yù)先估計哈希表中最有可能容納的元素數(shù)量,在初始化哈希表時給予合適的值進行構(gòu)造,以避免不必要的擴充。
Dictionary
Hashtable 類是一個類型松耦合的數(shù)據(jù)結(jié)構(gòu),開發(fā)人員可以指定任意的類型作為 Key 或 Item。當(dāng) .NET 引入泛型支持后,類型安全的 Dictionary
DictionaryvariableName = new Dictionary ();
如果繼續(xù)使用上面描述的社保號和員工的示例,我們可以創(chuàng)建一個 Dictionary
DictionaryemployeeData = new Dictionary ();
這樣我們就可以添加和刪除員工信息了。
1 // Add some employees
2 employeeData.Add(455110189) = new Employee("Scott Mitchell");
3 employeeData.Add(455110191) = new Employee("Jisun Lee");
4
5 // See if employee with SSN 123-45-6789 works here
6 if (employeeData.ContainsKey(123456789))Dictionary
前面使用的挖掘技術(shù)(probing),如果發(fā)生沖突,則將嘗試列表中的下一個位置。如果使用二度哈希(rehashing),則將導(dǎo)致所有的哈希被重新計算。而新的鏈技術(shù)(chaining)將采用額外的數(shù)據(jù)結(jié)構(gòu)來處理沖突。Dictionary
下面的示意圖中描述了 Dictionary
上圖中,該 Dictionary 包含了 8 個桶,也就是自頂向下的黃色背景的位置。一定數(shù)量的 Employee 對象已經(jīng)被添加至 Dictionary 中。如果一個新的 Employee 要被添加至 Dictionary 中,將會被添加至其 Key 的哈希所對應(yīng)的桶中。如果在相同位置已經(jīng)有一個 Employee 存在了,則將會將新元素添加到列表的前面。
向 Dictionary 中添加元素的操作涉及到哈希計算和鏈表操作,但其仍為常量,復(fù)雜度為 O(1)。
對 Dictionary 進行查詢和刪除操作時,其平均時間取決于 Dictionary 中元素的數(shù)量和桶(bucket)的數(shù)量。具體的說就是運行時間為 O(n/m),這里 n 為元素的總數(shù)量,m 是桶的數(shù)量。但 Dictionary 幾乎總是被實現(xiàn)為 n = m,也就是說,元素的總數(shù)絕不會超過桶的總數(shù)。所以 O(n/m) 也變成了常量 O(1)。
參考資料
- An Extensive Examination of Data Structures Using C# 2.0 : Part 1: An Introduction to Data Structures
- An Extensive Examination of Data Structures Using C# 2.0 : Part 2: The Queue, Stack, and Hashtable
- 考察數(shù)據(jù)結(jié)構(gòu)——第一部分:數(shù)據(jù)結(jié)構(gòu)簡介[譯]
- 考察數(shù)據(jù)結(jié)構(gòu)——第二部分:隊列、堆棧和哈希表[譯]
本文出自:http://www.cnblogs.com/gaochundong/p/data_structures_and_asymptotic_analysis.html
網(wǎng)站欄目:常用數(shù)據(jù)結(jié)構(gòu)及復(fù)雜度
本文來源:http://fisionsoft.com.cn/article/cospgec.html


咨詢
建站咨詢

