Hash Table Implementation


10

Здравейте колеги. Понеже вече минаха изпитите и ни се отвори малко свободно време реших да го оползотворя, като разгледам някои интересни за мен теми относно структурите от данни. И по-конкретно как работят и как се създават хеш-таблици. Аз не бях много добре запознат с подробности, но след достатъчно research успях да направя собствена, а след това метнах и една статия в блога за нея. 

Ако ви е интересно как работят, можете да й хвърлите едно око - клик




Отговори



6

Хубава статия. Харесва ми, че си сложил и unit тестове. За такъв тип класове, които по идея са правени, за да се преизползват, това е важно. Харесва ми още, че си ползвал GitHub - още едно доказателство, че курсовете в академията предават добри практики на учащите. И трето: споделянето и блогването - когато някой блогва доброволно без да му е казано "блогвай за домашно или не взимаш курса", това вече е духът на споделянето, който много ме радва.

Прекрасно е да видиш, че е имало ефект от курс по КПК и че хората мислят вече не просто да напишат някакъв код, а и да го напишат кадърно и да го тестват автоматизирано.

Иначе това е една от задачите от курса по структури от данни и алгоритми - да се напише хеш таблица (собствен клас, който не ползва стандартните библиотеки).

Наков


от svetlin.nakov (31978 точки)


2

Браво колега, разгледах сорса и статията, и си личи че си се постарал. Естествено, имам малко заяждания, но няма как:

* HashTableArray.cs.Items: методът пълни списък с всички асоциации в таблицата, всеки път когато се извика. Защо не използваш итератор, както си направил малко по-горе със Keys?

* Пак там, ред 131: какъв е смисълът да връщаш null стойности? Така както аз го разбирам, null значи че в дадена "кофа" в момента няма нищо - това е имплементационен детайл и ползващият класа не го интересува.

* След това в HashTable.GrowArray когато се натъкнеш на null, слагаш в колекцията default(K) - което значи или null, или ако K е структура - нулирана стойност. В единия случай де факто не правиш нищо, в другия създаваш garbage стойност. Нужна ли е изобщо тази част?

* не виждам да се пазиш от стойности с дублиран ключ :-)

* В HashTable.Keys и HashTable.Items можеш директно да върнеш итератора от HashTableArray, ще ускориш методите и спестиш ненужна индиректност.

* в ArrayNode ми се струва че имаш малко излишни проверки за null

* В про- имплементациите, капацитетът обикновено е просто число, за да се намалят колизиите, тъй като общността на "кофи" в които може да попадне някой ключ зависи от най-големият общ делител между него и капацитета. В този случай използваш 1000,2000,4000..., което значи че четен хеш може да попадне само в четна кофа, хеш делящ се на 4, само в кофа с индекс делящ се на 4 и т.н.

* В статията споменаваш че "GetHashCode() става за учебни цели". Всъщност, GetHashCode е предвиден именно за ползване в хеширащи структури, и трябва да имаме много добра причина за да използваме нещо друго. Хешовете в System.Security.Cryptography са за съвсем други работи.

Впрочем, добра идея да почнеш с хеш-таблиците. Това са едни от най-полезните оръжия в арсенала ни и доброто им познаване е много полезно. +1.

--
intelligence shared is intelligence squared


от staafl (5770 точки)


0
1)2)3) - поправих ги. 4) - Това не е multidictionary. 5)6) - поправени. 7) - не се бях замислял за това. Направих default-ната големина 1051 и се видя по-равномерното разпределение. В тестовете обаче оставих предварителното задаване на големина, за да минават по-бързо, все пак търсим коректен резултат, а не производителност.
8) - В статията споменавам и че хеш функциите имат различни свойства. Ако искаш хеш, който не може да се ривърсне, тоест сигурен, с този няма да стане. Ако искаш хеш, който да ти гарантира уникална стойност, този не го прави - http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx Ако обаче искаш нещо бързо и не ти се налага да работиш с чувствителна информация getHashCode() е идеален. MSDN - The System.Security.Cryptography namespace provides cryptographic services, including secure encoding and decoding of data, as well as many other operations, such as hashing, random number generation, and message authentication. For more information, see Cryptographic Services.
Благодаря за code review-то. По едно време се бях омотал и това допринесе за тези недоразумения.

от georgi.ivanov (3261 точки)

0
добра работа. по коментарите:
4 - не бях видял че в ArrayNode.Add хвърляш ArgumentException - малко е заровено. Оттеглям забележката. Впрочем, в такива случаи лично аз обичам да пускам един булев параметър "throwExceptionIfЕдиКаквоСи", колкото да се уверя че ползващият метода е наясно с поведението му
7 - Споменавам го за пълнота :-) Все пак, performance е една от причините да ползваме хеш таблици. Впрочем, за числата от порядъка на големината на хеш-таблица, таблица с пресметнати 1000 прости числа + елементарна проверка с делене до корен квадратен е напълно достатъчна.
8 - Това казвам и аз. В случая с хеш-таблицата не ти трябва нито криптографска сигурност, нито уникалност - трябва ти само бързина и горе-долу равномерно разпределение. Единствената причина при която бих си играл с друг хеш е, ако знам предварително че ключовете ми имат някакво статистическо разпределение, от което да се възползваm (примерно при числа до 1 милион може да вдигнa на степен + модул за да ги "разхвърлям")

от staafl (5770 точки)


0
Впечатли ме опитът ти да създадеш хеш-таблица и да обясниш това, ще видя какво ще направя и аз за домашно :-)
Тук бих споделила първата ми "среща" с асоциативния достъп като най-близък до човешкия, или да кажем, "разумния" начин на съхраняване и търсене на инфо. Това беше една книга на Дж. Мартин от преди години, в която той подробно обясняваше различните методи, които впрочем станаха класика.
Ставаше въпрос за съхраняване и търсене на физическо ниво, и то за дискови памети. При тях критично за бързината при търсене на данни е времето за позициониране на главите върху пътечките, разположени концентрично около оста (шпиндела), тъй като механиката е в пъти по-бавна от електронната част.
Основно предимство на асоциативния достъп е това, че адресът (номер на пътечка) за съответния запис се изчислява чрез хеш-функция от самото съдържание и след това директно се позиционира главата върху пътечката - значителна икономия на време, ако се сравни с едно разкарване по целия диск навътре-навън, дока то се намери записът, както при останалите методи.
Как се решава проблемът с еднаквите ключове? Много просто - те се разполагат върху една пътечка и веднъж позиционирала главата, започва да търси по сектори, като в рамките на един оборот (незначително време) намира съответния запис.
Ако броят на еднаквите ключове е по-голям от броя на секторите върху пътечката, се предвижда резервна - подобно на това, което ни разказаха на лекцията. Но това е САМО още едно позициониране :-)
Това, както и други понятия в изкуствения интелект (например, "размитите" множества), ме порази с практичността си - приближаваш се максимално точно, с най-малко разходи, до целта - не е необходимо всичко да е идеално; след това я постигаш с точни средства.

от ellapt (6303 точки)


0
На мен не ми е ясно едно нещо. Да речем, че в даден момент големината на масива, който съдържа свързаните списъци с

от denis.rizov (205 точки)


0
Когато преоразмеряваш масива трябва да изчислиш нов индекс за всеки един елемент от стария масив - не копираш просто списъците от първия масив във втория, а добавяш елементите един по един в новия масив.

от pirin (1101 точки)

0
Благодаря ти много. От вчера си блъскам главата, а решението е било много просто :)

от denis.rizov (205 точки)