Хеш-таблица

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене
A small phone book as a hash table

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

Определение[редактиране | edit source]

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

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

  • Void put (key, data); - включване на елемент с ключ key и данни data в хеш таблицата
  • Data get (key); - търсене и извличане на данните от елемент с ключ key от хеш таблицата
  • Void remove (key); - изключване на елемент с ключ key от хеш таблицата

Всеки елемент на хеш-таблицата се характеризира с две полета: ключ key и данни data. Ключът представлява уникален идентификатор: ако два елемента имат един и същ ключ се считат идентични.

Хеш - функции[редактиране | edit source]

Хеш-функция (или хеш алгоритъм) е метод, който преобразува данни в число, подходящо за манипулиране от компютъра. Тези функции осигуряват начин за създаване на малки дигитални „отпечатъци” от всякакъв тип данни. Тези „отпечатъци” често са наричани хеш-стойности. Означава се с: h (k), където k е ключ.

Фундаментално свойство на всички хеш-функции е, че ако две хеш-стойности (спрямо една хеш функция) са различни, то и въведените данни се различават по някакъв начин. Tова свойство е следствие от определеността на хеш-функциите. От друга страна, ако две хеш-стойности са еднакви, това не означава, че въведените данни са еднакви.

Изискванията при избор на подходяща хеш-функция са:

  • Да се изчислява бързо, лесно и с малък брой операции;
  • Изчислените с нея хеш-адреси да са такива, че да има минимум колизии.

Конкретната хеш-функция зависи от вида на ключовете (данните). Когато те са цяло число, тя има вида:

(1) h (k) = k mod n, (остатък от делението на k с n, n- размер на таблицата.)

По този начин хеш-адреса винаги е в границите на индексите на таблицата.

Когато ключът не е цяло число, а е низ, хеш-функцията има вида:

(2) h (k) = f(k) mod n, f(k)- преобразува ключа в цяло число.

Тогава, когато h (k1) = h (k2) настъпва колизия.Идеална хеш-функция (без колизии) няма или поне досега няма обосновано твърдение (с ясно математическо доказателство), че някоя хеш-функция не подлежи на колизия. Два блока с информация са в колизия, ако те се различават по съдържание, но имат един и същи хеш. Не е задължително блоковете да са два - може да са и повече (повече колизии). Една хеш-функция е под заплаха, ако се намери начин за контролирано намиране на колизия (т.е. да се намери алгоритъм, който е повторим и по зададен изходен блок от информация и неговия хеш, той да позволява да се изчисли друг блок информация, който има същия хеш). За една хеш-функция се казва, че е разбита, ако е намерен алгоритъм за редукция на броя търсения.Колизиите се разрешават чрез отворено и затворено хеширане.

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

Затворено хеширане - При затвореното хеширане се използва само едномерен масив и индекс:

h (k) = [h(k) + f(i)] % n, където: h(k)- оригинална хеш-функция; i- пореден номер на опита (индексиране); f (i)- функция за разрешаване на колизии, като винаги f (0) = 0.

Класически хеш - функции[редактиране | edit source]

Удачния избор на хеш-функция се определя от две неща:

- Хеш- функцията да не отнема много изчислително време
- Да разпределя елементите относително равномерно в различните хеш-адреси

Най- често срещаните в практиката хеш-функции (върху целочислен ключ ):

· Остатък при деление с размера на таблицата

Ключът к се разделя целочислено на n и се взема остатъка от делението. При този подход не е удачно за капацитет на хеш-таблицата да се избира число n, степен на 2. Ако n=2p , то хеш-кодът на даден ключ k ще бъдат младшите p бита на k. Например n=24, k=173.

173=10101101(2) 173 % 16=13=1101(2)

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

· Мултипликативно хеширане

При мултипликативното хеширане избираме реална константа a между 0 и 1 и образуваме функцията:

hash( key ) = trunc( n * ( ( key * a ) - trunc( key * a ) ) )

Т.е. взимаме дробната част от умножението на ключа с константата и я умножаваме по размера на таблицата. Често за стойност на константата се избира

а = ( sqrt ( 5 ) - 1 ) / 2   ,

т.нар. златно сечение

Хеш-функции върху части от ключа[редактиране | edit source]

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

При тази схема от ключа се извличат само цифри, намиращи се на определени позиции(например първа, трета и пета цифра от числото). Така за ключовете 123569, 425435, 676576 ще получим хеш- адреси съответно 136, 453, 667. Очевидно в този случай n трябва да бъде 1000. този метод има добра успеваемост, когато числата не съдържат много повтарящи сe цифри.

· Сгъване

Този метод се прилага най-често, когато ключовете са много големи числа. Методът се основава на разделяне на ключа на части и извършване на някакви аритметични действия върху получените числа(например сумата от частите да определи хеш-адреса.

· Повдигане на средата в квадрат

При тази схема средните p цифри на ключа се повдигат в квадрат. Например за ключа 1256557134280980 средните три цифри са 134. 1342=17956. Ако резултатът надхвърли n се премахват първите няколко значещи цифри. Ако n=10001, то от 17956 се премахва първата цифра и получения хеш-адрес е 7956.

Хеш функции върху низове[редактиране | edit source]

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

hash( key )
{
  резултат = начална стойност
  за всеки символ c от key
    резултат = комбиниране( резултат, c )
    резултат = модифициране( резултат )
  резултат = допълнително_модифициране( резултат )
}

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

Справяне с колизии[редактиране | edit source]

Преди да започнем с обяснението на конкретни техники е важно да отбележим, че в литературата чисто терминологично са налице два вида разделение: хеширането бива отворено и затворено, а адресирането отворено и със списъци на препълванията (chaining). Това може да доведе до объркване, тъй като на отвореното адресиране съответства затвореното хеширане, а списъците с препълвания принадлежат към отвореното хеширане.

Определение: Колизия наричаме ситуация, при която два различни ключа връщат едно и също число за хеш-код.

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

Нареждане в списък(chaining)[редактиране | edit source]

Колизия решена с нареждане в списък

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

Отворена адресация (oppen addressing)[редактиране | edit source]

Колизия решена чрез отворена адрецация с линейно пробване (с интервал 1).

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

Линейно пробване (linear probing)[редактиране | edit source]

Използването на линейно пробване като метод за решаване на проблема с колизиите е неефективно и трябва да се избягва.

Този метод е един от най-лесните за имплементация. Представлява следният простичък код: (C#)

int newPosition = (oldPosition + i) % capacity;

където capacity е капацитетът на таблицата, oldPosition е позицията на която получаваме колизия, а i е номер на поредното пробване. Ако новополучената позиция е свободна, то мястото се използва, ако не пробваме отново като увеличаваме i с единица. Пробването може да е напред, както сме показали тук, или назад. Пробването назад става като вместо да прибавяме, вадим i от мястото, където е възникнала колизия.

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

Квадратично пробване (Quadratic probing)[редактиране | edit source]

Това е класически метод. Той се различава от линейното пробване по това, че използва квадратна функция на i (номер на поредното пробване) за намиране на следваща позиция (C#):

int newPosition = (oldPosition + c1*i + c2*i*i) % capacity;

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

От избора на константите зависи кои позиции ще пробваме. Например, ако изберем да са равни на 1, ще пробваме последователно oldPosition, oldPosition + 2, oldPosition + 6 и т.н. За таблица с капацитет от вида 2n е най-подходящо c1 и c2 да се изберат равни на 0,5.

Двойно хеширане (double hashing)[редактиране | edit source]

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

Квадратичното пробване е по-ефективно от линейното.

Хеширане в Java[редактиране | edit source]

  • метод hashCode на класа Object: public int hashCode()
  • ограничаване до конкретен размер на масив - например: h(k) = abs(k.hashCode())%N
  • хеш кодове за примитивни стойности:
- за стойности от числов тип с размер по-малък или равен на int : самата стойност или битовата последователност (при float) интерпретирана като стойност от тип int.
- за стойности от тип с размер (2 пъти) по-голям от int (long, double) - изключващо или на 2-те половини, интерпретирани като стойност от тип int.
  • хеш кодове за ключове, комбиниращи множество примитивни стойности или обекти: събиране с умножение на междинните суми по просто число (31). Например за масив от символи а :
int h = 0;
for(int i = 0; i < a.length; i++)
 {
   h = 31 * h + a[i];
 }

За масив от обекти a :

int h = 0;
for(int i = 0; i < a.length; i++)
{
  h = 31 * h + (a[i] != null ? a[i].hashCode() : 0);
}

Реализация[редактиране | edit source]

По-долу е дадена примерна реализация на основните операции върху хеш таблица с отворено хеширане (списък на препълванията) на C++. Използваме наготово функции за робота със списъци, за да не утежняваме кода с тяхната реализация.

void OpenHashTable::Put(HashTable::KeyType key, HashTable::DataType data)
{
        HashedKeyType i = HashFunction(key);
        list *l = listFind(mOpenTable[i], key);
   if (l)
        {
                l->data = data;
        }
        else
        {
                if (mOpenTable[i])
                        ++mCollisionsCount;
                listInsert(&mOpenTable[i], key, data);
        }
}
HashTable::DataType OpenHashTable::Get(HashTable::KeyType key)
{
        HashedKeyType i = HashFunction(key);
        list *l = listFind(mOpenTable[i], key);
        return l ? l->data : NOT_FOUND;
}
void OpenHashTable::Remove(HashTable::KeyType key)
{
        HashedKeyType i = HashFunction(key);
   if (mOpenTable[i])
                listDelete(&mOpenTable[i], key);
}

Външни препратки[редактиране | edit source]

Литература[редактиране | edit source]