Set, Map and Hash Table

Question 1

What is a hash function?

Answer 1

• функция, която преобразува един сложен обект в друг тип (String/Integer)
• Hash функции превръщат данните с произволна дължина в такива с фиксирана дължина;
• Hash функциите са стабилни(един и същ output при един същ input), сигурни(не могат да бъдат reversed; не можем да получим началната стойност на база резултата от функцията; от изходните данни не можем да стигнем до входните)
• Можем да ги разделим на:
  -> Перфектни
  Ще мапнат всеки ключ към индивидуален индекс
  Трябва да знаем всички ключове предварително (трябва да знаем обема и типа данни предварително)
  -> Добри
  Когато не знаем всички ключове предварително (не знаем обема и типа данни предварително)
  Ще мапнат повечето ключове към индивидуален индекс
• Използват се за запазване на пароли в база данни и търсене по ключ в таблица
• Чрез модулно деление изчисляваме мястото, на което да добавим обекта в масива!!!

Question 2

What is the complexity of adding a pair to a HashTable? Why is it what it is?

Answer 2

Сложността на добавяне на двойка (ключ-стойност) към хеш таблица обикновено е O(1) в средния случай, но може да бъде O(n) в най-лошия случай (защото може да имаме колизия).

Question 3

How many ways do you know for handling collisions?

Answer 3

• Навързване/ Separate Chaining – Когато на даден елемент му бъде отредено същото място като на друг, се образува свързан списък от двата елемента.
• Open Addressing – Когато на даден елемент му бъде отредено същото място като на друг, то той заема следващото свободно място в масива

Question 4

What is the difference between HashMap and TreeMap?

Answer 4

1. HashMap:
   - Хеширане: Използва хеш таблица.
   - Ред на елементите: Не е сортиран.
   - Сложност: O(1) за основни операции.
   - Null: Позволява null (ключове и стойности).
2. TreeMap:
   - Дърво: Използва дърво.
   - Ред на елементите: Поддържа естествен ред или зададен ред чрез компаратор.
   - Сложност: O(log n) за основни операции.
   - Null: Не позволява null ключове (може да има null стойности).

Question 5

What is the complexity of retrieving a pair from a HashMap?

Answer 5

• O(1) в средния случай.
• O(n) в най-сложния случай (заради колизии).

Question 6

What is the complexity of retrieving a pair from a TreeMap?

Answer 6

• O(log n) - защото TreeMap използва червено-черно дърво (балансирано бинарно дърво), което осигурява логаритмична сложност за операции като извличане, добавяне и премахване.