Phenquestions
Да приемем, че сте собственик на голям магазин за провизии в окръга, където живеете. Да приемем, че живеете на голяма територия, която не е търговска зона. Не сте единственият с магазин за провизии в района; имате няколко конкуренти. И тогава ви хрумва, че трябва да запишете телефонните номера на клиентите си в тетрадка. Разбира се, тетрадката е малка и не можете да запишете всички телефонни номера за всичките си клиенти.
Затова решавате да записвате само телефонните номера на редовните си клиенти. И така, имате таблица с две колони. В колоната вляво има имена на клиенти, а в колоната вдясно - съответните телефонни номера. По този начин има картографиране между имената на клиентите и телефонните номера. Дясната колона на таблицата може да се разглежда като основна хеш таблица. Имената на клиентите вече се наричат ключове, а телефонните номера се наричат стойности. Имайте предвид, че когато клиент премине към трансфер, ще трябва да анулирате реда му, като позволите реда да бъде празен или да бъде заменен с този на нов редовен клиент. Също така имайте предвид, че с течение на времето броят на редовните клиенти може да се увеличи или намали и така масата да нараства или да се свива.
Като друг пример за картографиране, приемете, че в окръг има клуб на фермери. Разбира се, не всички фермери ще бъдат членове на клуба. Някои членове на клуба няма да бъдат редовни членове (присъстващи и с принос). Барът може да реши да запише имената на членовете и техния избор на напитка. Той разработва таблица от две колони. В лявата колона той пише имената на членовете на клуба. В дясната колона той записва съответния избор на напитка.
Тук има проблем: в дясната колона има дубликати. Тоест едно и също име на напитка се среща повече от веднъж. С други думи, различните членове пият една и съща сладка напитка или една и съща алкохолна напитка, докато други членове пият различна сладка или алкохолна напитка. Човекът с барове решава да реши този проблем, като вмъкне тясна колона между двете колони. В тази средна колона, започвайки отгоре, той номерира редовете, започващи от нула (т.е.д. 0, 1, 2, 3, 4 и т.н.), надолу, по един индекс на ред. С това проблемът му е решен, тъй като името на члена сега се преобразува в индекс, а не в името на напитка. И така, тъй като напитката се идентифицира с индекс, името на клиента се преобразува в съответния индекс.
Само колоната със стойности (напитки) формира основната хеш таблица. В модифицираната таблица колоната с индекси и свързаните с тях стойности (със или без дубликати) образуват нормална хеш таблица - пълната дефиниция на хеш таблица е дадена по-долу. Ключовете (първа колона) не са непременно част от хеш таблицата.
Като друг пример отново да разгледаме мрежов сървър, където потребител от своя клиентски компютър може да добави някаква информация, да изтрие някаква информация или да промени някои. Има много потребители на сървъра. Всяко потребителско име отговаря на парола, съхранена в сървъра. Тези, които поддържат сървъра, могат да виждат потребителските имена и съответната парола и така да могат да повредят работата на потребителите.
Така собственикът на сървъра решава да създаде функция, която криптира парола, преди да бъде съхранена. Потребителят влиза в сървъра с нормалната си разбирана парола. Сега обаче всяка парола се съхранява в криптирана форма. Ако някой види шифрована парола и се опита да влезе с нея, това няма да работи, защото влизането в системата получава разбирана парола от сървъра, а не криптирана парола.
В този случай разбраната парола е ключът, а кодираната парола е стойността. Ако шифрованата парола е в колона с криптирани пароли, тогава тази колона е основна хеш таблица. Ако тази колона е предшествана от друга колона с индекси, започващи от нула, така че всяка шифрована парола е свързана с индекс, тогава и колоната с индекси, и кодираната колона за парола образуват нормална хеш таблица. Ключовете не са задължително част от хеш таблицата.
В този случай имайте предвид, че всеки ключ, който е разбирана парола, съответства на потребителско име. И така, има потребителско име, което съответства на ключ, който е съотнесен към индекс, който е свързан със стойност, която е криптиран ключ.
Дефиницията на хеш функция, пълната дефиниция на хеш таблица, значението на масив и други подробности са дадени по-долу. Трябва да имате познания за указатели (препратки) и свързани списъци, за да оцените останалата част от този урок.
Значение на хеш функцията и хеш таблицата
Масив
Масивът е набор от последователни местоположения в паметта. Всички места са с еднакъв размер. Стойността в първото местоположение е достъпна с индекса 0; стойността във второто местоположение е достъпна с индекса 1; третата стойност е достъпна с индекса 2; четвърти с индекс, 3; и така нататък. Масивът обикновено не може да се увеличи или намали. За да се промени размерът (дължината) на масив, трябва да се създаде нов масив и да се копират съответните стойности в новия масив. Стойностите на масив винаги са от един и същи тип.
Хеш функция
В софтуера хеш функцията е функция, която взема ключ и създава съответния индекс за клетка на масив. Масивът е с фиксиран размер (фиксирана дължина). Броят на ключовете е с произволен размер, обикновено по-голям от размера на масива. Индексът, получен в резултат на хеш функцията, се нарича хеш стойност или обобщение или хеш код или просто хеш.
Хеш таблица
Хеш таблицата е масив със стойности, към чиито индекси се съпоставят ключовете. Ключовете косвено се съпоставят със стойностите. Всъщност се казва, че ключовете са картографирани към стойностите, тъй като всеки индекс е свързан със стойност (със или без дубликати). Функцията, която прави картографиране обаче (i.д. хеширане) отнася ключове към индексите на масива, а не към стойностите, тъй като в стойностите може да има дубликати. Следващата диаграма илюстрира хеш таблица за имената на хората и техните телефонни номера. Клетките на масива (слотовете) се наричат сегменти.
Забележете, че някои кофи са празни. Хеш таблицата не трябва непременно да има стойности във всичките си групи. Стойностите в групите не трябва непременно да са във възходящ ред. Индексите, с които са свързани обаче, са във възходящ ред. Стрелките показват картографирането. Забележете, че ключовете не са в масив. Те не трябва да бъдат в каквато и да е структура. Хеш функцията взема всеки ключ и хешира индекс за масив. Ако в кофата няма стойност, свързана с хеширания индекс, може да се постави нова стойност в тази група. Логическата връзка е между ключа и индекса, а не между ключа и стойността, свързана с индекса.
Стойностите на масив, като тези на тази хеш таблица, винаги са от един и същи тип данни. Хеш таблица (кофи) може да свързва ключове към стойностите на различни типове данни. В този случай стойностите на масива са всички указатели, сочещи към различни типове стойности.
Хеш таблицата е масив с хеш функция. Функцията взема ключ и хешира съответния индекс и по този начин свързва ключове към стойности в масива. Не е задължително ключовете да са част от хеш таблицата.
Защо масив, а не свързан списък за хеш таблица
Масивът за хеш таблица може да бъде заменен от свързана структура от данни на списъка, но би имало проблем. Първият елемент на свързан списък е естествено с индекс 0; вторият елемент естествено е с индекс 1; третият естествено е с индекс 2; и така нататък. Проблемът със свързания списък е, че за да се извлече стойност, списъкът трябва да се прегледа и това отнема време. Достъпът до стойност в масив става чрез произволен достъп. След като индексът е известен, стойността се получава без итерация; този достъп е по-бърз.
Сблъсък
Хеш функцията взема ключ и хешира съответния индекс, за да прочете асоциираната стойност или да вмъкне нова стойност. Ако целта е да се прочете стойност, засега няма проблем (няма проблем). Ако обаче целта е да се вмъкне стойност, хешираният индекс може вече да има свързана стойност и това е сблъсък; новата стойност не може да бъде поставена там, където вече има стойност. Има начини за разрешаване на сблъсък - вижте по-долу.
Защо се случва сблъсък
В примера за магазин за доставки по-горе имената на клиентите са ключовете, а имената на напитките са стойностите. Забележете, че клиентите са твърде много, докато масивът има ограничен размер и не може да вземе всички клиенти. Така че в масива се съхраняват само напитките на редовни клиенти. Сблъсъкът ще се случи, когато нередовен клиент стане редовен. Клиентите на магазина формират голям набор, докато броят на кофите за клиентите в масива е ограничен.
При хеш таблиците се записват стойностите за ключовете, които са много вероятни. Когато ключ, който не е вероятно, стане вероятно, вероятно ще има сблъсък. Всъщност сблъсъкът винаги се случва с хеш таблици.
Основи за разрешаване на сблъсъци
Два подхода за разрешаване на сблъсъка се наричат разделно верижно и отворено адресиране. На теория ключовете не трябва да са в структурата на данните или не трябва да са част от хеш таблицата. И двата подхода изискват ключовата колона да предшества хеш таблицата и да стане част от цялостната структура. Вместо ключовете да са в колоната ключове, указателите към ключовете може да са в колоната ключове.
Практичната хеш таблица включва колона с ключове, но тази колона с ключове не е официално част от хеш таблицата.
Всеки подход за резолюция може да има празни групи, не е задължително в края на масива.
Отделно верижно обвързване
В отделни вериги, когато възникне сблъсък, новата стойност се добавя вдясно (не над или отдолу) на сблъсканата стойност. Така че две или три стойности в крайна сметка имат един и същ индекс. Рядко повече от три трябва да имат един и същ индекс.
Може ли повече от една стойност наистина да имат един и същ индекс в масив? - Не. Така че в много случаи първата стойност за индекса е указател към свързана структура от данни на списъка, която съдържа една, две или три сблъскани стойности. Следващата диаграма е пример за хеш таблица за отделна верига на клиенти и техните телефонни номера:
Празните кофи са маркирани с буквата x. Останалите слотове имат указатели към свързани списъци. Всеки елемент от свързания списък има две полета с данни: едното за името на клиента и другото за телефонния номер. Възниква конфликт за ключовете: Питър Джоунс и Сузан Лий. Съответните стойности се състоят от два елемента от един свързан списък.
За конфликтни ключове критерият за вмъкване на стойност е същият критерий, използван за намиране (и четене) на стойността.
Отворете Адресиране
При отворено адресиране всички стойности се съхраняват в масива на сегмента. Когато възникне конфликт, новата стойност се вмъква в празна кофа нова, съответната стойност за конфликта, следвайки някакъв критерий. Критерият, използван за вмъкване на стойност при конфликт, е същият критерий, използван за намиране (търсене и четене) на стойността.
Следващата диаграма илюстрира разрешаване на конфликти с отворено адресиране:
Функцията хеш взема ключа, Питър Джоунс и хешира индекса 152, и съхранява телефонния си номер в свързаната кофа. След известно време хеш функцията хешира същия индекс, 152 от ключа, Сузан Лий, сблъсквайки се с индекса за Питър Джоунс. За да се реши това, стойността за Сюзан Лий се съхранява в кофата на следващия индекс 153, който беше празен. Хеш функцията хешира индекса, 153 за ключа, Робин Худ, но този индекс вече е използван за разрешаване на конфликта за предишен ключ. Така стойността за Робин Худ се поставя в следващата празна кофа, която е тази на индекс 154.
Методи за разрешаване на конфликти за отделно верижно и открито адресиране
Отделното верижно обвързване има своите методи за разрешаване на конфликти, а откритото адресиране също има свои собствени методи за разрешаване на конфликти.
Методи за разрешаване на отделни верижни конфликти
Методите за отделни верижни хеш таблици са обяснени накратко сега:
Отделно верижно обвързване със свързани списъци
Този метод е както е обяснено по-горе. Всеки елемент от свързания списък обаче не трябва непременно да има ключовото поле (напр.ж. поле за име на клиента по-горе).
Отделно верижно свързване с главни клетки на списъка
При този метод първият елемент от свързания списък се съхранява в група от масива. Това е възможно, ако типът данни за масива е елементът на свързания списък.
Отделно верижно свързване с други структури
Всякаква друга структура от данни, като самобалансиращо се двоично дърво за търсене, която поддържа необходимите операции, може да се използва вместо свързания списък - вижте по-късно.
Методи за разрешаване на конфликти при открито адресиране
Метод за разрешаване на конфликт при отворено адресиране се нарича сонда последователност. Три добре известни последователности на сонди са обяснени накратко сега:
Линейно сондиране
При линейно сондиране, когато възникне конфликт, се търси най-близката празна кофа под кофата в конфликт. Също така, при линейно сондиране, както ключът, така и неговата стойност се съхраняват в една и съща група.
Квадратично сондиране
Да приемем, че конфликтът възниква при индекс H. Следващият празен слот (сегмент) с индекс H + 12 се използва; ако това вече е заето, следващото празно при H + 22 се използва, ако това вече е заето, тогава следващото празно при H + 32 се използва и т.н. Има варианти на това.
Двойно хеширане
При двойно хеширане има две хеш функции. Първият изчислява (хешира) индекса. Ако възникне конфликт, вторият използва същия ключ, за да определи колко надолу трябва да се вмъкне стойността. Има още нещо за това - вижте по-късно.
Перфектна хеш функция
Перфектната хеш функция е хеш функция, която не може да доведе до сблъсък. Това може да се случи, когато наборът от ключове е относително малък и всеки ключ се преобразува в определено цяло число в хеш таблицата.
В ASCII набор от символи, главни букви могат да се преобразуват в съответните им малки букви, като се използва хеш функция. Буквите са представени в паметта на компютъра като числа. В ASCII набор от символи A е 65, B е 66, C е 67 и т.н. и a е 97, b е 98, c е 99 и т.н. За да картографирате от А в а, добавете 32 до 65; за картографиране от B към b, добавете 32 до 66; за картографиране от C на c, добавете 32 до 67; и така нататък. Тук главните букви са ключовете, а малките букви са стойностите. Хеш таблицата за това може да бъде масив, чиито стойности са свързаните индекси. Не забравяйте, че кофите от масива могат да бъдат празни. Така че кофите в масива от 64 до 0 могат да бъдат празни. Хеш функцията просто добавя 32 към големия кодов номер, за да получи индекса, а оттам и малката буква. Такава функция е перфектна хеш функция.
Хеширане от целочислени до целочислени индекси
Има различни методи за хеширане на цяло число. Един от тях се нарича метод на разделяне по модул (функция).
Функцията за хеширане на Modulo Division
Функция в компютърния софтуер не е математическа функция. В изчисленията (софтуер) функцията се състои от набор от изрази, предшествани от аргументи. За функцията за разделяне по модул ключовете са цели числа и се преобразуват в индекси на масива от сегменти. Наборът от ключове е голям, така че само ключовете, които е много вероятно да се появят в дейността, ще бъдат картографирани. Така че възникват сблъсъци, когато трябва да се картографират малко вероятни ключове.
В изявлението,
20/6 = 3R2
20 е дивидентът, 6 е делителят, а 3 остатък 2 е коефициентът. Остатъкът 2 се нарича още по модул. Забележка: възможно е да има модул 0.
За това хеширане размерът на таблицата обикновено е степен 2, напр.ж. 64 = 26 или 256 = 28, и т.н. Делителят за тази хешираща функция е просто число, близко до размера на масива. Тази функция разделя ключа на делителя и връща модула. Модулът е индексът на масива от групи. Свързаната стойност в групата е стойност по ваш избор (стойност за ключа).
Хеширане на ключове с променлива дължина
Тук ключовете на набора ключове са текстове с различна дължина. Различни цели числа могат да се съхраняват в паметта, като се използва един и същ брой байтове (размерът на английски символ е байт). Когато различните ключове са с различен размер на байта, се казва, че те са с променлива дължина. Един от методите за хеширане на променливи дължини се нарича Radix Conversion Hashing.
Хеширане на преобразуване на Radix
В низ всеки знак в компютъра е число. При този метод,
Хеш код (индекс) = x0аk − 1+х1аk − 2+... + xk − 2а1+хk − 1а0
Където (x0, x1,…, xk − 1) са символите на входния низ и a е radix, e.ж. 29 (виж по-късно). k е броят на символите в низа. Има още нещо за това - вижте по-късно.
Ключове и ценности
В двойка ключ / стойност стойността може да не е непременно число или текст. Това може да бъде и запис. Записът е списък, написан хоризонтално. В двойка ключ / стойност всеки ключ може действително да се отнася до друг текст или номер или запис.
Асоциативен масив
Списъкът е структура от данни, където елементите на списъка са свързани и има набор от операции, които действат в списъка. Всеки елемент от списъка може да се състои от двойка елементи. Общата хеш таблица с нейните ключове може да се разглежда като структура на данните, но тя е по-скоро система, отколкото структура на данни. Ключовете и съответните им стойности не са много зависими един от друг. Те не са много свързани помежду си.
От друга страна, асоциативният масив е подобно нещо, но ключовете и техните стойности са много зависими един от друг; те са много свързани помежду си. Например можете да имате асоциативен масив от плодове и техните цветове. Всеки плод естествено има своя цвят. Името на плода е ключът; цветът е стойността. По време на вмъкването всеки ключ се вмъква със своята стойност. При изтриване всеки ключ се изтрива със стойността си.
Асоциативен масив е структура от данни на хеш таблица, съставена от двойки ключ / стойност, където няма дубликат за ключовете. Стойностите могат да имат дубликати. В тази ситуация ключовете са част от структурата. Тоест, ключовете трябва да се съхраняват, докато с общата таблица на ключовете не трябва да се съхраняват ключовете. Проблемът с дублираните стойности е естествено решен от индексите на масива от групи. Не бъркайте между дублирани стойности и сблъсък при индекс.
Тъй като асоциативен масив е структура от данни, is има поне следните операции:
Асоциативни операции с масиви
вмъкване или добавяне
Това вмъква нова двойка ключ / стойност в колекцията, съпоставяйки ключа с неговата стойност.
преназначи
Тази операция замества стойността на определен ключ с нова стойност.
изтриване или премахване
Това премахва ключ плюс съответната му стойност.
погледни нагоре
Тази операция търси стойността на определен ключ и връща стойността (без да я премахва).
Заключение
Структурата на данните на хеш таблицата се състои от масив и функция. Функцията се нарича хеш функция. Функцията преобразува ключовете в стойности в масива чрез индексите на масива. Ключовете не трябва непременно да са част от структурата на данните. Наборът от ключове обикновено е по-голям от съхранените стойности. Когато възникне сблъсък, той се разрешава или от подхода за отделно верижно обхождане, или от отворения подход за адресиране. Асоциативен масив е специален случай на структурата на данните на хеш таблицата.
