В днешната статия ще проучим вътрешните реализации на Dictionary и Set в езика Swift и как тези реализации влияят на тяхното специфично поведение. До края на тази статия ще разберем:

  • защо речникът съхранява стойности по неподреден начин?
  • защо наборът съхранява стойности по неподреден начин?
  • защо наборът не съдържа дублирани стойности?

В езика Swift има три типа колекции: масив, речник и набор

Масив, вероятно най-често използваният тип колекция, обикновено се използва за попълване на Списъци в SwiftUI или TableView в UIKit. Масивите са базирани на индекс колекции, което означава, че всяка стойност има сдвоен индекс и елементите следват определен ред.

Набор се различава по това, че няма свързани индекси. Стойностите в набор могат да бъдат достъпни само чрез итерация през него. В сравнение с Array, Set не може да съдържа дублирани стойности и стойностите му не са подредени. Следният пример илюстрира това:

Както можете да видите, има само една „Полша“ и редът на елементите не съвпада с посочения от нас ред.

Речник ни позволява да извличаме стойности с помощта на свързани ключове и подобно на набор, стойностите му не са подредени.

Сега, след като разбираме разликите между масив, набор и речник, нека се потопим в документацията и да проверим какви изисквания трябва да бъдат изпълнени, за да се използва всеки от типовете колекции.

Добавянето на каквато и да е стойност към Масив е лесно, тъй като Elements не е необходимо да отговарят на какъвто и да е протокол.

За набор неговите елементи трябва да отговарят на протокола Хеширане.

По същия начин Ключът на речника трябва да съответства на протокола Hashable. Съответствието с протокола Hashable гарантира, че даден тип може да произведе уникална хеш стойност на цяло число.

За точно същите стойности ще бъдат върнати същите хеш стойности. По подразбиране всички типове стойности прилагат протокола Hashable.

Създаването на хеш стойност от множество стойности се извършва с помощта на Hasher. Извикваме комбиниране на стойности и след като приключим, извикваме функция за финализиране, която връща хеш стойност. Редът на комбинацията от стойности е важен. В следващия пример hasher3, за разлика от hasher1 и hasher2, започва комбинацията с „текст“, последван от 23. В резултат на това той генерира уникален хеш.

Хеш стойностите могат също да бъдат генерирани от референтни типове — Класове. Всичко, което трябва да направим, е да се съобразим с протокола Hashable и да приложим два метода. В следващия пример, тъй като struct е тип стойност и нейните стойности са типове стойности, не е необходимо да добавяме метод == и хеш. За абсолютно еднакви стойности два различни типа ще върнат една и съща хеш стойност.

От решаващо значение е да разберете как работи Hashable, за да разберете внедряването на Речник.

Може би сте забелязали, че хеш-стойността може да приема големи числа, така че хеш-стойността трябва да се преобразува в разумен индекс чрез вътрешната функция на речника. Понякога има ситуации, при които различни ключове се преобразуват в един и същ индекс в масив. Това е известно като хеш колизия. За да се справи с това, всеки елемент е „свързан списък“. Всички възли на свързания списък се състоят от ключ и стойност и препратка към следващия код. В горния пример вмъкването на стойността с ключ “FIN” започва с хеширане на ключ и след това преобразуване в индекса на масива. Под индекс 1 вече има елемент с ключ “PL”. Тъй като ключовете „FIN“ и „PL“ не са равни, новият елемент се добавя като следващ възел в свързания списък. Замяна на елемент ще се случи, когато добавим нов елемент с ключ, който вече съществува в HashTable.

Конструкцията на комплекта е подобна. Вместо хешируем ключ, ние използваме хешируема стойност.

С познаването на структурите от данни и алгоритмите, използвани в Set и Dictionary, можем да отговорим на зададените по-рано въпроси.

Въпрос 1: защо Речникът съхранява стойности по неподреден начин?

Отговор: Никога не знаем къде в HashTable ще бъде поставен определен ключ.

Въпрос 2: защо Set съхранява стойности по неподреден начин?

Отговор: Никога не знаем къде в HashTable ще бъдат поставени стойностите.

Въпрос 3: защо наборът не съдържа дублирани стойности?

Отговор 3: Две еднакви стойности ще бъдат присвоени на един и същ индекс в HashTable, така че нова вмъкната стойност ще замени старата.

В крайна сметка си струва да знаете за предимствата на сложността на търсенето на Set спрямо Array. Когато търси елемент в масива, програмата трябва да премине през всички елементи и да ги сравни с търсения елемент. В случай на набор, търсената стойност се преобразува в цифрови представяния, които сочат към място в паметта, където се намира тази стойност. Така че сложността на търсенето на Set е O(1), докато сложността на Array е O(n).

Добре, това е засега. Ако тази статия е била ценна за вас, любезно ви моля да обмислите възможността да я споделите с други, които биха могли да се възползват от нея.

Благодарим ви, че прочетохте до края. Моля, обмислете следването на писателя и тази публикация. Посетете Stackademic, за да разберете повече за това как демократизираме безплатното обучение по програмиране по света.