РЕАЛІЗАЦІЯ ХЕШ-ТАБЛИЦІ В C/C++ ЗА ДОПОМОГОЮ ОКРЕМОГО ЛАНЦЮЖКА - TECHCODEVIEW.COM

вступ:

Засоби скорочення URL-адрес є прикладом хешування, оскільки вони зіставляють великий розмір URL-адреси з малим розміром

Деякі приклади хеш-функцій:

ключ % кількість відер
Значення ASCII символу * ПростіЧисло ^x. Де x = 1, 2, 3….n
Ви можете створити власну хеш-функцію, але це має бути хороша хеш-функція, яка дає менше колізій.

Компоненти хешування

Індекс сегмента:

Значення, яке повертає функція Hash, є індексом сегмента для ключа в окремому методі ланцюжка. Кожен індекс у масиві називається сегментом, оскільки він є сегментом пов’язаного списку.

Переробка:

Повторне хешування — це концепція, яка зменшує зіткнення, коли елементи збільшуються в поточній хеш-таблиці. Він створить новий масив подвоєного розміру та скопіює в нього попередні елементи масиву, і це схоже на внутрішню роботу вектора в C++. Очевидно, що хеш-функція має бути динамічною, оскільки вона має відображати деякі зміни при збільшенні ємності. Хеш-функція включає в себе ємність хеш-таблиці, тому під час копіювання ключових значень із попереднього масиву хеш-функція дає різні індекси відра, оскільки це залежить від ємності (відер) хеш-таблиці. Як правило, коли значення коефіцієнта завантаження перевищує 0,5, виконується повторне хешування.

Подвоїти розмір масиву.
Скопіюйте елементи попереднього масиву в новий масив. Ми використовуємо хеш-функцію під час повторного копіювання кожного вузла в новий масив, тому це зменшить зіткнення.
Видаліть попередній масив із пам’яті та наведіть покажчик внутрішнього масиву хеш-карти на цей новий масив.
Як правило, коефіцієнт завантаження = кількість елементів у хеш-карті / загальна кількість сегментів (ємність).

Зіткнення:

Колізія – це ситуація, коли індекс сегмента не порожній. Це означає, що заголовок пов’язаного списку присутній у цьому індексі сегмента. У нас є два або більше значень, які відображаються на один і той самий індекс сегмента.

Основні функції нашої програми

Вставка
Пошук
Хеш-функція
Видалити
Переспівування

Хеш-карта

Реалізація без переробки:

C

#include> #include> #include> // Linked List node> struct> node {> > // key is string> > char> * key;> > // value is also string> > char> * value;> > struct> node* next;> };> // like constructor> void> setNode(> struct> node* node,> char> * key,> char> * value)> {> > node->ключ = ключ;> > node->значення = значення;> > node->наступний = NULL;> > return> ;> };> struct> hashMap {> > // Current number of elements in hashMap> > // and capacity of hashMap> > int> numOfElements, capacity;> > // hold base address array of linked list> > struct> node** arr;> };> // like constructor> void> initializeHashMap(> struct> hashMap* mp)> {> > // Default capacity in this case> > mp->місткість = 100;> > mp->numOfElements = 0;> > // array of size = 1> > mp->arr = (> struct> node**)> malloc> (> sizeof> (> struct> node*)> > * mp->місткість);> > return> ;> }> int> hashFunction(> struct> hashMap* mp,> char> * key)> {> > int> bucketIndex;> > int> sum = 0, factor = 31;> > for> (> int> i = 0; i <> strlen> (key); i++) {> > // sum = sum + (ascii value of> > // char * (primeNumber ^ x))...> > // where x = 1, 2, 3....n> > sum = ((sum % mp->місткість)>> > + (((> int> )key[i]) * factor) % mp->місткість)>> > % mp->місткість;> > // factor = factor * prime> > // number....(prime> > // number) ^ x> > factor = ((factor % __INT16_MAX__)> > * (31 % __INT16_MAX__))> > % __INT16_MAX__;> > }> > bucketIndex = sum;> > return> bucketIndex;> }> void> insert(> struct> hashMap* mp,> char> * key,> char> * value)> {> > // Getting bucket index for the given> > // key - value pair> > int> bucketIndex = hashFunction(mp, key);> > struct> node* newNode = (> struct> node*)> malloc> (> > // Creating a new node> > sizeof> (> struct> node));> > // Setting value of node> > setNode(newNode, key, value);> > // Bucket index is empty....no collision> > if> (mp->arr[bucketIndex] == NULL) {> > mp->arr[bucketIndex] = newNode;> > }> > // Collision> > else> {> > // Adding newNode at the head of> > // linked list which is present> > // at bucket index....insertion at> > // head in linked list> > newNode->next = mp->arr[bucketIndex];> > mp->arr[bucketIndex] = newNode;> > }> > return> ;> }> void> delete> (> struct> hashMap* mp,> char> * key)> {> > // Getting bucket index for the> > // given key> > int> bucketIndex = hashFunction(mp, key);> > struct> node* prevNode = NULL;> > // Points to the head of> > // linked list present at> > // bucket index> > struct> node* currNode = mp->arr[індекс відра];> > while> (currNode != NULL) {> > // Key is matched at delete this> > // node from linked list> > if> (> strcmp> (key, currNode->ключ) == 0) {> > // Head node> > // deletion> > if> (currNode == mp->arr[bucketIndex]) {> > mp->arr[bucketIndex] = currNode->next;> > }> > // Last node or middle node> > else> {> > prevNode->наступний = currNode->наступний;> > }> > free> (currNode);> > break> ;> > }> > prevNode = currNode;> > currNode = currNode->далі;> > }> > return> ;> }> char> * search(> struct> hashMap* mp,> char> * key)> {> > // Getting the bucket index> > // for the given key> > int> bucketIndex = hashFunction(mp, key);> > // Head of the linked list> > // present at bucket index> > struct> node* bucketHead = mp->arr[індекс відра];> > while> (bucketHead != NULL) {> > // Key is found in the hashMap> > if> (bucketHead->ключ == ключ) {> > return> bucketHead->значення;> > }> > bucketHead = bucketHead->далі;> > }> > // If no key found in the hashMap> > // equal to the given key> > char> * errorMssg = (> char> *)> malloc> (> sizeof> (> char> ) * 25);> > errorMssg =>

