TechCodeview

Увод у хеширање у структури података:

Хеширање је популарна техника у рачунарству која укључује мапирање великих скупова података у вредности фиксне дужине. То је процес претварања скупа података променљиве величине у скуп података фиксне величине. Способност извођења ефикасних операција претраживања чини хеширање суштинским концептом у структурама података.

Шта је хеширање?

Алгоритам хеширања се користи за претварање улаза (као што је стринг или цео број) у излаз фиксне величине (који се назива хеш код или хеш вредност). Подаци се затим чувају и преузимају користећи ову хеш вредност као индекс у низу или хеш табели. Хеш функција мора бити детерминистичка, што гарантује да ће увек дати исти резултат за дати улаз.

Хеширање се обично користи за креирање јединственог идентификатора за део података, који се може користити за брзо тражење тих података у великом скупу података. На пример, веб прегледач може да користи хеширање за безбедно складиштење лозинки за веб локацију. Када корисник унесе своју лозинку, претраживач је конвертује у хеш вредност и упоређује је са сачуваном хеш вредношћу да би потврдио аутентичност корисника.

израз регресије у Јави

Шта је хеш кључ?

У контексту хеширања, хеш кључ (такође познат као хеш вредност или хеш код) је нумерички или алфанумерички приказ фиксне величине генерисан алгоритмом хеширања. Изводи се из улазних података, као што је текстуални низ или датотека, кроз процес познат као хеширање.

Хеширање укључује примену специфичне математичке функције на улазне податке, која производи јединствени хеш кључ који је типично фиксне дужине, без обзира на величину улаза. Добијени хеш кључ је у суштини дигитални отисак оригиналних података.

Хеш кључ има неколико сврха. Обично се користи за проверу интегритета података, јер ће чак и мала промена у улазним подацима произвести значајно другачији хеш кључ. Хеш кључеви се такође користе за ефикасно проналажење и складиштење података у хеш табелама или структурама података, јер омогућавају брзо тражење и операције поређења.

Како функционише хеширање?

Процес хеширања се може поделити у три корака:

• Улаз: Подаци који се хеширају се уносе у алгоритам хеширања.
• Хеш функција: Алгоритам хеширања узима улазне податке и примењује математичку функцију да генерише хеш вредност фиксне величине. Хеш функција треба да буде дизајнирана тако да различите улазне вредности производе различите хеш вредности, а мале промене на улазу дају велике промене у излазу.
• Излаз: Враћа се хеш вредност, која се користи као индекс за складиштење или преузимање података у структури података.

Алгоритми хеширања:

Постоје бројни алгоритми хеширања, од којих сваки има своје предности и недостатке. Најпопуларнији алгоритми укључују следеће:

• МД5: Алгоритам хеширања који се широко користи који производи 128-битну хеш вредност.
• СХА-1: Популарни алгоритам хеширања који производи 160-битну хеш вредност.
• СХА-256: Безбеднији алгоритам хеширања који производи 256-битну хеш вредност.

Хеш функција:

Хеш функција: Хеш функција је врста математичке операције која узима улаз (или кључ) и даје резултат фиксне величине познат као хеш код или хеш вредност. Хеш функција мора увек дати исти хеш код за исти улаз да би била детерминистичка. Поред тога, хеш функција треба да произведе јединствени хеш код за сваки улаз, који је познат као хеш својство.

ислеттер јава

Постоје различите врсте хеш функција, укључујући:

Метод дељења:

Овај метод подразумева дељење кључа величином табеле и узимање остатка као хеш вредности. На пример, ако је величина табеле 10, а кључ 23, хеш вредност би била 3 ​​(23 % 10 = 3).

Метод множења:

Овај метод укључује множење кључа константом и узимање разломка производа као хеш вредности. На пример, ако је кључ 23, а константа 0,618, хеш вредност би била 2 (спрат(10*(0,61823 - спрат(0,61823))) = спрат(2,236) = 2).

Универзално хеширање:

Овај метод укључује коришћење насумичне хеш функције из породице хеш функција. Ово осигурава да хеш функција није пристрасна према било ком одређеном улазу и да је отпорна на нападе.

Резолуција судара

Један од главних изазова у хеширању је руковање колизијама, до којих долази када две или више улазних вредности производе исту хеш вредност. Постоје различите технике које се користе за решавање колизија, укључујући:

• Уланчавање: У овој техници, сваки слот хеш табеле садржи повезану листу свих вредности које имају исту хеш вредност. Ова техника је једноставна и лака за имплементацију, али може довести до лоших перформанси када повезане листе постану предугачке.
• Отворено адресирање: У овој техници, када дође до колизије, алгоритам тражи празан слот у хеш табели испитивањем узастопних слотова док се не пронађе празан слот. Ова техника може бити ефикаснија од уланчавања када је фактор оптерећења низак, али може довести до груписања и лоших перформанси када је фактор оптерећења висок.
• Двоструко хеширање: Ово је варијација отвореног адресирања која користи другу хеш функцију да одреди следећи слот за испитивање када дође до колизије. Ова техника може помоћи да се смањи груписање и побољша перформансе.

Пример резолуције колизије

Наставимо са нашим примером хеш табеле величине 5. Желимо да ускладиштимо парове кључ/вредност 'Јохн: 123456' и 'Мари: 987654' у хеш табели. Оба кључа производе исти хеш код од 4, тако да долази до колизије.

Можемо користити уланчавање да решимо колизију. Креирамо повезану листу на индексу 4 и додајемо парове кључ/вредност на листу. Хаш табела сада изгледа овако:

0:

1:

помоћник комесара полиције

2:

3:

4: Јован: 123456 -> Марија: 987654

5:

Хеш табела:

Хеш табела је структура података која чува податке у низу. Типично, величина за низ је изабрана која је већа од броја елемената који могу да стане у хеш табелу. Кључ се мапира у индекс у низу помоћу функције хеш.

Хеш функција се користи за лоцирање индекса где елемент треба да се убаци у хеш табелу да би се додао нови елемент. Елемент се додаје том индексу ако не постоји колизија. Ако постоји колизија, метод резолуције колизије се користи за проналажење следећег слободног места у низу.

ури вс урл

Хеш функција се користи за лоцирање индекса у коме је елемент ускладиштен да би се он преузео из хеш табеле. Ако елемент није пронађен у том индексу, метода резолуције колизије се користи за тражење елемента у повезаној листи (ако се користи ланчано повезивање) или у следећем доступном слоту (ако се користи отворено адресирање).

Операције хеш табеле

Постоји неколико операција које се могу извршити на хеш табели, укључујући:

• Уметање: Уметање новог пара кључ/вредност у хеш табелу.
• Брисање: Уклањање пара кључ/вредност из хеш табеле.
• Претрага: Тражење пара кључ/вредност у хеш табели.

Креирање хеш табеле:

Хеширање се често користи за прављење хеш табела, које су структуре података које омогућавају брзо уметање, брисање и преузимање података. Један или више парова кључ/вредност може бити ускладиштено у сваком од низова кантица који чине хеш табелу.

Да бисмо креирали хеш табелу, прво морамо да дефинишемо хеш функцију која мапира сваки кључ у јединствени индекс у низу. Једноставна хеш функција може бити да узме збир АСЦИИ вредности знакова у кључу и користи остатак када се подели са величином низа. Међутим, ова хеш функција је неефикасна и може довести до колизија (два кључа који се мапирају у исти индекс).

Да бисмо избегли колизије, можемо да користимо напредније хеш функције које производе равномернију дистрибуцију хеш вредности у низу. Један популаран алгоритам је дјб2 хеш функција, која користи операције у битовима за генерисање хеш вредности:

басх подели стринг по делимитеру

 unsigned long hash(char* str) { unsigned long hash = 5381; int c; while (c = *str++) { hash = ((hash << 5) + hash) + c; } return hash; } 

Ова хеш функција узима стринг као улаз и враћа непотписану дугу целобројну хеш вредност. Функција иницијализује хеш вредност од 5381, а затим итерира преко сваког знака у стрингу, користећи битне операције за генерисање нове хеш вредности. Враћа се коначна хеш вредност.

Хеш табеле у Ц++

У Ц++, стандардна библиотека обезбеђује класу контејнера хеш табеле под називом унордеред_мап. Контејнер унордеред_мап је имплементиран помоћу хеш табеле и обезбеђује брз приступ паровима кључ/вредност. Контејнер унордеред_мап користи хеш функцију за израчунавање хеш кода кључева, а затим користи отворено адресирање за решавање колизија.

Да бисте користили контејнер унордеред_мап у Ц++-у, потребно је да укључите датотеку заглавља. Ево примера како да направите унордеред_мап контејнер у Ц++:

 #include #include int main() { // create an unordered_map container std::unordered_map my_map; // insert some key-value pairs into the map my_map['apple'] = 10; my_map['banana'] = 20; my_map['orange'] = 30; // print the value associated with the 'banana' key std::cout << my_map['banana'] << std::endl; return 0; } 

