logo

TechCodeview

Maišos lentelės įgyvendinimas C/C++ naudojant atskirą grandinėjimą

Įvadas:

URL sutrumpinimo priemonės yra maišos pavyzdys, nes jis susieja didelio dydžio URL su mažu dydžiu

Kai kurie maišos funkcijų pavyzdžiai:

  • raktas % segmentų skaičius
  • ASCII simbolio reikšmė * PrimeNumberx. Kur x = 1, 2, 3….n
  • Galite sukurti savo maišos funkciją, tačiau ji turėtų būti gera maišos funkcija, kuri sumažintų susidūrimų skaičių.

Maišos komponentai



Grupės indeksas:

Funkcijos maišos grąžinama reikšmė yra atskiro grandinės metodo rakto segmento indeksas. Kiekvienas masyvo indeksas vadinamas segmentu, nes tai yra susieto sąrašo segmentas.

Perdirbimas:

Pakartotinis maišos nustatymas yra koncepcija, kuri sumažina susidūrimą, kai dabartinėje maišos lentelėje elementų skaičius padidinamas. Jis sukurs naują dvigubo dydžio masyvą ir nukopijuos į jį ankstesnius masyvo elementus ir tai yra kaip vidinis vektoriaus darbas C++. Akivaizdu, kad maišos funkcija turėtų būti dinamiška, nes ji turėtų atspindėti kai kuriuos pokyčius padidinus talpą. Maišos funkcija apima joje esančios maišos lentelės talpą, todėl, kopijuojant raktų reikšmes iš ankstesnio masyvo maišos funkcijos, gaunami skirtingi segmentų indeksai, nes tai priklauso nuo maišos lentelės talpos (kibirų). Paprastai, kai apkrovos koeficiento vertė yra didesnė nei 0,5, kartojama.

  • Dvigubai padidinkite masyvo dydį.
  • Nukopijuokite ankstesnio masyvo elementus į naują masyvą. Mes naudojame maišos funkciją, kol kiekvieną mazgą vėl kopijuosime į naują masyvą, todėl tai sumažins susidūrimą.
  • Ištrinkite ankstesnį masyvą iš atminties ir nukreipkite maišos žemėlapio vidinio masyvo žymeklį į šį naują masyvą.
  • Paprastai apkrovos koeficientas = maišos žemėlapio elementų skaičius / bendras segmentų skaičius (talpa).

Susidūrimas:

Susidūrimas yra situacija, kai segmento indeksas nėra tuščias. Tai reiškia, kad tame segmento indekse yra susieto sąrašo antraštė. Turime dvi ar daugiau verčių, susietų su tuo pačiu segmento indeksu.



: Java

Pagrindinės funkcijos mūsų programoje

  • Įdėjimas
  • Paieška
  • Maišos funkcija
  • Ištrinti
  • Perdirbimas

Maišos žemėlapis

Diegimas be pakeitimo:

C






java skaityti csv

#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->raktas = raktas;> >node->reikšmė = vertė;> >node->kitas = 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->talpa = 100;> >mp->numOfElements = 0;> >// array of size = 1> >mp->arr = (>struct> node**)>malloc>(>sizeof>(>struct> node*)> >* mp->talpa);> >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->talpa)> >+ (((>int>)key[i]) * factor) % mp->talpa)> >% mp->talpa;> >// 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] = naujasMazgas;> >}> >// 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] = naujasMazgas;> >}> >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[bucketIndex];> >while> (currNode != NULL) {> >// Key is matched at delete this> >// node from linked list> >if> (>strcmp>(key, currNode->klavišas) == 0) {> >// Head node> >// deletion> >if> (currNode == mp->arr[bucketIndex]) {> >mp->arr[bucketIndex] = currNode->next;> >}> >// Last node or middle node> >else> {> >prevNode->next = currNode->ext;> >}> >free>(currNode);> >break>;> >}> >prevNode = currNode;> >currNode = currNode->kitas;> >}> >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[bucketIndex];> >while> (bucketHead != NULL) {> >// Key is found in the hashMap> >if> (bucketHead->raktas == raktas) {> >return> bucketHead->vertė;> >}> >bucketHead = bucketHead->kitas;> >}> >// 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++




poeilutės pavyzdys 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->raktas = raktas;> >node->reikšmė = vertė;> >node->kitas = 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->talpa = 100;> >mp->numOfElements = 0;> >// array of size = 1> >mp->arr = (>struct> node**)>malloc>(>sizeof>(>struct> node*) * mp->talpa);> >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->talpa) + (((>int>)key[i]) * factor) % mp->talpa) % mp->talpa;> >// 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] = naujasMazgas;> >}> >// 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] = naujasMazgas;> >}> >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[bucketIndex];> >while> (currNode != NULL) {> >// Key is matched at delete this> >// node from linked list> >if> (>strcmp>(key, currNode->klavišas) == 0) {> >// Head node> >// deletion> >if> (currNode == mp->arr[bucketIndex]) {> >mp->arr[bucketIndex] = currNode->next;> >}> >// Last node or middle node> >else> {> >prevNode->next = currNode->ext;> }> free>(currNode);> break>;> }> prevNode = currNode;> >currNode = currNode->kitas;> >}> 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[bucketIndex];> while> (bucketHead != NULL) {> > >// Key is found in the hashMap> >if> (>strcmp>(bucketHead->raktas, raktas) == 0) {> >return> bucketHead->vertė;> >}> > >bucketHead = bucketHead->kitas;> }> // 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;> }> 

>

>

pašalinant paskutinį įsipareigojimą
Išvestis 

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

Paaiškinimas:

    Įterpimas: įterpia rakto ir reikšmių porą susieto sąrašo, kuris yra nurodytame segmento indekse, pradžioje. hashFunction: suteikia tam tikro rakto segmento indeksą. Mūsų maišos funkcija = ASCII simbolio reikšmė * pirminis skaičiusx . Pirminis skaičius mūsų atveju yra 31, o x reikšmė didėja nuo 1 iki n, kai raktas yra iš eilės. trynimas: ištrina rakto-reikšmių porą iš duoto rakto maišos lentelės. Jis pašalina mazgą iš susieto sąrašo, kuriame yra rakto ir vertės pora. Paieška: ieškokite nurodyto rakto vertės.
  • Šis įgyvendinimas nenaudoja pakartotinio maišymo koncepcijos. Tai fiksuoto dydžio susietų sąrašų masyvas.
  • Pateiktame pavyzdyje raktas ir reikšmė yra eilutės.

Laiko ir erdvės sudėtingumas:

Maišos lentelės įterpimo ir ištrynimo operacijų laiko sudėtingumas yra vidutiniškai O(1). Yra keletas matematinių skaičiavimų, kurie tai įrodo.

    Įterpimo laiko sudėtingumas: vidutiniu atveju jis yra pastovus. Blogiausiu atveju jis yra linijinis. Paieškos laiko sudėtingumas: vidutiniu atveju jis yra pastovus. Blogiausiu atveju jis yra linijinis. Ištrynimo laiko sudėtingumas: vidutiniais atvejais jis yra pastovus. Blogiausiu atveju jis yra linijinis. Erdvės sudėtingumas: O(n), nes turi n elementų skaičių.

Susiję straipsniai:

  • Atskira grandininio susidūrimo apdorojimo technika maišos procese.