字典是一種利用鍵值對來存儲的數據結構。作為一種抽象類， dictionaryBase? 類可以實現不同的結構

sortedList? 是按照分類順序基于鍵值來存儲鍵值對的，它可以通過引用數據結構中的值得索引位置也可以訪問存貯在結構中的數據。

Dictionary? 中，存儲在字段中的鍵值對于時間上最為? DictionaryEntry? 對象來存儲的。 DictionaryEntry? 結構提供兩個域，一個用于鍵，一個用于值。對于內部而言會把鍵值存儲在 innerHashTable?? 的散列對象中。

?

public?class?IPAddresses?:?DictionaryBase

{

????public?IPAddresses()

????{

????}

????public?void?Add(string?name,?string?ip)

????{

????????base.InnerHashtable.Add(name,?ip);

????}

????public?string?Item(string?name)

????{

????????return?base.InnerHashtable[name].ToString();

????}

????public?void?Remove(string?name)

????{

????????base.InnerHashtable.Remove(name);

????}

}

??static?void?Main()

????{

????????IPAddresses?myIPs?=?new?IPAddresses();

????????myIPs.Add("Mike",?"192.155.12.1");

????????myIPs.Add("David",?"192.155.12.2");

????????myIPs.Add("Bernica",?"192.155.12.3");

????????Console.WriteLine("There?are?"?+?myIPs.Count?+?"?IP?addresses");

????????Console.WriteLine("David's?ip?address:?"?+?myIPs.Item("David"));

????????myIPs.Clear();

????????Console.WriteLine("There?are?"?+?myIPs.Count?+?"?IP?addresses");

????}

class?chapter

{

????static?void?Main()

????{

????????for?(int?i?=?0;?i?<?4;?i++)

????????????Console.WriteLine();

????????IPAddresses?myIPs?=?new?IPAddresses(@"c:\data\ips.txt");

????????Console.WriteLine("There?are?{0}?IP?addresses",?myIPs.Count);

????????Console.WriteLine("David's?IP?address:?"?+?myIPs.Item("David"));

????????Console.WriteLine("Bernica's?IP?address:?"?+?myIPs.Item("Bernica"));

????????Console.WriteLine("Mike's?IP?address:?"?+?myIPs.Item("Mike"));

????}

}

?

?

IPAddresses?myIPs?=?new?IPAddresses(@"c:\ips.txt");

DictionaryEntry[]?ips?=?new?DictionaryEntry[myIPs.Count-1];

myIPs.CopyTo(ips,?0);

?

?

泛型KeyValuePair?類，每個對象只能存儲一個值

<string,?int>?mcmillan?=?new?KeyValuePair<string,?int>("McMillan",?99);

Console.Write(mcmillan.Key);

Console.Write("?"?+?mcmillan.Value);

?

?

using?System;

using?System.Collections.Generic;

using?System.Text;

namespace?Generics

{

????class?Program

????{

????????static?void?Main(string[]?args)

????????{

?

????????????KeyValuePair<string,?int>[]?gradeBook?=?new?KeyValuePair<string,?int>[10];

????????????gradeBook[0]?=?new?KeyValuePair<string,int>("McMillan",?99);

????????????gradeBook[1]?=?new?KeyValuePair<string,int>("Ruff",?64);

????????????for?(int?i?=?0;?i?<=?gradeBook.GetUpperBound(0);?i++)

????????????????if?(gradeBook[i].Value?!=?0)

????????????????????Console.WriteLine(gradeBook[i].Key?+?":?"?+?gradeBook[i].Value);

????????????Console.Read();

????????}

????}

}

?

SortedList? 類

?

SortedList?myips?=?new?SortedList();

myips.Add("Mike",?"192.155.12.1");

myips.Add("David",?"192.155.12.2");

myips.Add("Bernica",?"192.155.12.3");

?

?

SortedList<Tkey,?TValue>

?

?

SortedList<string,?string>?myips?=?new?SortedList<string,?string>();

?

SortedList<string,?int>?gradeBook?=?new?SortedList<string,?int>();

?

?

foreach(Object?key?in?myips.Keys)

Console.WriteLine("Name:?"?+?key?+?"\n"?+?"IP:?"?+?myips[key]);

?

for(int?i?=?0;?i?<?myips.Count;?i++)

Console.WriteLine("Name:?"?+?myips.GetKey(i)?+?"\n"?+?"IP:?"?+?myips.GetByIndex(i));

?

myips.Remove("David");

myips.RemoveAt(1);

int?indexDavid?=?myips.IndexOfKey("David");