'Oops! No data found.
'>

;> > return> errorMssg;> }> // Drivers code> int> main()> {> > // Initialize the value of mp> > struct> hashMap* mp> > = (> struct> hashMap*)> malloc> (> sizeof> (> struct> hashMap));> > initializeHashMap(mp);> > insert(mp,> 'Yogaholic'> ,> 'Anjali'> );> > insert(mp,> 'pluto14'> ,> 'Vartika'> );> > insert(mp,> 'elite_Programmer'> ,> 'Manish'> );> > insert(mp,> 'GFG'> ,> 'techcodeview.com'> );> > insert(mp,> 'decentBoy'> ,> 'Mayank'> );> > printf> (>

'%s
'>

, search(mp,> 'elite_Programmer'> ));> > printf> (>

'%s
'>

, search(mp,> 'Yogaholic'> ));> > printf> (>

'%s
'>

, search(mp,> 'pluto14'> ));> > printf> (>

'%s
'>

, search(mp,> 'decentBoy'> ));> > printf> (>

'%s
'>

, search(mp,> 'GFG'> ));> > // Key is not inserted> > printf> (>

'%s
'>

, search(mp,> 'randomKey'> ));> > printf> (>

'
After deletion : 
'>

);> > // Deletion of key> > delete> (mp,> 'decentBoy'> );> > printf> (>

'%s
'>

, search(mp,> 'decentBoy'> ));> > return> 0;> }>

C++

