diff options
fix typo
1 files changed, 9 insertions, 9 deletions
| -rw-r--r-- | Seminar14/README.md | 18 |
diff --git a/Seminar14/README.md b/Seminar14/README.md index 481116a..f74e6ae 100644 --- a/Seminar14/README.md +++ b/Seminar14/README.md @@ -23,23 +23,23 @@ The dictionary problem is the classic problem of designing efficient data struct Речниците са **най - популярната** нетривиална структура от данни в компютърните науки. Причината е, че много проблеми от реалния свят могат ефикасно да се решат с речници. ## Интуиция -Цял семестър сме си водили старателно записки по всички предмети и сега изпитите наближават. Това предполага много четене, разбира се от записките, които старателно сме водили цял семестър. Това предполага, че често ще ни се налага да търсим записки от определена лекция. +Цял семестър сме си водили старателно записки по всички предмети и сега изпитите наближават. Това предполага много четене, разбира се от записките, които старателно сме водили цял семестър. Ясно е, че често ще ни се налага да търсим записки от определена лекция. -Слагаме свички записки на куп, без никаква наредба. Сега, за да намерим записките от третата лекция по структури от данни ще ни се наложи да претърсим целия куп от лекции. Никой обаче не учи по един предмет цял ден, вероятно след 3 часа учене по структури от данни ни се иска да прочетем нещо по функционално програмиране и сега пак претърсваме целия куп. +Слагаме всички записки на куп, без никаква наредба. Сега, за да намерим записките от третата лекция по структури от данни ще ни се наложи да претърсим целия куп от лекции. Никой обаче не учи по един предмет цял ден, вероятно след 3 часа учене по структури от данни ни се иска да прочетем нещо по функционално програмиране и сега пак претърсваме целия куп. -Отиваме до Икеа и си купуваме 6 кутии. Правим логичното нещо - слагаме записките по структури от данни в първата, тези по функционално във втората и тнт. +Отиваме до Икеа и си купуваме 6 кутии. Правим логичното нещо - слагаме записките по структури от данни в първата, тези по функционално във втората и тнт. Сега, ако ни се наложи да търсим записки по определен предмет вече няма да се налага да изровим целия куп с листи а само кутията в която се намират те. ## Хеш функции Интуитивно хеш таблиците ще са просто множество от кутии (или както се наричат в практиката buckets(кофи)). За реализацията на хеш таблици използваме хеш функции, които при додаден ключ генерират индекс (хеш код), на който трябва да се запише съответната стойност. -Това звучи страхотно, но по принципа на Дирихле ако имаме повече елементи за слагане в кофите отколкото кофи ще се наложи да сложим поне два елемента в една кофа. Нека *X* и *Y* са два различни ключа. Абсолютно възможно е +Това звучи страхотно, но по принципа на Дирихле ако имаме повече елементи за слагане в кофите отколкото кофи ще се наложи да сложим поне два елемента в една кофа. Това на практика става и преди да елементите да станат повече от кофите. Нека *X* и *Y* са два различни ключа. Абсолютно възможно е ``` h(X) = h(Y) ``` -и това наричаме колизия. От тук можем да си направим два извода. Първо, хеш функцията **не е обратима** и второ ще трябва да измислим някакъв начин да се справим с тези колизии. +и това наричаме *колизия*. От тук можем да си направим два извода. Първо, хеш функцията **не е обратима** и второ ще трябва да измислим някакъв начин да се справим с тези колизии. Какво наричаме добра хеш функция? * Функцията трябва да използва всички данни от ключа. @@ -58,7 +58,7 @@ int hashDummy(int key) { Какво наричаме перфектна хеш функция? Няма такава. Добрата хеш функция се държи добре върху определен вход, но няма универсална хеш функция. Намирането на добра хеш функция може да изисква голямо задълбочено разбиране в някои математически дисциплини. ## Справяне с колизии - Separate chaining -Нека си мислим за кофите като масив от свързани списъци. +Нека си мислим за кофите като за свързани списъци. За всеки елемент, индексът на свързания списък, в който трябва да го добавим се определя от хеш функцията. ```cpp @@ -75,7 +75,7 @@ void insert(const Key& k, const Value& v) { table[idx].push_back({k, v}); } ``` -Проблем: какво правим когато ключа вече съществува? Ако оставим кода така ще имаме списък с два ключа, имащи различни стоъности. +Проблем: какво правим когато ключът вече съществува? Ако оставим кода така ще имаме списък с два ключа, имащи различни стойности. Полезно е да имаме функционалност, която ъпдейтва стойността на ключа. Правим следното: ```cpp @@ -84,7 +84,7 @@ void insert(const Key& k, const Value& v) { for(auto& elementInBucket : table[idx]) { if(elementInBucket.key == k) { - elementInBucket.value = v; + elementInBucket.value = v; // update key return; } } @@ -93,7 +93,7 @@ void insert(const Key& k, const Value& v) { } ``` -Страхотно, сега търсенето ни се свежда до линейно търсене в списък: +Страхотно, сега търсенето ни се свежда до търсене в списък: ```cpp Value getValue(const Key& k) { size_t idx = index(k); |
