JS DSA Flashcards
Какво е hash-table как съхраняваме елементи?
Хеш таблицата е колекция, която съдържа набор от стойности
computeHash(key) функция изчислява индекс чрез хеширане на ключ. Индексът съответства на position в масив / array, където се съхраняват стойности Перфектна функция за хеширане произвежда същия хеш за същия ключ
Сollide (един ключове, едни и същи хешове)
Каква е сложността на общите операции с хеш таблици?
Хеш таблицата има O(1) сложност за операции, базирани на ключове
add()
remove()
get()
update()
Скоростта на обработка на данните не зависи от размера на хеш таблицата
Какво е алгоритъм за хеширане?
computeHash(key) Перфектна функция за хеширане произвежда същия хеш за същия ключ
Produces the same hash for the same key Perfect hashing function
Hashes never collide (different keys, same hashes)
hash=computeHash(‘JohnJamison’);//28782839483 (depends on hash fn)
index=hash%buckets.length;//3
buckets[index]=’JohnJamison’;
“
Какво е collision? Как можем да разрешим collision?
Колизия е ситуация, когато различни ключове имат една и съща хеш стойност
- Стратегии за разрешаване на колизии
- Записване в съседна клетка
- Второ хеширане
- Преоразмеряване - сложна операция
( computeHash(key1) == computeHash(key2) ) за ( key1 != key2 )
Подходи за разрешаване на колизията са:
Chaining in a list
Using the neighboring slots (linear probing)
Re-hashing (second hash function)
Кои са важните характеристики на set?
Set– тип абстрактни данни с уникални елементи. при които реда не е определящ Set е нелинейна структура от данни, която имплементира структурата на абстрактните данни Set, обикновено чрез използване на хеш таблица.
Има две характеристики:
1. Елементите са уникални
2. Редът не е важен.
Операциите, които можем да използваме с Set , са:
- add(item) → добавя даден елемент към набора → O(1)
- Елементът е добавен някъде, в никакъв ред или място
- не е възможно добавяне на аналогичен елемент - са уникални.
- remove(item) → премахва елемент от набора → O(1)
- contains(item) → определя дали елементът е в набора → O(1)
- size() → връщане на текущия брой елементи → O(n)
”
Дайте пример за алгоритми, които можем да подобрим с помощта на set?
Adding elements
constset=newSet();
set.add(1); // {1}
set.add(2); // {1,2}
set.add(7); // {1,2,7}
set.add(7); // {1,2,7}
Checking
set.has(1); // true
set.has(8); // false
Removing
set.delete(1); // {2, 7}Кои са важните характеристики на map?
Map е нелинейна структура от данни, която реализира структурата на абстрактни данни Асоцииран масив, обикновено чрез използване на хеш таблица или двоични дървета.
Map е колекция от елементи, където всеки елемент се съхранява като двойка ключ-стойност. Обектът на Map може да съдържа както обекти, така и примитивни стойности като ключ или стойност. Когато превъртаме обекта на Map, той връща двойката ключ-стойност в същия ред, както е добавен. .
Map позволява намирането на стойности чрез дефинирани от потребителя уникални ключове.
Операциите, които можеm да използваme с Map, са:
new Map()– creates the map.
map.set(key, value)– stores the value by the key. O(1)
map.get(key)– returns the value by the key,undefinedifkeydoesn’t exist in map. O(1)
map.has(key)– returnstrueif thekeyexists,falseotherwise. O(n)
map.delete(key)– removes the value by the key. O(1)
map.clear()– removes everything from the map.
map.size– returns the current element count.
Дайте пример за алгоритми, които можем да подобрим с помощта на map?
Имплементиране на hash table с Map class.
Най-използвани функции:
set(key, value) – добавя или актуализира value по даден ключ key
get(key) – връща value или undefined
delete(key) – изтрива key/value pair by key
has(key) – проверява дали даден key съществува
entries() – връща колекция от key/value pairs
Алгоритъмът
Последователност от инструкции, при изпълнението на които се решава определен формулиран проблем. Алгоритъмът е „абстрактно“ описание на процес, което е точно, но общо
Алгоритъмът е правилен ако дава правилен резултат за всички входни данни, при един неправилен отговор за един или повече входни данни е неправилен алгоритъм.
Евристичните алгоритми приближават правилния отговор и имат точност за скорост.
Програма
Имплементация на алгоритъм за конкретна машина на конкретен език
Type of Complexity
O(1) - Constant Complexity
O(n) - Linear Complexity
O(n2) - Quadratic Complexity
O(log n) - Logarithmic Complexity O(n3) - Cubic Complexity:
O(n log n) - Linearithmic Complexity: O(2n) - Exponential Complexity
Сложността не е еквивалентна на броя на инструкциите.
Ние се фокусираме върху това как броят на операциите расте с нарастването на входа.
Array
Fixed number of contiguous memory cells
Dynamic Array
Array that resizes itself as it grows
LinkedList
Nodes that reference the next one / each element has a reference to the next one/
Linked List е линейна структура от данни, която implementira абстрактната структура от данни List динамично. Идеята е че всеки елемент знае за съществуване на следващаия елемент или node.
Link list използва повече памет защото има референции елементите се заменят/изтриват /добавят по лесно защото не се налага преинициализиране на индекса както е в арей лист
При Singly linked list елемента има само next знае кой е следващия елемент или node Doubly linked list елемента знае кой е предходния и следващия елемент или node
Stack
LIFO - Стекът осигурява достъп до елемента последен влязъл, първи излязъл. Най-полезно, когато алгоритъмът зависи от такъв достъп (such as DFS, Undo/Redo functionality, the Call Stack).
Функционалност на класа на стека:
- push() - добавя елемент в горната част на стека
- pop() - премахва елемента от горната част на стека
- peek() - връща стойността на горния елемент, без да го премахва
- count - връща броя на елементите в стека
- isEmpty - връща булева стойност, показваща дали стекът е празен
Операциите с данни на тези структури поддържат деструктивно актуализиране когато имаме достъп до елемент ние го премахваме от структурата.