#include> #include> // Linked List node> struct> node {> > // key is string> > char> * key;> > // value is also string> > char> * value;> > struct> node* next;> };> // like constructor> void> setNode(> struct> node* node,> char> * key,> char> * value) {> > node->ключ = ключ;> > node->значення = значення;> > node->наступний = NULL;> > return> ;> }> struct> hashMap {> > // Current number of elements in hashMap> > // and capacity of hashMap> > int> numOfElements, capacity;> > // hold base address array of linked list> > struct> node** arr;> };> // like constructor> void> initializeHashMap(> struct> hashMap* mp) {> > // Default capacity in this case> > mp->місткість = 100;> > mp->numOfElements = 0;> > // array of size = 1> > mp->arr = (> struct> node**)> malloc> (> sizeof> (> struct> node*) * mp->місткість);>> > return> ;> }> int> hashFunction(> struct> hashMap* mp,> char> * key) {> > int> bucketIndex;> > int> sum = 0, factor = 31;> > for> (> int> i = 0; i <> strlen> (key); i++) {> > // sum = sum + (ascii value of> > // char * (primeNumber ^ x))...> > // where x = 1, 2, 3....n> > sum = ((sum % mp->місткість) + (((> int> )key[i]) * factor) % mp->місткість) % mp->ємність;> > // factor = factor * prime> > // number....(prime> > // number) ^ x> > factor = ((factor % __INT16_MAX__) * (31 % __INT16_MAX__)) % __INT16_MAX__;> > }> > bucketIndex = sum;> > return> bucketIndex;> }> void> insert(> struct> hashMap* mp,> char> * key,> char> * value) {> > // Getting bucket index for the given> > // key - value pair> > int> bucketIndex = hashFunction(mp, key);> > struct> node* newNode = (> struct> node*)> malloc> (> > // Creating a new node> > sizeof> (> struct> node));> > // Setting value of node> > setNode(newNode, key, value);> > // Bucket index is empty....no collision> > if> (mp->arr[bucketIndex] == NULL) {> > mp->arr[bucketIndex] = newNode;> > }> > // Collision> > else> {> > // Adding newNode at the head of> > // linked list which is present> > // at bucket index....insertion at> > // head in linked list> > newNode->next = mp->arr[bucketIndex];> > mp->arr[bucketIndex] = newNode;> > }> > return> ;> }> void> deleteKey(> struct> hashMap* mp,> char> * key) {> > // Getting bucket index for the> > // given key> > int> bucketIndex = hashFunction(mp, key);> > struct> node* prevNode = NULL;> > // Points to the head of> > // linked list present at> > // bucket index> > struct> node* currNode = mp->arr[індекс відра];> > while> (currNode != NULL) {> > // Key is matched at delete this> > // node from linked list> > if> (> strcmp> (key, currNode->ключ) == 0) {> > // Head node> > // deletion> > if> (currNode == mp->arr[bucketIndex]) {> > mp->arr[bucketIndex] = currNode->next;> > }> > // Last node or middle node> > else> {> > prevNode->наступний = currNode->наступний;> }> free> (currNode);> break> ;> }> prevNode = currNode;> > currNode = currNode->далі;> > }> return> ;> }> char> * search(> struct> hashMap* mp,> char> * key) {> // Getting the bucket index for the given key> int> bucketIndex = hashFunction(mp, key);> // Head of the linked list present at bucket index> struct> node* bucketHead = mp->arr[індекс відра];> while> (bucketHead != NULL) {> > > // Key is found in the hashMap> > if> (> strcmp> (bucketHead->ключ, ключ) == 0) {> > return> bucketHead->значення;> > }> > > bucketHead = bucketHead->далі;> }> // If no key found in the hashMap equal to the given key> char> * errorMssg = (> char> *)> malloc> (> sizeof> (> char> ) * 25);> strcpy> (errorMssg,>

'Oops! No data found.
'>

);> return> errorMssg;> }> // Drivers code> int> main()> {> // Initialize the value of mp> struct> hashMap* mp = (> struct> hashMap*)> malloc> (> sizeof> (> struct> hashMap));> initializeHashMap(mp);> insert(mp,> 'Yogaholic'> ,> 'Anjali'> );> insert(mp,> 'pluto14'> ,> 'Vartika'> );> insert(mp,> 'elite_Programmer'> ,> 'Manish'> );> insert(mp,> 'GFG'> ,> 'techcodeview.com'> );> insert(mp,> 'decentBoy'> ,> 'Mayank'> );> printf> (>

'%s
'>

, search(mp,> 'elite_Programmer'> ));> printf> (>

'%s
'>

, search(mp,> 'Yogaholic'> ));> printf> (>

'%s
'>

, search(mp,> 'pluto14'> ));> printf> (>

'%s
'>

, search(mp,> 'decentBoy'> ));> printf> (>

'%s
'>

, search(mp,> 'GFG'> ));> // Key is not inserted> printf> (>

'%s
'>

, search(mp,> 'randomKey'> ));> printf> (>

'
After deletion : 
'>

);> // Deletion of key> deleteKey(mp,> 'decentBoy'> );> // Searching the deleted key> printf> (>

'%s
'>

, search(mp,> 'decentBoy'> ));> return> 0;> }>

Вихід

Manish Anjali Vartika Mayank techcodeview.com Oops! No data found. After deletion : Oops! No data found.

Пояснення:

хеш-функція = значення ASCII символу * простий номер ^x

Ця реалізація не використовує концепцію повторного хешування. Це масив зв’язаних списків фіксованого розміру.
Ключ і значення є рядками в наведеному прикладі.

Часова складність і просторова складність:

Часова складність операцій вставки та видалення хеш-таблиці в середньому становить O(1). Є певний математичний розрахунок, який це підтверджує.

Часова складність вставки: у середньому випадку вона постійна. У гіршому випадку вона лінійна. Часова складність пошуку: У середньому вона постійна. У гіршому випадку вона лінійна. Часова складність видалення: у середніх випадках вона постійна. У гіршому випадку вона лінійна. Просторова складність: O(n), оскільки містить n елементів.

Схожі статті: