1.幾種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)

這里主要總結(jié)下在工作中常碰到的幾種數(shù)據(jù)結(jié)構(gòu)：Array，ArrayList，List，LinkedList，Queue，Stack，Dictionary。,t>

數(shù)組Array：

數(shù)組是最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)。其具有如下特點(diǎn)：

數(shù)組存儲(chǔ)在連續(xù)的內(nèi)存上。

數(shù)組的內(nèi)容都是相同類型。

數(shù)組可以直接通過(guò)下標(biāo)訪問(wèn)。

數(shù)組Array的創(chuàng)建：

1 int size = 5; 2 int[] test = new int[size];

創(chuàng)建一個(gè)新的數(shù)組時(shí)將在 CLR 托管堆中分配一塊連續(xù)的內(nèi)存空間，來(lái)盛放數(shù)量為size，類型為所聲明類型的數(shù)組元素。如果類型為值類型，則將會(huì)有size個(gè)未裝箱的該類型的值被創(chuàng)建。如果類型為引用類型，則將會(huì)有size個(gè)相應(yīng)類型的引用被創(chuàng)建。

由于是在連續(xù)內(nèi)存上存儲(chǔ)的，所以它的索引速度非?？欤L問(wèn)一個(gè)元素的時(shí)間是恒定的也就是說(shuō)與數(shù)組的元素?cái)?shù)量無(wú)關(guān)，而且賦值與修改元素也很簡(jiǎn)單。

string[] test2 = new string[3];
//賦值
test2[0] = "chen";
test2[1] = "j";
test2[2] = "d";
//修改
test2[0] = "chenjd";

但是有優(yōu)點(diǎn)，那么就一定會(huì)伴隨著缺點(diǎn)。由于是連續(xù)存儲(chǔ)，所以在兩個(gè)元素之間插入新的元素就變得不方便。而且就像上面的代碼所顯示的那樣，聲明一個(gè)新的數(shù)組時(shí)，必須指定其長(zhǎng)度，這就會(huì)存在一個(gè)潛在的問(wèn)題，那就是當(dāng)我們聲明的長(zhǎng)度過(guò)長(zhǎng)時(shí)，顯然會(huì)浪費(fèi)內(nèi)存，當(dāng)我們聲明長(zhǎng)度過(guò)短的時(shí)候，則面臨這溢出的風(fēng)險(xiǎn)。這就使得寫代碼像是投機(jī)，很厭惡這樣的行為！針對(duì)這種缺點(diǎn)，下面隆重推出ArrayList。

ArrayList：

為了解決數(shù)組創(chuàng)建時(shí)必須指定長(zhǎng)度以及只能存放相同類型的缺點(diǎn)而推出的數(shù)據(jù)結(jié)構(gòu)。ArrayList是System.Collections命名空間下的一部分，所以若要使用則必須引入System.Collections。正如上文所說(shuō)，ArrayList解決了數(shù)組的一些缺點(diǎn)。

不必在聲明ArrayList時(shí)指定它的長(zhǎng)度，這是由于ArrayList對(duì)象的長(zhǎng)度是按照其中存儲(chǔ)的數(shù)據(jù)來(lái)動(dòng)態(tài)增長(zhǎng)與縮減的。

ArrayList可以存儲(chǔ)不同類型的元素。這是由于ArrayList會(huì)把它的元素都當(dāng)做Object來(lái)處理。因而，加入不同類型的元素是允許的。

ArrayList的操作：

ArrayList test3 = new ArrayList();
//新增數(shù)據(jù)
test3.Add("chen");
test3.Add("j");
test3.Add("d");
test3.Add("is");
test3.Add(25);
//修改數(shù)據(jù)
test3[4] = 26;
//刪除數(shù)據(jù)
test3.RemoveAt(4);

說(shuō)了那么一堆”優(yōu)點(diǎn)“，也該說(shuō)說(shuō)缺點(diǎn)了吧。為什么要給”優(yōu)點(diǎn)”打上引號(hào)呢？那是因?yàn)锳rrayList可以存儲(chǔ)不同類型數(shù)據(jù)的原因是由于把所有的類型都當(dāng)做Object來(lái)做處理，也就是說(shuō)ArrayList的元素其實(shí)都是Object類型的，辣么問(wèn)題就來(lái)了。

ArrayList不是類型安全的。因?yàn)榘巡煌念愋投籍?dāng)做Object來(lái)做處理，很有可能會(huì)在使用ArrayList時(shí)發(fā)生類型不匹配的情況。

如上文所訴，數(shù)組存儲(chǔ)值類型時(shí)并未發(fā)生裝箱，但是ArrayList由于把所有類型都當(dāng)做了Object，所以不可避免的當(dāng)插入值類型時(shí)會(huì)發(fā)生裝箱操作，在索引取值時(shí)會(huì)發(fā)生拆箱操作。這能忍嗎？

注：為何說(shuō)頻繁的沒(méi)有必要的裝箱和拆箱不能忍呢？所謂裝箱 (boxing)：就是值類型實(shí)例到對(duì)象的轉(zhuǎn)換(百度百科)。那么拆箱：就是將引用類型轉(zhuǎn)換為值類型咯（還是來(lái)自百度百科）。下面舉個(gè)栗子~

//裝箱，將String類型的值FanyoyChenjd賦值給對(duì)象。
int  info = 1989;  
object obj=(object)info;  

//拆箱，從Obj中提取值給info
object obj = 1;
int info = (int)obj;

那么結(jié)論呢？顯然，從原理上可以看出，裝箱時(shí)，生成的是全新的引用對(duì)象，這會(huì)有時(shí)間損耗，也就是造成效率降低。

List泛型List

為了解決ArrayList不安全類型與裝箱拆箱的缺點(diǎn)，所以出現(xiàn)了泛型的概念，作為一種新的數(shù)組類型引入。也是工作中經(jīng)常用到的數(shù)組類型。和ArrayList很相似，長(zhǎng)度都可以靈活的改變，最大的不同在于在聲明List集合時(shí)，我們同時(shí)需要為其聲明List集合內(nèi)數(shù)據(jù)的對(duì)象類型，這點(diǎn)又和Array很相似，其實(shí)List內(nèi)部使用了Array來(lái)實(shí)現(xiàn)。

List test4 = new List();  
  
//新增數(shù)據(jù)  
test4.Add(“Fanyoy”);  
test4.Add(“Chenjd”);  

//修改數(shù)據(jù)  
test4[1] = “murongxiaopifu”;  
  
//移除數(shù)據(jù)  
test4.RemoveAt(0);  

這么做最大的好處就是

即確保了類型安全。

也取消了裝箱和拆箱的操作。

它融合了Array可以快速訪問(wèn)的優(yōu)點(diǎn)以及ArrayList長(zhǎng)度可以靈活變化的優(yōu)點(diǎn)。

LinkedList

也就是鏈表了。和上述的數(shù)組最大的不同之處就是在于鏈表在內(nèi)存存儲(chǔ)的排序上可能是不連續(xù)的。這是由于鏈表是通過(guò)上一個(gè)元素指向下一個(gè)元素來(lái)排列的，所以可能不能通過(guò)下標(biāo)來(lái)訪問(wèn)。如圖

?

既然鏈表最大的特點(diǎn)就是存儲(chǔ)在內(nèi)存的空間不一定連續(xù)，那么鏈表相對(duì)于數(shù)組最大優(yōu)勢(shì)和劣勢(shì)就顯而易見(jiàn)了。

向鏈表中插入或刪除節(jié)點(diǎn)無(wú)需調(diào)整結(jié)構(gòu)的容量。因?yàn)楸旧聿皇沁B續(xù)存儲(chǔ)而是靠各對(duì)象的指針?biāo)鶝Q定，所以添加元素和刪除元素都要比數(shù)組要有優(yōu)勢(shì)。

鏈表適合在需要有序的排序的情境下增加新的元素，這里還拿數(shù)組做對(duì)比，例如要在數(shù)組中間某個(gè)位置增加新的元素，則可能需要移動(dòng)移動(dòng)很多元素，而對(duì)于鏈表而言可能只是若干元素的指向發(fā)生變化而已。

有優(yōu)點(diǎn)就有缺點(diǎn)，由于其在內(nèi)存空間中不一定是連續(xù)排列，所以訪問(wèn)時(shí)候無(wú)法利用下標(biāo)，而是必須從頭結(jié)點(diǎn)開(kāi)始，逐次遍歷下一個(gè)節(jié)點(diǎn)直到尋找到目標(biāo)。所以當(dāng)需要快速訪問(wèn)對(duì)象時(shí)，數(shù)組無(wú)疑更有優(yōu)勢(shì)。

綜上，鏈表適合元素?cái)?shù)量不固定，需要經(jīng)常增減節(jié)點(diǎn)的情況。

示例：

下面的代碼示例演示了類的許多功能LinkedList。

using System;
using System.Text;
using System.Collections.Generic;

public class Example
{
    public static void Main()
    {
        // Create the link list.
        string[] words =
            { "the", "fox", "jumps", "over", "the", "dog" };
        LinkedList sentence = new LinkedList(words);
        Display(sentence, "The linked list values:");
        Console.WriteLine("sentence.Contains("jumps") = {0}",
            sentence.Contains("jumps"));

        // Add the word 'today' to the beginning of the linked list.
        sentence.AddFirst("today");
        Display(sentence, "Test 1: Add 'today' to beginning of the list:");

        // Move the first node to be the last node.
        LinkedListNode mark1 = sentence.First;
        sentence.RemoveFirst();
        sentence.AddLast(mark1);
        Display(sentence, "Test 2: Move first node to be last node:");

        // Change the last node to 'yesterday'.
        sentence.RemoveLast();
        sentence.AddLast("yesterday");
        Display(sentence, "Test 3: Change the last node to 'yesterday':");

        // Move the last node to be the first node.
        mark1 = sentence.Last;
        sentence.RemoveLast();
        sentence.AddFirst(mark1);
        Display(sentence, "Test 4: Move last node to be first node:");

        // Indicate the last occurence of 'the'.
        sentence.RemoveFirst();
        LinkedListNode current = sentence.FindLast("the");
        IndicateNode(current, "Test 5: Indicate last occurence of 'the':");

        // Add 'lazy' and 'old' after 'the' (the LinkedListNode named current).
        sentence.AddAfter(current, "old");
        sentence.AddAfter(current, "lazy");
        IndicateNode(current, "Test 6: Add 'lazy' and 'old' after 'the':");

        // Indicate 'fox' node.
        current = sentence.Find("fox");
        IndicateNode(current, "Test 7: Indicate the 'fox' node:");

        // Add 'quick' and 'brown' before 'fox':
        sentence.AddBefore(current, "quick");
        sentence.AddBefore(current, "brown");
        IndicateNode(current, "Test 8: Add 'quick' and 'brown' before 'fox':");

        // Keep a reference to the current node, 'fox',
        // and to the previous node in the list. Indicate the 'dog' node.
        mark1 = current;
        LinkedListNode mark2 = current.Previous;
        current = sentence.Find("dog");
        IndicateNode(current, "Test 9: Indicate the 'dog' node:");

        // The AddBefore method throws an InvalidOperationException
        // if you try to add a node that already belongs to a list.
        Console.WriteLine("Test 10: Throw exception by adding node (fox) already in the list:");
        try
        {
            sentence.AddBefore(current, mark1);
        }
        catch (InvalidOperationException ex)
        {
            Console.WriteLine("Exception message: {0}", ex.Message);
        }
        Console.WriteLine();

        // Remove the node referred to by mark1, and then add it
        // before the node referred to by current.
        // Indicate the node referred to by current.
        sentence.Remove(mark1);
        sentence.AddBefore(current, mark1);
        IndicateNode(current, "Test 11: Move a referenced node (fox) before the current node (dog):");

        // Remove the node referred to by current.
        sentence.Remove(current);
        IndicateNode(current, "Test 12: Remove current node (dog) and attempt to indicate it:");

        // Add the node after the node referred to by mark2.
        sentence.AddAfter(mark2, current);
        IndicateNode(current, "Test 13: Add node removed in test 11 after a referenced node (brown):");

        // The Remove method finds and removes the
        // first node that that has the specified value.
        sentence.Remove("old");
        Display(sentence, "Test 14: Remove node that has the value 'old':");

        // When the linked list is cast to ICollection(Of String),
        // the Add method adds a node to the end of the list.
        sentence.RemoveLast();
        ICollection icoll = sentence;
        icoll.Add("rhinoceros");
        Display(sentence, "Test 15: Remove last node, cast to ICollection, and add 'rhinoceros':");

        Console.WriteLine("Test 16: Copy the list to an array:");
        // Create an array with the same number of
        // elements as the linked list.
        string[] sArray = new string[sentence.Count];
        sentence.CopyTo(sArray, 0);

        foreach (string s in sArray)
        {
            Console.WriteLine(s);
        }

        // Release all the nodes.
        sentence.Clear();

        Console.WriteLine();
        Console.WriteLine("Test 17: Clear linked list. Contains 'jumps' = {0}",
            sentence.Contains("jumps"));

        Console.ReadLine();
    }

    private static void Display(LinkedList words, string test)
    {
        Console.WriteLine(test);
        foreach (string word in words)
        {
            Console.Write(word + " ");
        }
        Console.WriteLine();
        Console.WriteLine();
    }

    private static void IndicateNode(LinkedListNode node, string test)
    {
        Console.WriteLine(test);
        if (node.List == null)
        {
            Console.WriteLine("Node '{0}' is not in the list.\n",
                node.Value);
            return;
        }

        StringBuilder result = new StringBuilder("(" + node.Value + ")");
        LinkedListNode nodeP = node.Previous;

        while (nodeP != null)
        {
            result.Insert(0, nodeP.Value + " ");
            nodeP = nodeP.Previous;
        }

        node = node.Next;
        while (node != null)
        {
            result.Append(" " + node.Value);
            node = node.Next;
        }

        Console.WriteLine(result);
        Console.WriteLine();
    }
}

//This code example produces the following output:
//
//The linked list values:
//the fox jumps over the dog

//Test 1: Add 'today' to beginning of the list:
//today the fox jumps over the dog

//Test 2: Move first node to be last node:
//the fox jumps over the dog today

//Test 3: Change the last node to 'yesterday':
//the fox jumps over the dog yesterday

//Test 4: Move last node to be first node:
//yesterday the fox jumps over the dog

//Test 5: Indicate last occurence of 'the':
//the fox jumps over (the) dog

//Test 6: Add 'lazy' and 'old' after 'the':
//the fox jumps over (the) lazy old dog

//Test 7: Indicate the 'fox' node:
//the (fox) jumps over the lazy old dog

//Test 8: Add 'quick' and 'brown' before 'fox':
//the quick brown (fox) jumps over the lazy old dog

//Test 9: Indicate the 'dog' node:
//the quick brown fox jumps over the lazy old (dog)

//Test 10: Throw exception by adding node (fox) already in the list:
//Exception message: The LinkedList node belongs a LinkedList.

//Test 11: Move a referenced node (fox) before the current node (dog):
//the quick brown jumps over the lazy old fox (dog)

//Test 12: Remove current node (dog) and attempt to indicate it:
//Node 'dog' is not in the list.

//Test 13: Add node removed in test 11 after a referenced node (brown):
//the quick brown (dog) jumps over the lazy old fox

//Test 14: Remove node that has the value 'old':
//the quick brown dog jumps over the lazy fox

//Test 15: Remove last node, cast to ICollection, and add 'rhinoceros':
//the quick brown dog jumps over the lazy rhinoceros

//Test 16: Copy the list to an array:
//the
//quick
//brown
//dog
//jumps
//over
//the
//lazy
//rhinoceros

//Test 17: Clear linked list. Contains 'jumps' = False
//

Queue

在Queue這種數(shù)據(jù)結(jié)構(gòu)中，最先插入在元素將是最先被刪除；反之最后插入的元素將最后被刪除，因此隊(duì)列又稱為“先進(jìn)先出”（FIFO—first in first out）的線性表。通過(guò)使用Enqueue和Dequeue這兩個(gè)方法來(lái)實(shí)現(xiàn)對(duì) Queue 的存取。

一些需要注意的地方：

先進(jìn)先出的情景。

默認(rèn)情況下，Queue的初始容量為32， 增長(zhǎng)因子為2.0。

當(dāng)使用Enqueue時(shí)，會(huì)判斷隊(duì)列的長(zhǎng)度是否足夠，若不足，則依據(jù)增長(zhǎng)因子來(lái)增加容量，例如當(dāng)為初始的2.0時(shí)，則隊(duì)列容量增長(zhǎng)2倍。

乏善可陳。

示例：

下面的代碼示例演示了泛型類的幾個(gè)方法 Queue 。 此代碼示例創(chuàng)建具有默認(rèn)容量的字符串隊(duì)列，并使用 Enqueue 方法將五個(gè)字符串進(jìn)行排隊(duì)。 枚舉隊(duì)列的元素，而不會(huì)更改隊(duì)列的狀態(tài)。 Dequeue方法用于取消對(duì)第一個(gè)字符串的排隊(duì)。 Peek方法用于查看隊(duì)列中的下一項(xiàng)，然后 Dequeue 使用方法將其取消排隊(duì)。

ToArray方法用于創(chuàng)建數(shù)組，并將隊(duì)列元素復(fù)制到該數(shù)組，然后將數(shù)組傳遞給 Queue 采用的構(gòu)造函數(shù) IEnumerable ，創(chuàng)建隊(duì)列的副本。 將顯示副本的元素。

創(chuàng)建隊(duì)列大小兩倍的數(shù)組，并 CopyTo 使用方法從數(shù)組中間開(kāi)始復(fù)制數(shù)組元素。 在 Queue 開(kāi)始時(shí)，將再次使用構(gòu)造函數(shù)來(lái)創(chuàng)建包含三個(gè) null 元素的隊(duì)列的第二個(gè)副本。

Contains方法用于顯示字符串 "四" 位于隊(duì)列的第一個(gè)副本中，在此之后， Clear 方法會(huì)清除副本， Count 屬性顯示該隊(duì)列為空。

using System;
using System.Collections.Generic;

class Example
{
    public static void Main()
    {
        Queue numbers = new Queue();
        numbers.Enqueue("one");
        numbers.Enqueue("two");
        numbers.Enqueue("three");
        numbers.Enqueue("four");
        numbers.Enqueue("five");

        // A queue can be enumerated without disturbing its contents.
        foreach( string number in numbers )
        {
            Console.WriteLine(number);
        }

        Console.WriteLine("\nDequeuing '{0}'", numbers.Dequeue());
        Console.WriteLine("Peek at next item to dequeue: {0}",
            numbers.Peek());
        Console.WriteLine("Dequeuing '{0}'", numbers.Dequeue());

        // Create a copy of the queue, using the ToArray method and the
        // constructor that accepts an IEnumerable.
        Queue queueCopy = new Queue(numbers.ToArray());

        Console.WriteLine("\nContents of the first copy:");
        foreach( string number in queueCopy )
        {
            Console.WriteLine(number);
        }

        // Create an array twice the size of the queue and copy the
        // elements of the queue, starting at the middle of the
        // array.
        string[] array2 = new string[numbers.Count * 2];
        numbers.CopyTo(array2, numbers.Count);

        // Create a second queue, using the constructor that accepts an
        // IEnumerable(Of T).
        Queue queueCopy2 = new Queue(array2);

        Console.WriteLine("\nContents of the second copy, with duplicates and nulls:");
        foreach( string number in queueCopy2 )
        {
            Console.WriteLine(number);
        }

        Console.WriteLine("\nqueueCopy.Contains("four") = {0}",
            queueCopy.Contains("four"));

        Console.WriteLine("\nqueueCopy.Clear()");
        queueCopy.Clear();
        Console.WriteLine("\nqueueCopy.Count = {0}", queueCopy.Count);
    }
}

