Хештаблица
Hashtable
В тази тема ще видим как да доразвием идеята за хеширане до структура данни, която позволява много бързо (константно) добавяне, търсене, и изтриване на елементи - стандартните операции в повечето структури данни за съхранение на произволни обекти. Ще разгледаме два различни подхода за имплементация (чрез "separate chaining" и чрез "open addressing"). Ще обсъдим сложностите (и скритите зад тях константи), както и ще покажем примерна имплементация.
Задача за клиенти на банка
Нека имаме следната примерна задача, която искаме да решим.Банка иска да пази информация за телефонните номера на клиентите си, и по-конкретно - по дадено име на клиент бързо да може да намери неговия телефонен номер. За целта трябва да може да се добави нов клиент (с неговия телефонен номер), да се промени телефонния номер на вече съществуващ клиент, а както и да се изтрие записа за даден клиент (в случай, че той закрие сметката си в банката). Разбира се, трябва да може и да се пита дали даден човек е клиент на банката и ако да - какъв е телефонният му номер.
През цялата тема ще правим референции към тази задача, показвайки как можем да ползваме хештаблица за решаването й.Досегашни структури данни
Ползвайки прости структури данни, като масив или свързан списък, потенциално би се наложило да претърсим всички клиенти на банката, за да намерим телефонния номер на някой от тях, което означаваO(N) сложност в най-лошия случай.Леко подобрение е да държим клиентите на банката сортирани в масива, като така търсенето и обновяването ще станат логаритмични (тъй като ще можем да приложим двоично търсене). Добавянето и изтриването на клиенти, обаче, ще си останат линейни операции.
Ползвайки по-сложна структура данни, като например двоично дърво за търсене, сложността на всички операции би била
O(logN) (ако разчитаме, че клиентите ще биват добавяни в що-годе произволен ред, което съответства на реалността).Можем ли да се справим по-добре? Оказва се, че да!
Хештаблица
Хештаблица (от английски: hashtable) наричаме структура данни, която се базира на хеширане и поддържа константно (O(1)) добавяне, търсене, променяне, и изтриване на елементи. Хештаблицата всъщност е относително проста като идея, но за да се избегнат "лоши случаи" често бива надградена с няколко подобрения. В най-простия си вариант, тя представлява масив от обекти, като всеки обект се намира на позицията в масива, сочена от хеша на обекта. С други думи, ако имаме обект X с хеш 42, обект Y с хеш 13, и обект Z с хеш 17, то Y ще бъде на 13-та позиция в масива, Z ще бъде на 17-та, а X - на 42-ра позиция.
В задачата с банката имаме малко по-различна постановка, тъй като обектите са "сложни". От една страна имаме хора, които индексираме по име, а всеки човек има телефонен номер, което е информацията, която ни интересува за него. Такъв тип обекти се наричат "key/value pairs", тъй като се състоят от ключ (key) - в случая името, и стойност (value) - телефонния номер. Това не променя нещата по никакъв начин - просто вместо да хешираме целия обект, ще хешираме само неговия ключ, а стойността ще поставяме в съответния индекс на масива.
В темата за хеширане видяхме как можем да превърнем произволен стринг в число със зададена от нас големина. Така, например, ако банката има един милион клиента, можем да ползваме хеш с модул MOD малко над милион, като хешът на всяко име ще стане валиден индекс в масив с толкова (MOD) елемента. Тъй като имената обикновено са къси, можем да счетем, че хеширането им е константна операция. От гледна точка на Big-O нотацията, дължините на имената на клиентите не зависи от броя клиенти на банката N, тоест сложността по N за хеширането наистина е
O(1). Индексирането в масив също е O(1) операция, така че намирането на телефонния номер може да стане константно - значително по-добре от логаритъма, който имахме от двоичното търсене или ползването на двоично наредено дърво!Поддържани операции
| ? | Считаме, че ако можем да търсим бързо обект с даден ключ (key), то също така бързо можем и да променяме неговата стойност (value). |
За разлика от двоичното наредено дърво, в хештаблица не можем да търсим ефективно най-малкия, най-големия, или най-близкия елемент, тъй като в хештаблицата елементите не са наредени. Всъщност, техният ред зависи от хеширащата функция, която ползваме, а тя, в общия случай, е произволна. В следствие на това, тези операции биха били с линейна (
O(N)) сложност. Разширяването и смаляването на хештаблица става подобно на динамичен масив и изисква копиране на всички елементи. Тоест, тази операция отново е линейна (
O(N)). Нещо повече, както при разширяването, така и при смаляването, се налага да преизчислим хешовете на всички елементи, тоест тази операция е със значително по-голяма константа, отколкото беше при динамичния масив.Справяне с колизии
В темата за хеширане казахме, че един от основните проблеми на хеширането е възможността да се получат колизии: два различни елемента да имат един и същ хеш. Този проблем не е изчезнал, и всъщност е особено важен за хештаблицата. Представете си, че в примера с банката двама човека с различни имена се случи да имат един и същ хеш. Така бихме могли да върнем телефонния номер на грешния човек!Какво можем да направим, за да се справим с това? Една идея е да заделим значително по-голям масив, отколкото ни е нужен, като така намалим шанса два елемента да получат еднакъв хеш. Ако в примера с банката бяхме заделили масив с два милиона елемента (за един милион клиенти), то шансът два фиксирани човека да имат еднакъв хеш става двойно по-малък.
Все пак, проблемът не изчезва. Даже, както показахме в миналата тема, в следствие на birthday paradox, при един милион обекта, равномерно-разпределени в два милиона клетки, шансът да има поне една двойка различни имена с еднакъв хеш, е почти 100%. Дори да имахме сто пъти по-голям масив, шансът за колизия отново щеше да е над 99%! Тоест, трябва да се примирим с факта, че ще имаме колизии, и вместо това да измислим как да живеем с тях.
На първо време, вместо да пазим само стойността в хештаблицата (и да разчитаме, че хешът еднозначно ще определя обекта), ще пазим целия обект (стойността и ключа). Така в случай, че имаме съмнения за колизия, можем да сравняваме ключвете директно, за да проверим това.
Separate Chaining
Един от двата основни метода за справяне с колизии при хештаблиците се нарича "separate chaining", или просто "chaining". В него ползваме друга структура данни за случаите, в които имаме колизии. Казахме, че шансът два елемента да имат еднакъв хеш е много голям, но какъв е шансът десет елемента да имат еднакъв такъв? При добра хешираща функция - значително по-малък. Шансът сто различни елемента да имат еднакъв хеш вече става пренебрежимо малък.В такъв случай, можем да поставяме всички елементи (ключ и стойност) с еднакъв хеш в друга структура данни, с която сме окей да имаме по-бавни операции. Вместо един елемент от масив, на всяка хеш-стойност ще съпоставим свързан списък (или динамичен масив), в който ще държим всички елементи, които имат този хеш.
| ? | Тъй като във всяка "клетка" реално можем да пазим по повече от един елемент, то масивът от списъци, който правим, може да е дори с по-малък размер от общия брой елементи, които вкарваме. Така гарантирано ще имаме колизии, но пък ще имаме по-малко неизползвани списъци/вектори (реално жертваме бързодействие за памет). Все пак, да правим това е силно непрепоръчително. |
Нека видим какво представляват операциите при тази техника за справяне с колизиите. Добавянето на елемент е равносилно на това просто да го сложим в края на съответстващия на хеша му списък/вектор. Търсенето пък представлява обхождане на списъка/вектора, отговарящ на хеша му. Триенето е намиране и премахване от списък/вектор.
| ! | При не много добра имплементация или хешираща функция, това търсене или премахване може да стане близко, ако не и повече от логаритъм, за някои от елементите. За мнозинството от тях, обаче, ще е константно. |
Open Addressing
Алтернативна техника за справяне с колизиите е все пак да си ползваме масив от единични клетки, но при колизия да пробваме следващата клетка (една надясно), после по-следващата и така нататък, докато уцелим все още неизползвана такава. С други думи, когато почнем да търсим телефонния номер на даден човек, първо хешираме името му и проверяваме дали съответната клетка е празна или не. Ако е празна, значи нямаме информация за този човек в хештаблицата.| ! | Алтернативно, вместо да ползвате дясната клетка като следващ избор, може да приложите някаква друга функция, която по дадено число в интервал ви дава друго число в този интервал. Важно е, обаче, тази функция да обхожда всички елементи от хештаблицата, преди да стигне отново в първоначалната. В противен случай е възможно да почне да се "върти" в някакъв малък цикъл от клетки и никога да не намери празна клетка (макар и такава да има). |
Ако допуснем, че хеширащата функция е добра и разпределя елементите относително равномерно из масива, шансът да получим колизия и да няма празна клетка близо надясно е относително малък. В примера от по-рано, имайки милион елемента в масив с размер два милиона, шансът при хеширането да уцелим вече заета клетка е около 1/2. Шансът и съседната ѝ също да е заета е отново 1/2, тоест шансът две обходени клетки да не стигнат става 1/4.
| ! | Макар и този начин на пръв поглед да изглежда като по-ефективен (ползва по-малко памет и не изисква ползването на допълнителни структури), то имплементирането на операцията изтриване е значително по-сложно. Сещате ли се защо? |
Отново можем да жертваме време за памет, като в случая ще покажем как можем да жертваме памет за време. Ако вместо да пазим масив около двойно по-голям, отколкото ни трябва, ще пазим тройно по-голям такъв (в примера по-горе - с три милиона елемента за един милион имена).
| ? | Дадените сметки тук са малко бакалски и разчитат на това хеширащата функция да е много добра. За съжаление, на практика често става така, че се формират региони от изцяло запълнени клетки, което значително влошава нещата. |
Този вариант има редица проблеми, в следствие на което не е особено популярен. Първо, възможно е да се получи "клъстер" - много имена да попаднат близо едно до друго, и тъй като заемат най-близката свободна клетка, да се получи дълга редица от заети клетки. Всеки път, когато елемент попадне в тази редица, тя трябва да бъде обходена изцяло, преди да се стигне до празна клетка. Нещо повече, след това тази редица става дори по-дълга. В следствие на това, бързодействието на хештаблица с такъв подход за справяне с колизиите деградира експоненциално със запълването на таблицата.
Вторият проблем тук е, че изтриването въобще не е тривиално. Не можем просто да намерим елемента и да го премахнем, защото това може потенциално да наруши логиката за по-късно добавени елементи. Нека, например, първо сме добавили елемента X с хеш 42 и сме го сложили на 42-ра позиция (която е била празна). По-късно сме добавили елемента Y, който също има хеш 42. Тъй като 42-ра клетка вече е била заета, сме потърсили свободна клетка надясно. Да кажем, че 43-та е била свободна и сме го поставили там. След време, обаче, изтриваме X и 42-ра клетка се освобождава. Сега, ако търсим Y, бихме го хеширали (получавайки 42) и да виждайки, че е свободна, бихме стигнали до заключението, че Y не присъства в таблицата!
Други
Съществуват и много най-различни други начини за справяме с колизиите, като например Double Hashing или Cuckoo Hashing.Load Factor
Колко често се получават колизии зависи основно от две неща - от хеширащата функция и от това колко пълна е таблицата. Приемайки, че хеширащата функция е добра, броят колизии остава основно да зависи от това колко запълнена е хештаблицата. Много по-очаквано е да имаме колизия, ако е запълнена на 90%, отколкото ако е запълнена на 10%. Процентът на запълненост се нарича load factor и е нещо много важно за бързодействието на тази структура данни.Можем да увеличаваме или намаляваме размера на хештаблицата, като така контролираме нейния load factor-а. Различни имплементации гледат да го държат под различни константи. Например,
HashMap в Java ползва load factor 0.75, докато други ползват 0.6, или дори 0.5.Разбира се, не може през цялото време load factor-ът да е такъв, какъвто го искаме, тъй като това означава, че след всяко добавяне или изваждане на елемент трябва да променяме размера на масива, който ползваме (а с това и да преизчисляваме хешовете на всички елементи).
Стандартна практика е по-скоро да сложим някакъв интервал около желаното от нас число и да правим
resize() само ако текущият load factor излезе от него. | ! | Тук желаният load factor не е точно по средата на интервала, тъй като обикновено е по-лошо таблицата да става много запълнена (и, съответно, бързодействието да деградира), отколкото да харчим малко повече памет. |
Имплементация
Поради описаните проблеми на Open Addressing, нашата имплементация ще бъде на по-простата (и по-популярна) версия със Separate Chaining.Данни
За простота, в примерната "проста" имплементация ще фиксираме размера на масива (NUM_BUCKETS), като така няма да имплементирамеresize(). В пълната имплементация (линкната в края на темата) ще покажем как можем да направим това, така че да държим броя елементи около желания load factor.За колизиите (различните елементи с еднакъв хеш) ще ползваме динамични масиви (STL-ски vector-и). Така всеки индекс в масива отговаря на даден хеш, а векторът на съответния индекс държи всички различни обекти с този хеш. Напомняме, че трябва да пазим както стойността, така и ключа, за да можем да сравняваме по стойност (а не по хеш), когато вече търсим в съответния вектор. Допълнително, ключът ни трябва и за да можем да хешираме наново всички обекти когато смаляваме или разширяваме таблицата (както можете да видите в пълната имплементация).
const int NUM_BUCKETS = 100003;
struct Object {
string key;
int value;
};
vector <Object> hashtable[NUM_BUCKETS];Хеширане на ключа
Тъй като все пак пишем хештаблица, ни е нужна функция, която да хешира ключовете на обектите. В случая ключът наObject обектите е string, тоест ни трябва хешираща функция за стрингове. Бихме могли да ползваме тази, която показахме в темата за хеширане (базирана на бройни системи), с тази разлика, че модулът сега е броят елементи в хештаблицата, тоест NUM_BUCKETS.
int hashString(const string& str) {
int hash = 1;
for (int i = 0; i < (int)str.size(); i++) {
hash = (hash * 257LL + str[i]) % NUM_BUCKETS;
}
return hash;
}Добавяне на елемент
Добавянето на елемент става като първо го хешираме, за да знаем на коя позиция да го сложим, след което обходим вектора в тази позиция за да проверим дали елементът случайно не е вече в хештаблицата (в който случай просто променяме стойността му). В случай, че не сме го намерили, го добавяме във вектора с обектите с тази хеш стойност.void insert(const string& key, int value) {
int hash = hashString(key);
for (int i = 0; i < (int)hashtable[hash].size(); i++) {
if (hashtable[hash][i].key == key) {
hashtable[hash][i].value = value;
return;
}
}
hashtable[hash].push_back(Object(key, value));
}insert()-ът е O(1). Разбира се, когато работим с хештаблици винаги е хубаво да имаме едно наум за скритата константа от тези "константни, ама не съвсем" операции.Търсене на елемент
Търсенето на елемент ще правим в две части: в първата ще хешираме ключа, а във втората ще го търсим линейно във вектора, който бива сочен от този хеш.int get(const string& key) {
int hash = hashString(key);
for (int i = 0; i < (int)hashtable[hash].size(); i++) {
if (hashtable[hash][i].key == key) {
return hashtable[hash][i].value;
}
}
throw "Element " + key + " not found!";
}exception, като разчитаме, че потребителят ще го хваща (или пък винаги ще вика функцията само за елементи, които със сигурност са в хештаблицата).Относително честа алтернатива на този подход е да се подава втори аргумент, който указва каква стойност да се върне в случай, че няма елемент с дадения ключ:
int get(const string& key, int defaultValue) {
int hash = hashString(key);
for (int i = 0; i < (int)hashtable[hash].size(); i++) {
if (hashtable[hash][i].key == key) {
return hashtable[hash][i].value;
}
}
return defaultValue;
}Премахване на елемент
Премахването на елемент не е особено по-различно от търсенето, но накрая премахваме елемента. В показаната по-долу имплементация просто слагаме последния елемент от вектора на негово място и след това намаляме размера с единица. Няма проблем да направим това, тъй като няма изискване да държим елементите в някакъв ред.void erase(const string& key) {
int hash = hashString(key);
for (int i = 0; i < (int)hashtable[hash].size(); i++) {
if (hashtable[hash][i].key == key) {
hashtable[hash][i] = hashtable[hash].back();
hashtable[hash].pop_back();
return;
}
}
fprintf(stderr, "WARNING: Element %s not found!\n", key.c_str());
}Цялостна имплементация
Цялостна имплементация и тестове може да намерите тук: HashTable.h | HashTableTester.cpp.Задачи
Директна имплементация на хештаблица можете да приложите в задачата Phonelst. По-сложна задачка, също базирана на хеширане, е Cipher Message 2. За малко по-разчупен вариант на хешмап, можете да видите Cuckoo.Приложение
Поради скоростта на операциите си, хештаблицата е една от най-използваните структури данни в "комерсиалното" или "истинското" програмиране (не само състезателното такова). Езици като C++, Python, и Java, разбира се, имат в стандартната си библиотека имплементация: unordered_map/unordered_set в C++, dict/set в Python, и HashMap/HashSet в Java. За някои езици, дори, тя не просто присъства в стандартната библиотека, а е основополагаща за целия език - например, в Javascript всеки обект реално е хештаблица.Референции
За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.
натиснете Enter и изпратете Вашето предложение.
Страницата е посетена 4452 пъти.