Објашњење:

• Овај програм демонстрира употребу контејнера унордеред_мап у Ц++, који је имплементиран помоћу хеш табеле и обезбеђује брз приступ паровима кључ-вредност.
• Прво, програм укључује потребне датотеке заглавља: ​​и.
• Затим, програм креира празан контејнер унордеред_мап под називом ми_мап, који има стринг кључеве и целобројне вредности. Ово се ради помоћу синтаксе стд::унордеред_мап ми_мап;
• Затим, програм убацује три пара кључ/вредност у ми_мап контејнер користећи оператор []: 'јабука' са вредношћу 10, 'банана' са вредношћу 20 и 'наранџаста' са вредношћу 30.
• Ово се ради помоћу синтаксе ми_мап['аппле'] = 10;, ми_мап['банана'] = 20; и ми_мап['оранге'] = 30; редом.
• Коначно, програм штампа вредност придружену кључу 'банана' користећи оператор [] и објекат стд::цоут.

Излаз програма:

Уметање података у хеш табелу

Да бисмо уметнули пар кључ-вредност у хеш табелу, прво морамо да унесемо индекс у низ за чување пара кључ-вредност. Ако се други кључ мапира на исти индекс, имамо колизију и морамо да се носимо са тим на одговарајући начин. Један уобичајени метод је коришћење уланчавања, где сваки сегмент у низу садржи повезану листу парова кључ-вредност који имају исту хеш вредност.

Ево примера како да убаците пар кључ/вредност у хеш табелу коришћењем уланчавања:

 typedef struct node { char* key; int value; struct node* next; } node; node* hash_table[100]; void insert(char* key, int value) { unsigned long hash_value = hash(key) % 100; node* new_node = (node*) malloc(sizeof(node)); new_node->key = key; new_node->value = value; new_node->next = NULL; if (hash_table[hash_value] == NULL) { hash_table[hash_value] = new_node; } else { node* curr_node = hash_table[hash_value]; while (curr_node->next != NULL) { curr_node = curr_node->next; } curr_node->next = new_node; } } 

Објашњење:

• Прво је дефинисана структура која се зове чвор, који представља један чвор у хеш табели.
• Сваки чвор има три члана: цхар* кључ за складиштење кључа, инт вредност за складиштење повезане вредности и показивач на други чвор који се позива поред да обрађује колизије у хеш табели користећи повезану листу.
• Низ показивача чворова под називом хасх_табле је декларисан са величином од 100. Овај низ ће се користити за чување елемената хеш табеле.
• Функција инсерт узима кључ цхар* и вредност инт као параметре.
• Почиње израчунавањем хеш вредности за дати кључ користећи хеш функцију, за коју се претпоставља да је дефинисана негде другде у програму.
• Хеш вредност се затим смањује да би се уклопила у величину низа хасх_табле помоћу оператора модула % 100.
• Нови чвор се креира коришћењем динамичке алокације меморије (маллоц(сизеоф(ноде))), а његовим члановима (кључ, вредност и следећи) се додељују дати кључ, вредност и НУЛЛ, респективно.
• Ако је одговарајући слот у низу хасх_табле празан (НУЛЛ), што указује да није дошло до колизије, нови чвор се директно додељује том слоту (хасх_табле[хасх_валуе] = нев_ноде).

Међутим, ако већ постоји чвор на том индексу у низу хасх_табле, функција треба да обради колизију. Он прелази преко повезане листе почевши од тренутног чвора (хасх_табле[хасх_валуе]) и креће се на следећи чвор док не дође до краја (цурр_ноде->нект != НУЛЛ). Када се дође до краја листе, нови чвор се додаје као следећи чвор (цурр_ноде->нект = нев_ноде).

Имплементација хеширања у Ц++:

