Разбивка на това какво представляват хеш таблиците и как да се кодира такава

Обикновено, когато мисля за хеш таблици, ги виждам като масиви на стероиди. Това е многофункционална структура от данни, която може да реши много видове проблеми и може също така да съхранява огромно разнообразие от типове данни и количества супер ефективно.

Какво всъщност е?

Хеш таблицата е основно масив, който свързва ключ към конкретна стойност на данните. Например, да кажем, че искаме да създадем база данни, която съхранява информацията за профилите на всички потребители на уебсайт; в този случай ключовете ще бъдат имената на потребителите, а стойностите ще бъдат информацията за техния профил, включително неща като дата на раждане, имейл адрес, националност и т.н.

Но как всъщност да поставим цялата тази система върху масив? Индексите на слотовете в масива са цели числа, не потребителски имена, нали?

Използваме хеш функции, за да превърнем ключовете в цели числа. „Те са основно машини за магически числа, които могат да приемат информация с всякаква дължина и да изхвърлят обратно число с фиксиран размер.“ Например, да кажем, че моето потребителско име на уебсайта от предишния пример е „ramyzhang“. Ще въведем този низ в хеш функция и функцията ще направи куп изчисления, за да изплюе число от, да речем, 5 цифри или число, което достига максимум до 10 (в зависимост от вида на хеша функция е). Това число винаги ще бъде свързано с низа „ramyzhang“, без значение колко пъти сте поставили „ramyzhang“ през функцията.

След това, тъй като полученият хеш е цяло число, можете просто да отидете и директно да използвате това число като индекс за информацията за профила на потребителя „ramyzhang“.

Верижният метод

Нека просто направим кратка пауза, за да помислим за хеш функциите за секунда – тъй като преобразуваме данни с произволна дължина (x) в данни с фиксиран размер (y), набор от данни xще бъде много по-голям от набора от данни y. Има безкрайни записи в набора от данни x, но ограничени в набора от данни y, тъй като всички числа трябва да са с определен размер или дължина. С други думи, възможно е да има две или повече части от данни в набор от данни x, които ще хешират едно и също цяло число в набор от данни y.

Това се нарича проблем със сблъсък и ето какво можете да направите, за да се справите с него:

Когато две или повече части от данни се сблъскати хешират към едно и също цяло число (индекс), можем просто да свържем данните в „свързан списък“ на този индекс на масива, както можете да видите по-горе .

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

Като цяло, ако имате добра хеш функция, сблъсъците трябва да се случват по-рядко. Нека да разгледаме други видове решения на проблема със сблъсъка.

Методът на линейното сондиране

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

Нека този път направим това с конкретен пример.

Събрах следния мини набор от данни за идентификатори на книги, които представляват разположението на всяка книга в библиотека:

Добре, сега имаме нужда от хеш функция, за да нанесем всичко това в масив. Тъй като наборът от данни има дължина 10, ние просто ще направим хеш функцията x mod 10 =y. (Уверете се, че проучете как да използвате по-добра хеш функция, ако наистина искате да създадете добра хеш таблица, това е само за пример!)

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

Уау, това са много сблъсъци. Преди да се опитаме да поправим това, нека бързо реорганизираме набора от данни, така че да е в хронологичен ред:

Добре, всичко е наред! Нека опитаме да приложим метода на линейното сондиране сега. Това, което искаме да направим, е да вземем данните, които са се сблъскали, и да преведем другата надолу по масива, докато намери следващия свободен слот. Така че ключът 245 вече ще има индекс 6 вместо 5, а ключът 8 ще има индекс 10 вместо 8. Нека разгледаме много нови нови индекси:

Изглежда доста добре! Това е методът на линейно изследване. Сега, ако искате, можете да извадите 1 от всички тези момчета (тъй като масивите започват с индекс 0) или дори просто да го запазите както е и да имате масив с 11 слота.

Кодирайте го!

Сега, след като имаме основна представа както за верижния метод, така и за метода на линейно изследване, нека изградим хеш таблица с метода на линейно изследване! Искаме да уточним няколко неща: първо ще дефинираме нашите необработени данни с двойката ключ-стойност, след което ще опишем подробно хеш функцията. След това ще създадем три основни метода за търсене в хеш-таблицата, вмъкване на нови записи и изтриването им.

Нека започнем, като направимструктурас двойката ключ-стойност. Ще направим това, като следваме примера с библиотеката от по-рано. (Това е написано на C. Кодът е цитиран от TutorialsPoint). Нека направим стойностите, свързани с всеки идентификатор на книга, серийния код на книгата.

struct BookInfo {
   int ID
   int SerialCode;
};

Добре! Нека да преминем към самата хеш функция.

int hashCode(int ID){
   return ID % 10;
}

Числото 10 ще се промени в зависимост от размера на вашия оригинален набор от данни. Тъй като просто ще следваме предишния пример, ние използваме key mod 10 като наша хеш функция.

Сега нека приложим метод за търсене. Искаме да получим хеша на идентификатора на книгата, която търсим, за да можем да получим съответния й индекс в масива. След това ще потърсим в масива съответния индекс и ще сравним стойностите в този слот на масива. Ако съвпада, бинго! Ако не стане, тогава според метода на линейно изследване ние просто ще продължим да се ровим из масива, докато намерим съвпадение.

struct BookInfo *search(int ID) {
   //here we're getting the hash of the ID for the book we want   
   int hashedIndex = hashCode(ID);
	
   //walk through array until you find an empty slot
   while(hashArray[hashedIndex] != NULL) {
      //seeing if the value corresponds and returning value if yes
      if(hashArray[hashedIndex]->ID == ID)
         return hashArray[hashedIndex];
			
      //move towards the next slot in the array if not
      ++hashIndex;
		
      //wrap around the hash table
      hashedIndex %= 10;
   }

   return NULL;        
}

След това ще приложим метод за вмъкване! Това ще ни позволи да добавяме нови книги към нашата мини библиотека. Ще започнем с изчисляване на хеширания индекс на ID на новата книга. След това ще проверим дали вече има данни в този слот на масива; ако все още е празен, тогава просто ще вмъкнем новата книга в този слот. Ако е заето, тогава ще продължим нашия метод за линейно сондиране през масива, за да намерим следващия свободен слот.

void insert(int ID,int SerialCode) {
   struct BookInfo *book = (struct BookInfo*) malloc(sizeof(struct BookInfo));
   book->SerialCode = SerialCode;  
   book->ID = ID;     

   //getting the hash of the new book's ID
   int hashedIndex = hashCode(ID);

   //moving through array until we find an empty cell
   while(hashArray[hashedIndex] != NULL && hashArray[hashedIndex]->ID != -1) {
      //going to the next cell
      ++hashedIndex;
		
      //wrapping around the hash table
      hashedIndex %= 10;
   }
	
   hashArray[hashedIndex] = book;        
}

И накрая, ще приложим и метод за изтриване. За да изтрием елемент от нашата хеш таблица, всъщност искаме да изчислим хеширания индекс на идентификатора на книгата, който искаме да премахнем, да го потърсим в масива (и с метода на линейно изследване, ако е необходимо) и след това да го заменим с фиктивен елемент, за да сме сигурни, че нашата хеш таблица ще продължи да функционира правилно след изтриването.

struct BookInfo* delete(struct BookInfo* book) {
   int ID = book->ID;

   //getting the hash of the book we want to delete
   int hashedIndex = hashCode(ID);

   //moving through the array until we find an empty slot
   while(hashArray[hashedIndex] != NULL) {
	
      if(hashArray[hashedIndex]->ID == ID) {
         struct BookInfo* temp = hashArray[hashedIndex]; 
			
         //placing a dummy item in deleted slot
         hashArray[hashedIndex] = dummyBook; 
         return temp;
      } 
		
      //going to the next cell
      ++hashedIndex;
		
      //wrapping around the hash table
      hashIndex %= 10;
   }  
	
   return NULL;        
}

Сега сме почти завършени!

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

Благодарим ви, че прочетохте! Ако сте намерили това за полезно, ето някои следващи стъпки, които можете да предприемете:

  1. Изпратете няколко ръкопляскания по моя път!
  2. Следвайте ме в Medium и свържете се с мен в LinkedIn, за да бъдете актуализирани, когато излезе следващата статия от тази поредица!
  3. Вземете още малко практика, като решите някои проблеми с хеш-таблици!
  4. Вижте предишната статия от тази поредица за стекове и опашки!