int?indexIPDavid?=?myips.IndexOfValue(myips["David"]);

?

散列和 HasTable

散列是一種常見的順出數據技術，采用這種技術可以非常迅速的插入和檢索數據。散列所采用的數據結構成為散列表。

?

?

?散列表數據結構是圍繞數組設計的。存儲在數組內的每一個數據讀書基于鍵映射到一個范圍從 0 到散列表大小的數值上，這被稱為是鍵，為了把一個元素存儲到散列表內，利用所謂散列函數吧鍵映射到一個范圍從 0 到散列表大小的數上。由于鍵是不受限制的，而數組的大小又是有限制的，所以散列函數比較現實的目標是把鍵盡可能平均分布到數組的單元內。即使一個很好的散列函數也可能會出現兩個鍵散列到相同的數值情況 , 這種現象稱為沖突。

?

選擇散列函數?

?選擇散列函數的依據是所用鍵的數據類型。如果所用的鍵是整數，那么最簡單的函數是返回鍵對數組大小取莫結果（前提是數組的大小必須是素數）。然而許多應用中鍵都是字符串，下面一個簡單利用把鍵內字母 Ascll 碼相加，上述加和的數值與數組大小模莫就是散列值了。

?

?

using?System;

class?chapter

{

????static?void?Main()

????{

????????string[]?names?=?new?string[99];

????????string?name;

????????string[]?someNames?=?new?string[]{"David","Jennifer",?"Donnie",?"Mayo",?"Raymond",

????????????"Bernica",?"Mike",?"Clayton",?"Beata",?"Michael"};

????????int?hashVal;

????????for?(int?i?=?0;?i?<?10;?i++)

????????{

????????????name?=?someNames[i];

????????????hashVal?=?SimpleHash(name,?names);

????????????names[hashVal]?=?name;

????????}

????????ShowDistrib(names);

????}

????static?int?SimpleHash(string?s,?string[]?arr)

????{

????????int?tot?=?0;

????????char[]?cname;

????????cname?=?s.ToCharArray();

????????for?(int?i?=?0;?i?<=?cname.GetUpperBound(0);?i++)

????????????tot?+=?(int)cname[i];

????????return?tot?%?arr.GetUpperBound(0);

????}

????static?void?ShowDistrib(string[]?arr)

????{

????????for?(int?i?=?0;?i?<=?arr.GetUpperBound(0);?i++)

????????????if?(arr[i]?!=?null)

????????????????Console.WriteLine(i?+?"?"?+?arr[i]);

????}

}

問題出現了，鍵分布不均勻都聚集在數組的開始和結束處。

最終選擇數組的小取決于存儲在記錄的確切數量。一個保險數字是 10007 ，它是素數，而且還沒大到，會使用大量內存導致降低程序性能的地步。

一個好的解決方法

static?int?BetterHash(string?s,?string[]?arr)

{

????long?tot?=?0;

????char[]?cname;

????cname?=?s.ToCharArray();

????for?(int?i?=?0;?i?<=?cname.GetUpperBound(0);?i++)

????????tot?+=?37?*?tot?+?(int)cname[i];

????tot?=?tot?%?arr.GetUpperBound(0);

????if?(tot?<?0)

????????tot?+=?arr.GetUpperBound(0);

????return?(int)tot;

}

這個函數利用霍納法則 (Horner) 來計算多項式函數。

?

查找散列表中數據

static?bool?InHash(string?s,?string[]?arr)

{

????int?hval?=?BetterHash(s,?arr);

????if?(arr[hval]?==?s)

????????return?true;

????else

????????return?false;

}

?

解決沖突?

?在處理散列表的時候，不可避免的會遇到這種情況，即計算出的鍵的散列值已經存儲到了贏一個鍵，這個就是所謂的沖突。

筒式散列法

public?class?BucketHash

{

????private?const?int?SIZE?=?101;

????ArrayList[]?data;

????public?BucketHash()

????{

????????data?=?new?ArrayList[SIZE];

????????for?(int?i?=?0;?i?<=?SIZE?-?1;?i++)

????????????data[i]?=?new?ArrayList(4);

????}

????public?int?Hash(string?s)

????{

????????long?tot?=?0;

????????char[]?charray;

????????charray?=?s.ToCharArray();

????????for?(int?i?=?0;?i?<=?s.Length?-?1;?i++)

????????????tot?+=?37?*?tot?+?(int)charray[i];

????????tot?=?tot?%?data.GetUpperBound(0);

????????if?(tot?<?0)

????????????tot?+=?data.GetUpperBound(0);

????????return?(int)tot;

????}

????public?void?Insert(string?item)

????{

????????int?hash_value;

????????hash_value?=?Hash(item);

????????if?(data[hash_value].Contains(item))

????????????data[hash_value].Add(item);

????}

????public?void?Remove(string?item)

????{

????????int?hash_value;

????????hash_value?=?Hash(item);

????????if?(data[hash_value].Contains(item))

????????????data[hash_value].Remove(item);

????}

}

