logo

TechCodeview

Реалізація хеш-таблиці в C/C++ з використанням окремого ланцюжка

вступ:

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

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

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

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



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

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

Переробка:

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

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

Зіткнення:

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



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

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

Хеш-карта

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

C



java elseif




розмір латексного шрифту

#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++




приклад підрядка в java

#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.>

Пояснення:

    вставка: вставляє пару ключ-значення в початок пов’язаного списку, який присутній у заданому індексі сегмента. hashFunction: дає індекс сегмента для даного ключа. наш хеш-функція = значення ASCII символу * простий номерx . Просте число в нашому випадку дорівнює 31, а значення x збільшується від 1 до n для послідовних символів у ключі. видалення: видаляє пару ключ-значення з хеш-таблиці для заданого ключа. Він видаляє вузол зі зв’язаного списку, який містить пару ключ-значення. Пошук: пошук значення заданого ключа.
  • Ця реалізація не використовує концепцію повторного хешування. Це масив зв’язаних списків фіксованого розміру.
  • Ключ і значення є рядками в наведеному прикладі.

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

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

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

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

  • Окрема ланцюгова техніка обробки колізій у хешуванні.