Хајде да видимо имплементацију хеширања у Ц++ користећи отворено адресирање и линеарно испитивање за решавање колизија. Применићемо хеш табелу која чува целе бројеве.

 #include using namespace std; const int SIZE = 10; class HashTable { private: int arr[SIZE]; public: HashTable() { for (int i = 0; i <size; i++) { arr[i]="-1;" } int hashfunction(int key) return key % size; void insert(int index="hashFunction(key);" i="0;" while (arr[(index + i) size] !="-1" && arr[(index i++; if cout << 'element already exists in the hash table' endl; else remove(int deleted from return; not found display() for (int < (arr[i]="=" -1 || -2) continue; 'index ' ': }; main() hashtable ht; ht.insert(5); ht.insert(15); ht.insert(25); ht.insert(35); ht.insert(45); ht.display(); ht.remove(15); ht.remove(10); ht.insert(55); 0; pre> <p> <strong>Explanation:</strong> </p> <ul> <li>This program implements a hash table data structure using linear probing to handle collisions.</li> <li>A hash table is a data structure that stores data in key-value pairs, where the keys are hashed using a hash function to generate an index in an array. This allows for constant-time average-case complexity for inserting, searching, and deleting elements from the hash table.</li> <li>The HashTable class has a private integer array arr of size SIZE, which is initialized to -1 in the constructor. The hash function method takes an integer key and returns the hash value of the key, which is simply the remainder of the key when divided by SIZE.</li> <li>The insert method takes an integer key and uses the hash function to get the index where the key should be inserted.</li> <li>If the index is already occupied by another key, linear probing is used to find the next available index in the array. Linear probing checks the next index in the array until it finds an empty slot or the key itself.</li> <li>If the key is already in the hash table, the method displays a message saying that the element already exists. Otherwise, it inserts the key at the calculated index.</li> <li>The remove method takes an integer key and uses the hash function to get the index where the key is located.</li> <li>If the key is not in the calculated index, linear probing is used to search for the key in the next indices in the array. Once the key is found, it is deleted by setting its value to -2.</li> <li>If the key is not found in the hash table, the method displays a message saying that the element is not found.</li> <li>The display method simply iterates through the array and prints out all non-empty key-value pairs.</li> <li>In the main function, an instance of the HashTable class is created, and several integers are inserted into the hash table using the insert method.</li> <li>Then, the display method is called to show the contents of the hash table. The remove method is called twice, first to remove an element that exists in the hash table and then to remove an element that does not exist.</li> <li>The display method is called after each remove method call to show the updated contents of the hash table.</li> <li>Finally, another integer is inserted into the hash table, and the display method is called again to show the final contents of the hash table.</li> </ul> <p> <strong>Program Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/hashing-data-structure-3.webp" alt="Hashing in Data Structure"> <h2>Applications of Hashing</h2> <p>Hashing has many applications in computer science, including:</p> <ul> <li>Databases: Hashing is used to index and search large databases efficiently.</li> <li>Cryptography: Hash functions are used to generate message digests, which are used to verify the integrity of data and protect against tampering.</li> <li>Caching: Hash tables are used in caching systems to store frequently accessed data and improve performance.</li> <li>Spell checking: Hashing is used in spell checkers to quickly search for words in a dictionary.</li> <li>Network routing: Hashing is used in load balancing and routing algorithms to distribute network traffic across multiple servers.</li> </ul> <h2>Advantages of Hashing:</h2> <ul> <li>Fast Access: Hashing provides constant time access to data, making it faster than other data structures like linked lists and arrays.</li> <li>Efficient Search: Hashing allows for quick search operations, making it an ideal data structure for applications that require frequent search operations.</li> <li>Space-Efficient: Hashing can be more space-efficient than other data structures, as it only requires a fixed amount of memory to store the hash table.</li> </ul> <h2>Limitations of Hashing:</h2> <ul> <li>Hash Collisions: Hashing can produce the same hash value for different keys, leading to hash collisions. To handle collisions, we need to use collision resolution techniques like chaining or open addressing.</li> <li>Hash Function Quality: The quality of the hash function determines the efficiency of the hashing algorithm. A poor-quality hash function can lead to more collisions, reducing the performance of the hashing algorithm.</li> </ul> <h2>Conclusion:</h2> <p>In conclusion, hashing is a widely used technique in a data structure that provides efficient access to data. It involves mapping a large amount of data to a smaller hash table using a hash function, which reduces the amount of time needed to search for specific data elements. The hash function ensures that data is stored in a unique location within the hash table and allows for easy retrieval of data when needed.</p> <p>Hashing has several advantages over other data structure techniques, such as faster retrieval times, efficient use of memory, and reduced collisions due to the use of a good hash function. However, it also has some limitations, including the possibility of hash collisions and the need for a good hash function that can distribute data evenly across the hash table.</p> <p>Overall, hashing is a powerful technique that is used in many applications, including database indexing, spell-checking, and password storage. By using a good hash function and implementing appropriate collision resolution techniques, developers can optimize the performance of their applications and provide users with a seamless experience.</p> <hr></size;>