Хеш-таблица. Речник

Вече познаваме задачата за търсене на обект в множество от n обекта. С последователно търсене тя се решава със сложност O(n). Ако сортираме елементите, с двоично търсене ускоряваме до O(log n). Но това ли е най-добрият алгоритъм?

Оказва се — не. С правилната идея търсенето може да стане за константно време: скорост, която изобщо не зависи от броя на елементите. Идеята се нарича хеширане.

Дадено е множество от n обекта, всеки идентифициран с уникален ключ — който може и да не е число: име, ЕГН, регистрационен номер на автомобил. Разполагаме с m единици памет, номерирани 0, 1, …, m−1. Номерът на единица памет наричаме адрес (или индекс).

Търсим функция H, която на всеки ключ съпоставя адрес. Такава задача наричаме изчисляване на адрес или просто адресиране:

• За да съхраним обект с ключ K — пресмятаме H(K) и го записваме на този адрес.
• За да проверим дали обект с ключ K е в паметта — отново пресмятаме H(K) и поглеждаме там.

Популярната техника за построяване на подходящи адресиращи функции се нарича хеширане (от англ. hash — каша, бъркотия). Функциите, построени с нея, наричаме хеш-функции, а паметта, достъпвана чрез тях — хеш-таблица.

Прост пример, при който n = m: ключовете са главните букви на кирилицата, а хеш-таблицата има по една клетка за всяка буква. Хеш-функцията съпоставя на всяка буква поредния ѝ номер, започвайки от 0:

int H(char c) { return c - 'А'; }

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

static char[] HashTable;

void Insert(char c) { HashTable[H(c)] = c; }
void Delete(char c) { HashTable[H(c)] = '*'; }
bool Search(char c)
{   if (HashTable[H(c)] == '*') return false;
    else return true;
}

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

int H(string s)
{   return ((s[0]-'А')*900 + (s[1]-'А')*30 + (s[2]-'А')) % 30; }

int H(string s)
{   return ((s[0]-'А')*900 + (s[s.Length/2]-'А')*30
           + (s[s.Length-1]-'А')) % 30; }

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

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

void Insert(string s)
{   int hnew, hold; string sold;
    hnew = H(s);
    if (HashTable[hnew] == "*")
    {   HashTable[hnew] = s; return; }
    hold = H(HashTable[hnew]);
    if (hold != hnew)              // натрапник с друг хеш
    {   sold = HashTable[hnew];
        HashTable[hnew] = s;       // новият влиза на мястото си
        s = sold;                  // а натрапникът търси ново място
    }
    int i = (hnew + 1) % m;
    while (HashTable[i] != "*") i = (i + 1) % m;
    HashTable[i] = s;
}

C# има вграден механизъм за хеширане на низове — класът HashAlgorithm от пространството System.Security.Cryptography. Той обаче не е предназначен за хеш-таблици: хеширащите му методи връщат низ. Класът служи за криптографски алгоритми, използвани за защита на данните от неразрешен достъп.

using (SHA256 sha256H = SHA256.Create())
{   string hash = GetHash(sha256H, s);
    // други действия в това пространство
}

Хеш-таблиците не са единственото приложение на хеширането. Със задачата за търсене на образец в текст се запознахме при низовете — наивният алгоритъм има сложност O(n·m). Алгоритъмът на Рабин–Карп използва хеширане:

• Хешираме образеца (с дължина n).
• Разглеждаме последователно поднизовете на текста с дължина n.
• Ако хешът на подниза е различен от този на образеца — преминаваме нататък без сравнение.
• Ако хешовете съвпадат — сравняваме двата низа символ по символ (за да се предпазим от колизия). При равенство — намерили сме срещане.

Хеш-функцията гледа буквите като цифри на бройна система с основа 26 (за малки латински букви), пресметната по правилото на Хорнер:

const long mod = 1000007;

static long H(string s)
{   long result = 0;
    for (int i = 0; i < s.Length; i++)
    {   result = (26 * result + s[i] - 'a') % mod; }
    return result;
}

Колекцията Dictionary<TKey, TValue> вече я познаваме от урока за колекции — елементите ѝ са двойки ключ–стойност, а ключовете трябва да са уникални. Сега знаем и тайната ѝ: свръхбързото търсене за константно време се осъществява именно с хеширане.

Пример от учебника — речник на ключовите думи на C# с обяснения:

Dictionary<string, string> SharpWords
    = new Dictionary<string, string>();
SharpWords.Add("int", "декларира променлива от тип int");
SharpWords.Add("string", "декларира променлива от тип string");
SharpWords.Add("for", "оператор за цикъл");
SharpWords.Add("while", "оператор за цикъл с предусловие");
SharpWords.Add("break", "прекъсва изпълнението на цикъл");

Console.WriteLine(SharpWords.Count);     // 5
Console.WriteLine(SharpWords["for"]);    // оператор за цикъл
SharpWords["for"] = "оператор за постъпков цикъл";   // промяна
SharpWords.Remove("string");             // премахване, връща bool
Console.WriteLine(SharpWords.Count);     // 4

foreach (KeyValuePair<string, string> pairKV in SharpWords)
{   Console.WriteLine("Key = {0}, Value = {1}",
        pairKV.Key, pairKV.Value);
}

• Достъпът до стойностите е като индексиране на масив, но ролята на индекс играе ключът: SharpWords["for"].
• Понеже ключовете не са индекси, обхождането става с foreach през класа KeyValuePair.
• Remove(ключ) проверява за наличие, изтрива и връща true; иначе връща false.

• Адресиране: функция H превръща ключа директно в адрес — търсене за константно време, независимо от броя на елементите.
• Хеш-функция трябва да се смята бързо; свободните адреси се отбелязват със специален не-ключ (напр. '*').
• Колизия = различни ключове с еднаква хеш-стойност. Разрешава се с по-добра хеш-функция или с линейно пробване (първия свободен адрес, циклично).
• Рабин–Карп: търсене на образец чрез сравняване на хешове; при съвпадение — проверка символ по символ заради колизии.
• Dictionary<K, V> е хеш-таблица: O(1) търсене; SortedList е сортиран: O(log n), но с подреден обход.