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

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

Интерфейсът IDictionary

Имплементациите на IDictionary биват няколко вида: само за четене (read-only), с фиксиран размер и с променлив размер. При колекциите, които са само за четене, не се позволява промяна на елементите им. При имплементация с фиксиран размер не се позволява добавяне и премах­ване на елементи, но е позволена промяната на вече съществуващи елементи. При имплементация със променлив размер е позволено добавя­не, премахване и промяна на елементи.

Класът Hashtable

Обектите, които се използват за ключове в хеш-таблица, трябва да импле­ментират или наследяват методите GetHashCode() и Equals(…). Структу­рата от данни "хеш-таблица" не може да работи без функция за пресмя_­тане на хеш-код за съхраняваните ключове и без функция за сравнение на ключове. При това ключовете, които се считат за еднакви, задължи­телно трябва да имат еднакъв хеш-код.

Тъй като всеки клас наследява System.Object, то той автоматично насле­дява и предефинирана имплементация на Equals(…). За съжаление, в общия случай тази имплементация се реализира чрез сравнение за съвпадение на референциите на двата обекта. Това генерално погледнато е грешен начин за сравнение и затова се налага да се имплементират специфични реализации за създадените от нас класове. Имплементацията на Equals(…) трябва да връща винаги един и същ резултат, когато се вика с едни и същи параметри.

Докато има записани някакви елементи в хеш-таблицата, ключовете им не трябва да се променят! В противен случай търсенето по ключ може да не работи правилно. Този проблем може да се получи, ако се използва за ключ референтен тип.

Класът Hashtable имплементира интерфейса IDictionary, а той от своя страна наследява IEnumerable. Това ни позволява свободата да изпол­зваме оператора foreach за да обхождаме елементите на хеш-таблици.

Hashtable – пример

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

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

Каталог: dotnetbook
dotnetbook -> Кратко съдържание
dotnetbook -> Кратко съдържание

Изтегляне 9.03 Mb.

Сподели с приятели: