Кратко съдържание



страница59/73
Дата21.07.2018
Размер8.57 Mb.
1   ...   55   56   57   58   59   60   61   62   ...   73

Речникови колекции


Нека сега разгледаме и по-сложната част от средствата за работа с колекции в .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 е използван за да съхранява съответствия между модели леки автомобили и техните цени. Понеже за ключ се изпол­зват моделите на автомобилите, след добавянето на няколко автомобила в сортирания списък, те могат да бъдат извлечени след това в азбучен ред чрез просто обхождане.

След изпълнение примерът извежда на конзолата следното:




1   ...   55   56   57   58   59   60   61   62   ...   73


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница