Хештаблица

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.
!Макар и този начин на пръв поглед да изглежда като по-ефективен (ползва по-малко памет и не изисква ползването на допълнителни структури), то имплементирането на операцията изтриване е значително по-сложно. Сещате ли се защо?
Шансът след двадесет обходени клетки все още да не сме намерили свободна такава, е около 0.0000954%. Шансът още да не сме намерили свободна клетка след 50 обходени клетки е 0.000000000000009%, тоест вече става пренебрежимо малък. При това, този шанс е в най-лошия случай - за мнозинството от елементите ще трябва да обходим едва няколко клетки (най-често една).

Отново можем да жертваме време за памет, като в случая ще покажем как можем да жертваме памет за време. Ако вместо да пазим масив около двойно по-голям, отколкото ни трябва, ще пазим тройно по-голям такъв (в примера по-горе - с три милиона елемента за един милион имена).
?Дадените сметки тук са малко бакалски и разчитат на това хеширащата функция да е много добра. За съжаление, на практика често става така, че се формират региони от изцяло запълнени клетки, което значително влошава нещата.
Така шансът клетката да е вече пълна при първоначалното хеширане на обекта е 1/3; след една допълнителна клетка става 1/9; след третата 1/27 и т.н. Шансът след двадесет клетки да не сме намерили свободна такава е 0.000000003%, а след петдесет - едва 0.0000000000000000000000001%. Разбира се, колкото повече памет ползваме, толкова повече намалява шансът да се нуждаем от дълги обхождания на клетки.

Този вариант има редица проблеми, в следствие на което не е особено популярен. Първо, възможно е да се получи "клъстер" - много имена да попаднат близо едно до друго, и тъй като заемат най-близката свободна клетка, да се получи дълга редица от заети клетки. Всеки път, когато елемент попадне в тази редица, тя трябва да бъде обходена изцяло, преди да се стигне до празна клетка. Нещо повече, след това тази редица става дори по-дълга. В следствие на това, бързодействието на хештаблица с такъв подход за справяне с колизиите деградира експоненциално със запълването на таблицата.

Вторият проблем тук е, че изтриването въобще не е тривиално. Не можем просто да намерим елемента и да го премахнем, защото това може потенциално да наруши логиката за по-късно добавени елементи. Нека, например, първо сме добавили елемента 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 не е точно по средата на интервала, тъй като обикновено е по-лошо таблицата да става много запълнена (и, съответно, бързодействието да деградира), отколкото да харчим малко повече памет.
Например, ако сме решили load factor-ът да е 0.66, то подходящ интервал би бил, например, [0.5, 0.75]. В случай, че броят елементи стане под 1/2 (0.5) то свиваме таблицата така, че след това load factor-ът да е около 0.66. Ако пък сме добавяли много нови елементи и load factor-ът стане над 0.75, то разширяваме хештаблицата така, че да стане отново около 0.66. Тази стратегия цели да не се налага твърде честа промяна на размера на хештаблицата ако добавяме и вадим по що-годе равен брой елементи.

Имплементация

Поради описаните проблеми на 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
;
}
Приели сме, че ще работим с ASCII символи, тоест знаци с кодове между 0 и 255, включително.

Добавяне на елемент

Добавянето на елемент става като първо го хешираме, за да знаем на коя позиция да го сложим, след което обходим вектора в тази позиция за да проверим дали елементът случайно не е вече в хештаблицата (в който случай просто променяме стойността му). В случай, че не сме го намерили, го добавяме във вектора с обектите с тази хеш стойност.
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))
;
}
Забележете, че тук нито хеширането на ключа, нито обхождането на вектора са константни операции. Тъй като, обаче, считаме, че ключовете ще са относително къси (много по-къси от NUM_BUCKETS), а броят елементи във всеки вектор от хештаблицата ще е относително малък (много по-малък от NUM_BUCKETS), то, от гледна точка на броя елементи в хештаблицата, 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 и изпратете Вашето предложение.
Страницата е посетена 1065 пъти.

Предложете корекция

Selected text (if you see this, there is something wrong)

(Незадължително) E-mail за обратна връзка: