Нека сега разгледаме и по-сложната част от средствата за работа с колекции в .NET Framework – речниковите колекции.
Интерфейсът IDictionary
Интерфейсът IDictionary е базов за речниковите колекции. Всеки техен елемент представлява двойка от тип ключ-стойност, която се съхранява в обект от тип DictionaryEntry. Ключът на всяка двойка трябва да е уникален и различен от null, а стойността, асоциирана с този ключ, може да е какъвто и да е обект, включително null. Интерфейсът IDictionary позволява съдържаните в колекцията ключове да се изброяват, но не ги сортира по какъвто и да е признак.
IDictionary поддържа операциите добавяне на нова двойка ключ-стойност (Add(…)), търсене на стойност по ключ (индексатор), премахване на двойка по ключ (Remove(…)), извличане на всички ключове (Keys), извличане на всички стойности (Values).
Имплементациите на IDictionary биват няколко вида: само за четене (read-only), с фиксиран размер и с променлив размер. При колекциите, които са само за четене, не се позволява промяна на елементите им. При имплементация с фиксиран размер не се позволява добавяне и премахване на елементи, но е позволена промяната на вече съществуващи елементи. При имплементация със променлив размер е позволено добавяне, премахване и промяна на елементи.
Класът Hashtable
Hashtable представлява имплементация на структурата от данни "хеш таблица" – речникова колекция, елементите на която се разполагат в специално заделена памет в зависимост от хеш кода на ключа на всяка от тях. Имплементацията на класа е направена така, че да позволява добавянето на елемент и търсенето по ключ да стават с константна сложност в средния случай. Тъй като класът имплементира IDictionary, това означава, че всеки ключ трябва да е уникален и различен от null.
Обектите, които се използват за ключове в хеш-таблица, трябва да имплементират или наследяват методите GetHashCode() и Equals(…). Структурата от данни "хеш-таблица" не може да работи без функция за пресмятане на хеш-код за съхраняваните ключове и без функция за сравнение на ключове. При това ключовете, които се считат за еднакви, задължително трябва да имат еднакъв хеш-код.
Тъй като всеки клас наследява System.Object, то той автоматично наследява и предефинирана имплементация на Equals(…). За съжаление, в общия случай тази имплементация се реализира чрез сравнение за съвпадение на референциите на двата обекта. Това генерално погледнато е грешен начин за сравнение и затова се налага да се имплементират специфични реализации за създадените от нас класове. Имплементацията на Equals(…) трябва да връща винаги един и същ резултат, когато се вика с едни и същи параметри.
|
Докато има записани някакви елементи в хеш-таблицата, ключовете им не трябва да се променят! В противен случай търсенето по ключ може да не работи правилно. Този проблем може да се получи, ако се използва за ключ референтен тип.
|
Класът Hashtable имплементира интерфейса IDictionary, а той от своя страна наследява IEnumerable. Това ни позволява свободата да използваме оператора foreach за да обхождаме елементите на хеш-таблици.
Hashtable – пример
Ето един пример, който демонстрира работата с класа Hashtable и показва как се използват основните операции, свързани с него:
static void Main()
{
Hashtable priceTable = new Hashtable();
priceTable.Add("BMW", 66000);
priceTable.Add("Ferrari", 200000);
priceTable.Add("Ford", 50000);
priceTable.Add("Audi", 80000);
Console.WriteLine("Car \"{0}\", price ${1}",
"Ferrari", priceTable["Ferrari"]);
priceTable.Remove("Ferrari");
priceTable["Audi"] = 88000;
foreach(DictionaryEntry carPrice in priceTable)
{
Console.WriteLine("Car \"{0}\", price ${1}",
carPrice.Key, carPrice.Value);
}
}
|
В примера се използва хеш-таблица за съхранение на съответствия между модели леки автомобили и техните цени. След изпълнението му се получава следният резултат:
Примерът демонстрира добавяне, извличане, изтриване и промяна на елементи в хеш-таблица, както и обхождане на всички елементи с foreach.
Производителност на Hashtable
Два фактора оказват влияние върху производителността на хеш-таблиците: техният размер и уникалността на хеш-кодовете, които се съпоставят на ключовете.
Влияние на колизиите върху производителността
Колизия се получава, когато на два различни ключа на елементи от хеш-таблицата се съпостави един и същ хеш-код. Hashtable използва алгоритъм с двойно хеширане за да намали негативния ефект на колизиите върху производителността, но най-добра производителност се постига когато няма никакви колизии.
Размерът на една хеш-таблица автоматично нараства при запълване до определен процент в резултат от добавяне на нови елементи, с което свежда до минимум вероятността да се получат колизии.
Влияние на размера на хеш-таблицата върху производителността
Операциите, предизвикващи увеличаване на размера на една хеш-таблица, са скъпи, защото предизвикват заделяне на нова памет, ново пресмятане на индексите за елементите и копиране на всеки елемент на нова позиция в таблицата. По подразбиране хеш-таблицата се конструира с размер 0. Това означава, че са необходими много операции по заделяне на памет докато се достигне подходящ размер.
Ако предварително знаете приблизително колко елемента ще добавите в хеш-таблицата, задавайте началния й размер като параметър на конструктора. Ето пример за инициализиране на хеш-таблица, която е оптимизирана за 1000 елемента:
Hashtable table = new Hashtable(1000);
|
Инициализирайки по такъв начин размера на хеш-таблицата, ние не указваме влияние върху производителността на търсещите операции, но можем да подобрим бързодействието на добавянето на нов елемент до няколко пъти.
Фактор на нарастване
Когато една хеш-таблица в .NET Framework нараства, тя винаги приема размер, който е просто число. (Причината за това се дължи на факта, че статистически е по-вероятно, ако n е произволно число, n % m да бъде уникален резултат, когато m е просто). По подразбиране хеш-таблицата увеличава размера си, когато броят на елементите й надвиши даден процент от размера й. Този процент може да се контролира като се променя факторът на нарастване. Фактор на нарастване 1.0 отговаря на 72%, 0.9 отговаря на 65% (0.9*72) и т.н. Валидните фактори на нарастване варират от 0.1 до 1.0.
Ето пример как да инициализираме хеш-таблица за 1000 елемента и да й зададем фактор на нарастване 0.8, което означава че таблицата ще нараства и ще се реиндексира когато броят на елементите й достигне приблизително 58% от размера й:
Hashtable table = new Hashtable (1000, 0.8f);
|
Факторът на нарастване по подразбиране е 1.0 и в повечето случаи не е нужно да се променя.
Увеличаване на уникалността на хеш-кодовете
Увеличаване до възможно най-висока степен уникалността на хеш-кодовете, генерирани от ключовете, е от голяма важност за производителността на хеш-таблиците. При по-уникални кеш-кодове се получават по-малко колизии и от там търсенето и добавянето работят по-бързо.
По подразбиране хеш-таблиците хешират ключовете, като викат техния метод GetHashCode(), който всеки обект е наследил от System.Object. Ако използваме за ключове обекти от клас, чийто метод GetHashCode() не генерира достатъчно уникални хеш-кодове, можем да направим едно от следните неща за да подобрим производителността:
-
Да припокрием метода GetHashCode() в производния клас и да осигурим имплементация, която генерира възможно по-уникални хеш-кодове.
-
Да създадем тип, който имплементира IHashCodeProvider и да подадем референция към обект от този тип на конструктора на хеш-таблицата. Това ще предизвика извикване на метода IHashCodeProvider.GetHashCode() за генериране на хеш-код.
Собствени хеш-функции
Когато използваме собствени класове за ключове в хеш-таблица, те трябва да припокрият методите GetHashCode() и Equals(…) наследени от System.Object.
Собствени хеш-функции – пример
В следващият пример ще демонстрираме как можем да използваме собствен клас за ключ в хеш таблица, като дефинираме по подходящ начин в него виртуалните методи GetHashCode() и Equals(…):
class Student
{
protected string mName;
protected int mAge;
public Student(string aName, int aAge)
{
mName = aName;
mAge = aAge;
}
public override string ToString()
{
return String.Format("({0}, {1})", mName, mAge);
}
public override bool Equals(object aStudent)
{
if ((aStudent==null) || !(aStudent is Student))
return false;
Student student = (Student) aStudent;
bool equals = (mName == student.mName) &&
(mAge == student.mAge);
return equals;
}
public override int GetHashCode()
{
int hashCode = mName.GetHashCode() ^ mAge;
return hashCode;
}
}
class CustomHashCodesDemo
{
private static Hashtable mAddressTable;
static void PrintAddress(Student aStudent)
{
if (mAddressTable.ContainsKey(aStudent))
{
Console.WriteLine("{0} has address: {1}.",
aStudent, mAddressTable[aStudent]);
}
else
{
Console.Write("There is no address for {0}.", aStudent);
}
}
static void Main()
{
Student john = new Student("Sir John", 23);
Student ann = new Student("Lady Ann", 22);
Student richard = new Student("King Richard", 33);
mAddressTable = new Hashtable();
mAddressTable.Add(john, "Nottigham Castle");
mAddressTable.Add(ann, "London Tower");
mAddressTable.Add(richard, "London Castle");
PrintAddress(john);
PrintAddress(new Student("Lady Ann", 22));
PrintAddress(new Student("Lady Ann", 24));
}
}
// Result:
// (Sir John, 23) has address: Nottigham Castle.
// (Lady Ann, 22) has address: London Tower.
// There is no address for (Lady Ann, 24).
|
В примера се използва класът Student като ключ в хеш-таблица, която съхранява съответствия между студенти и техните адреси. Ако в класа Student нямаме имплементация на методите Equals(…) и GetHashCode(), нашата хеш-таблица няма да работи коректно с ключове от тип Student.
Много често наш, собствен тип се състои от няколко различни полета, от които може да зависи хеш-кода на отделен обект от дадения тип. Един възможен начин за генериране на хеш код в такива ситуации е да се обединят хеш-кодовете на различните полета като се използва операцията ^ (изключващо или). Точно така се реализира генерирането на хеш код и в примера по-горе.
Изчисляването на хеш-кода за даден студент става като изчислим хеш-кода за неговото име и извършим операцията "изключващо или" с неговите години. По този начин се стремим да получаваме възможно по-уникални стойности за хеш-кодовете. При еднакви имена или еднакви години най-често стойностите ще са различни. Ако имената и годините на двама студента едновременно съвпадат, ще получим еднакви хеш-стойности (което е едно от важните изисквания при имплементацията на метода GetHashCode()).
Equals(…) е имплементиран така, че да връща винаги false за различни инстанции на обекти от тип Student и true за еднакви.
Класът SortedList
Речниковите колекции могат да бъдат реализирани не само в хеш-таблици, но и по други начин. Класът SortedList, например, представлява имплементация на интерфейса IDictionary, която прилича както на хеш-таблица, така и на масив. Тази колекция съхранява двойки елементи ключ-стойност, сортирани по ключ, като позволява индексиран достъп. Тъй като е нужна непрекъсната поддръжка на сортирана последователност, SortedList работи доста бавно (повечето операции имат линейна сложност).
SortedList – пример
Ето един пример, който илюстрира работата със SortedList:
SortedList sl = new SortedList();
sl.Add("BMW", 66000);
sl.Add("Ferrari", 200000);
sl.Add("Audi", 80000);
sl.Add("Ford", 50000);
sl.Remove("BMW");
sl["Audi"] = 88000;
Console.WriteLine("We sell only:");
foreach (string car in sl.GetKeyList())
{
Console.WriteLine("{0} ", car);
}
Console.WriteLine("\nThe prices are as follows:");
for (int i = 0; i < sl.Count; i++)
{
Console.WriteLine("{0} - ${1}",
sl.GetKey(i), sl.GetByIndex(i));
}
|
В него класът SortedList е използван за да съхранява съответствия между модели леки автомобили и техните цени. Понеже за ключ се използват моделите на автомобилите, след добавянето на няколко автомобила в сортирания списък, те могат да бъдат извлечени след това в азбучен ред чрез просто обхождане.
След изпълнение примерът извежда на конзолата следното:
Сподели с приятели: |