?

?

堆排序?

如果將堆看成是一棵完全二叉樹，則這棵完全二叉樹每個非葉子節點的值均不大于（或不小于）其左，右孩子節點的值。非葉子節點大于左右節點值得堆稱為大根堆，小于左右節點的值得堆稱為小根堆。

堆的結構類似于二叉樹，但是又不完全相同。首先構造堆通常采用的是數組而不是節點引用。

堆有兩個非常重要的條件?（ 1 ）堆必須是完整的，這就是意味著每一行都必須有數據填充。（ 2 ）每個節點包含的數據大于或者等于此節點下方孩子節點所包含的數據。

?

using?System;

public?class?Node

{

????public?int?data;

????public?Node(int?key)

????{

????????data?=?key;

????}

}

?

?

public?bool?Insert(int?key)

{

????if?(currSize?==?maxSize)

????????return?false;

????heapArray[currSize]?=?new?Node(key);

????currSize++;

????return?true;

}

?

public?void?ShiftUp(int?index)?//? 移動合適位置。

{

????int?parent?=?(index?-?1)?/?2;

????Node?bottom?=?heapArray[index];

????while?((index?>?0)?&&?(heapArray[parent].data?<?bottom.data))

????{

????????heapArray[index]?=?heapArray[parent];

????????index?=?parent;

????????parent?=?(parent?-?1)?/?2;

????}

????heapArray[index]?=?bottom;

}

?

public?Node?Remove()

{

????Node?root?=?heapArray[0];

????currSize--;

????heapArray[0]?=?heapArray[currSize];

????ShiftDown(0);

????return?root;

}

public?void?ShiftDown(int?index)

{

????int?largerChild;

????Node?top?=?heapArray[index];

????while?(index?<?(int)(currSize?/?2))

????{

????????int?leftChild?=?2?*?index?+?1;

????????int?rightChild?=?leftChild?+?1;

????????if?((rightChild?<?currSize)?&&?heapArray[leftChild].data?<?heapArray[rightChild].data)

????????????largerChild?=?rightChild;

????????else

????????????largerChild?=?leftChild;

????????if?(top.data?>=?heapArray[largerChild].data)

????????????break;

????????heapArray[index]?=?heapArray[largerChild];

????????index?=?largerChild;

????}

????heapArray[index]?=?top;

}

?

public?class?Heap

{

????Node[]?heapArray?=?null;

????private?int?maxSize?=?0;

????private?int?currSize?=?0;

????public?Heap(int?maxSize)

????{

????????this.maxSize?=?maxSize;

????????heapArray?=?new?Node[maxSize];

????}

public?bool?InsertAt(int?pos,?Node?nd)

{

????????heapArray[pos]?=?nd;

????????return?true;

}

????public?void?ShowArray()

????{

????????for?(int?i?=?0;?i?<?maxSize;?i++)

????????{

????????????if?(heapArray[i]?!=?null)

????????????????System.Console.Write(heapArray[i].data?+?"??");

????????}

????}

????static?void?Main()

????{

????????const?int?SIZE?=?9;

????????Heap?aHeap?=?new?Heap(SIZE);

????????Random?RandomClass?=?new?Random();

????????for?(int?i?=?0;?i?<?SIZE;?i++)

????????{

?

????????????int?rn?=?RandomClass.Next(1,?100);

????????????aHeap.Insert(rn);

????????}

????????Console.Write("Random:?");

????????aHeap.ShowArray();

????????Console.WriteLine();

????????Console.Write("Heap:?");

????????for?(int?i?=?(int)SIZE?/?2?-?1;?i?>=?0;?i--)

????????????aHeap.ShiftDown(i);

????????aHeap.ShowArray();

????????for?(int?i?=?SIZE?-?1;?i?>=?0;?i--)

????????{

????????????Node?bigNode?=?aHeap.Remove();

????????????aHeap.InsertAt(i,?bigNode);

????????}

????????Console.WriteLine();

????????Console.Write("Sorted:?");

????????aHeap.ShowArray();

????}

}

字典 DictionaryBase 和 SortedList