Обяснена таблица на хеш: какво е и как да се приложи

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

Някои важни бележки за хеш таблиците:

  1. Стойностите не се съхраняват в сортиран ред.
  2. Вие разчитате на потенциални сблъсъци. Това обикновено се прави с техника, наречена верига. Chaining означава да се създаде свързан списък със стойности, чиито ключове съответстват на определен индекс.

Внедряване на хеш таблица

Основната идея зад хеширането е да се разпределят двойки ключ / стойност в масив от заместители или „кофи“ в хеш таблицата.

Хеш таблицата обикновено е масив от свързани списъци. Когато искате да вмъкнете двойка ключ / стойност, първо трябва да използвате хеш функцията, за да прикачите ключа към индекс в хеш таблицата. Даден ключ, хеш функцията може да предложи индекс, където стойността може да бъде намерена или съхранена:

index = f(key, array_size)

Това често се прави в две стъпки:

hash = hashfunc(key) index = hash % array_size

Използването на този метод hashе независимо от размера на хеш таблицата. hashсе намалява до индекс - число между 0, началото на масива и array_size - 1, края на масива - с помощта на оператора modulo (%).

Да разгледаме следния низ, S:

string S = “ababcd”

Трябва да преброите честотата на всички знаци в S. Най-лесният начин да направите това е да прегледате всички възможни знаци и да преброите честотата на всеки един по един.

Това работи, но е бавно - сложността във времето на такъв подход е O (26 * N), Nкато размерът на низа се Sумножава по 26 възможни символа от AZ.

void countFre(string S) { for(char c = ‘a’;c <= ‘z’;++c) { int frequency = 0; for(int i = 0;i < S.length();++i) if(S[i] == c) frequency++; cout << c << ‘ ‘ << frequency << endl; } }

Изход:

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

Нека да разгледаме решение, което използва хеширане.

Вземете масив и използвайте хеш функцията, за да хеширате 26-те възможни знака с индекси на масива. След това повторете Sи увеличете стойността на текущия символ на низа със съответния индекс за всеки символ.

Сложността на този подход за хеширане е O (N), където N е размерът на низа.

int Frequency[26]; int hashFunc(char c) { return (c - ‘a’); } void countFre(string S) { for(int i = 0;i < S.length();++i) { int index = hashFunc(S[i]); Frequency[index]++; } for(int i = 0;i < 26;++i) cout << (char)(i+’a’) << ‘ ‘ << Frequency[i] << endl; }

Изход

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

Хеш сблъсъци

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

Оковаване

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

Например, представете си, че ключът 152 съдържа стойността "Джон Смит". Ако стойността "Сандра Дий" се добави към същия ключ, "Сандра Дий" се добавя като друг елемент към ключ 152, непосредствено след "Джон Смит".

152: [["John Smith", "p01"]] ... 152: [["John Smith", "p01"] ["Sandra Dee", "p02"]]

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

Отворено адресиране

Отвореното адресиране означава, че след като дадена стойност се съпостави с ключ, който вече е зает, вие се придвижвате по клавишите на хеш таблицата, докато намерите такъв, който е празен. Например, ако „Джон Смит“ е преобразуван в 152, „Сандра Дий“ ще бъде преобразувана в следващия отворен индекс:

152: ["John Smith", "p01"] ... 152: ["John Smith", "p01"], 153: ["Sandra Dee", "p02"]

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