/* This code example produces the following output:

one
two
three
four
five

Dequeuing 'one'
Peek at next item to dequeue: two
Dequeuing 'two'

Contents of the copy:
three
four
five

Contents of the second copy, with duplicates and nulls:



three
four
five

queueCopy.Contains("four") = True

queueCopy.Clear()

queueCopy.Count = 0
 */

Stack

與Queue相對(duì)，當(dāng)需要使用后進(jìn)先出順序（LIFO）的數(shù)據(jù)結(jié)構(gòu)時(shí)，我們就需要用到Stack了。

一些需要注意的地方：

后進(jìn)先出的情景。

默認(rèn)容量為10。

使用pop和push來(lái)操作。

乏善可陳。

示例:

下面的代碼示例演示了泛型類的幾個(gè)方法 Stack 。 此代碼示例創(chuàng)建一個(gè)具有默認(rèn)容量的字符串堆棧，并使用 Push 方法將五個(gè)字符串推送到堆棧上。 枚舉堆棧的元素，這不會(huì)更改堆棧的狀態(tài)。 Pop方法用于彈出堆棧中的第一個(gè)字符串。 Peek方法用于查看堆棧上的下一項(xiàng)，然后 Pop 使用方法將它彈出。

ToArray方法用于創(chuàng)建數(shù)組，并將堆棧元素復(fù)制到該數(shù)組，然后將該數(shù)組傳遞給 Stack 采用的構(gòu)造函數(shù)，并 IEnumerable 使用反轉(zhuǎn)元素的順序創(chuàng)建堆棧副本。 將顯示副本的元素。

創(chuàng)建堆棧大小兩倍的數(shù)組，并 CopyTo 使用方法從數(shù)組中間開(kāi)始復(fù)制數(shù)組元素。 Stack再次使用構(gòu)造函數(shù)來(lái)創(chuàng)建具有反轉(zhuǎn)的元素順序的堆棧副本; 因此，這三個(gè) null 元素位于末尾。

Contains方法用于顯示字符串 "四" 位于堆棧的第一個(gè)副本中，在此之后， Clear 方法會(huì)清除副本， Count 屬性會(huì)顯示堆棧為空。

using System;
using System.Collections.Generic;

class Example
{
    public static void Main()
    {
        Stack numbers = new Stack();
        numbers.Push("one");
        numbers.Push("two");
        numbers.Push("three");
        numbers.Push("four");
        numbers.Push("five");

        // A stack can be enumerated without disturbing its contents.
        foreach( string number in numbers )
        {
            Console.WriteLine(number);
        }

        Console.WriteLine("\nPopping '{0}'", numbers.Pop());
        Console.WriteLine("Peek at next item to destack: {0}",
            numbers.Peek());
        Console.WriteLine("Popping '{0}'", numbers.Pop());

        // Create a copy of the stack, using the ToArray method and the
        // constructor that accepts an IEnumerable.
        Stack stack2 = new Stack(numbers.ToArray());

        Console.WriteLine("\nContents of the first copy:");
        foreach( string number in stack2 )
        {
            Console.WriteLine(number);
        }

        // Create an array twice the size of the stack and copy the
        // elements of the stack, starting at the middle of the
        // array.
        string[] array2 = new string[numbers.Count * 2];
        numbers.CopyTo(array2, numbers.Count);

        // Create a second stack, using the constructor that accepts an
        // IEnumerable(Of T).
        Stack stack3 = new Stack(array2);

        Console.WriteLine("\nContents of the second copy, with duplicates and nulls:");
        foreach( string number in stack3 )
        {
            Console.WriteLine(number);
        }

        Console.WriteLine("\nstack2.Contains("four") = {0}",
            stack2.Contains("four"));

        Console.WriteLine("\nstack2.Clear()");
        stack2.Clear();
        Console.WriteLine("\nstack2.Count = {0}", stack2.Count);
    }
}

/* This code example produces the following output:

five
four
three
two
one

Popping 'five'
Peek at next item to destack: four
Popping 'four'

Contents of the first copy:
one
two
three

Contents of the second copy, with duplicates and nulls:
one
two
three




stack2.Contains("four") = False

stack2.Clear()

stack2.Count = 0
 */

Dictionary,t>

提到字典就不得不說(shuō)Hashtable哈希表以及Hashing（哈希，也有叫散列的），因?yàn)樽值涞膶?shí)現(xiàn)方式就是哈希表的實(shí)現(xiàn)方式，只不過(guò)字典是類型安全的，也就是說(shuō)當(dāng)創(chuàng)建字典時(shí)，必須聲明key和item的類型，這是第一條字典與哈希表的區(qū)別。關(guān)于哈希，簡(jiǎn)單的說(shuō)就是一種將任意長(zhǎng)度的消息壓縮到某一固定長(zhǎng)度，比如某學(xué)校的學(xué)生學(xué)號(hào)范圍從00000~99999，總共5位數(shù)字，若每個(gè)數(shù)字都對(duì)應(yīng)一個(gè)索引的話，那么就是100000個(gè)索引，但是如果我們使用后3位作為索引，那么索引的范圍就變成了000~999了，當(dāng)然會(huì)沖突的情況，這種情況就是哈希沖突(Hash Collisions)了。

回到Dictionary，我們?cè)趯?duì)字典的操作中各種時(shí)間上的優(yōu)勢(shì)都享受到了，那么它的劣勢(shì)到底在哪呢？對(duì)嘞，就是空間。以空間換時(shí)間，通過(guò)更多的內(nèi)存開(kāi)銷來(lái)滿足我們對(duì)速度的追求。在創(chuàng)建字典時(shí)，我們可以傳入一個(gè)容量值，但實(shí)際使用的容量并非該值。而是使用“不小于該值的最小質(zhì)數(shù)來(lái)作為它使用的實(shí)際容量，最小是3。”（老趙），當(dāng)有了實(shí)際容量之后，并非直接實(shí)現(xiàn)索引，而是通過(guò)創(chuàng)建額外的2個(gè)數(shù)組來(lái)實(shí)現(xiàn)間接的索引，即int[] buckets和Entry[] entries兩個(gè)數(shù)組（即buckets中保存的其實(shí)是entries數(shù)組的下標(biāo)），這里就是第二條字典與哈希表的區(qū)別，還記得哈希沖突嗎？對(duì)，第二個(gè)區(qū)別就是處理哈希沖突的策略是不同的！字典會(huì)采用額外的數(shù)據(jù)結(jié)構(gòu)來(lái)處理哈希沖突，這就是剛才提到的數(shù)組之一buckets桶了，buckets的長(zhǎng)度就是字典的真實(shí)長(zhǎng)度，因?yàn)閎uckets就是字典每個(gè)位置的映射，然后buckets中的每個(gè)元素都是一個(gè)鏈表，用來(lái)存儲(chǔ)相同哈希的元素，然后再分配存儲(chǔ)空間。,t>

?

因此，我們面臨的情況就是，即便我們新建了一個(gè)空的字典，那么伴隨而來(lái)的是2個(gè)長(zhǎng)度為3的數(shù)組。所以當(dāng)處理的數(shù)據(jù)不多時(shí)，還是慎重使用字典為好，很多情況下使用數(shù)組也是可以接受的。

幾種常見(jiàn)數(shù)據(jù)結(jié)構(gòu)的使用情景

?