Kas yra maišos lentelė?

Maišos lentelė apibrėžiama kaip duomenų struktūra, naudojama norint greitai įterpti, ieškoti ir pašalinti rakto-reikšmių poras. Jis veikia ant maišos koncepcija , kur kiekvienas raktas maišos funkcija paverčiamas į atskirą masyvo indeksą. Indeksas veikia kaip atitinkamos vertės saugojimo vieta. Paprastais žodžiais tariant, jis susieja raktus su verte.

Kas yra apkrovos koeficientas?

Maišos lentelės apkrovos koeficientas nustatomas pagal tai, kiek elementų ten yra, atsižvelgiant į lentelės dydį. Jei apkrovos koeficientas yra didelis, stalas gali būti netvarkingas ir ilgesnis paieškos laikas bei susidūrimai. Idealus apkrovos koeficientas gali būti išlaikytas naudojant gerą maišos funkciją ir tinkamą lentelės dydį.

Kas yra maišos funkcija?

Funkcija, kuri paverčia raktus į masyvo indeksus, yra žinoma kaip maišos funkcija. Klavišai turi būti tolygiai paskirstyti masyve naudojant tinkamą maišos funkciją, kad būtų sumažintas susidūrimas ir būtų užtikrintas greitas paieškos greitis.

• Sveikųjų skaičių visatos prielaida: Manoma, kad raktai yra sveikieji skaičiai tam tikrame diapazone pagal sveikųjų skaičių visatos prielaidą. Tai leidžia naudoti pagrindines maišos operacijas, pvz., dalybos arba daugybos maišą.
• Maiša pagal padalijimą: Šis paprastas maišos metodas naudoja likusią rakto reikšmę, padalijus ją iš masyvo dydžio kaip indeksą. Kai masyvo dydis yra pirminis skaičius, o klavišai yra tolygiai išdėstyti, jis veikia gerai.
• Maišos keitimas dauginant: Ši nesudėtinga maišos operacija raktą padaugina iš konstantos nuo 0 iki 1, prieš paimant rezultato trupmeninę dalį. Po to indeksas nustatomas trupmeninį komponentą padauginus iš masyvo dydžio. Be to, jis veikia efektyviai, kai klavišai yra išsklaidyti vienodai.

Maišos funkcijos pasirinkimas :

Tinkamos maišos funkcijos pasirinkimas grindžiamas raktų savybėmis ir numatomu maišos lentelės funkcionalumu. Labai svarbu naudoti funkciją, kuri tolygiai paskirsto klavišus ir sumažina susidūrimų skaičių.

Kriterijai, kuriais remiantis pasirenkama maišos funkcija:

• Siekiant užtikrinti, kad susidūrimų skaičius būtų kuo mažesnis, gera maišos funkcija turėtų vienodai paskirstyti raktus visoje maišos lentelėje. Tai reiškia, kad visoms raktų poroms tikimybė, kad du raktai susimaišys į tą pačią lentelės vietą, turėtų būti gana pastovi.
• Norint įgalinti greitą maišą ir raktų gavimą, maišos funkcija turi būti efektyvi skaičiavimo požiūriu.
• Turėtų būti sudėtinga nustatyti raktą iš jo maišos vertės. Dėl to bandymai atspėti raktą naudojant maišos reikšmę yra mažiau sėkmingi.
• Maišos funkcija turi būti pakankamai lanksti, kad būtų galima koreguoti keičiantis duomenims, kuriems taikoma maiša. Pavyzdžiui, maišos funkcija turi ir toliau tinkamai veikti, jei keičiasi raktų dydis arba formatas.

Susidūrimų sprendimo būdai :

Susidūrimai įvyksta, kai du ar daugiau raktų nurodo tą patį masyvo indeksą. Sujungimas, atvirasis adresavimas ir dviguba maiša yra keletas būdų, kaip išspręsti susidūrimus.

• Atviras adresavimas : susidūrimai tvarkomi ieškant šios tuščios lentelės vietos. Jei pirmasis lizdas jau užimtas, maišos funkcija taikoma kitiems lizdams, kol vienas lieka tuščias. Šį metodą galima naudoti įvairiais būdais, įskaitant dvigubą maišą, linijinį zondavimą ir kvadratinį zondavimą.
• Atskiras sujungimas : Atskirai sujungiant grandinę, pateikiamas susietas objektų, turinčių maišą į kiekvieną maišos lentelės lizdą, sąrašas. Du raktai įtraukiami į susietąjį sąrašą, jei jie susieti su tuo pačiu lizdu. Šis metodas yra gana paprastas naudoti ir gali valdyti keletą susidūrimų.
• Robino Hudo maiša: Siekiant sumažinti grandinės ilgį, Robino Hudo maišos susidūrimai sprendžiami išjungiant klavišus. Algoritmas lygina atstumą tarp lizdo ir dviejų raktų užimto ​​lizdo, jei naujas raktas turi maišą su jau užimtu lizdu. Esamas raktas pakeičiamas nauju, jei jis yra arčiau idealaus lizdo. Tai priartina esamą raktą prie idealaus lizdo. Šis metodas turi tendenciją sumažinti susidūrimų skaičių ir sumažinti vidutinį grandinės ilgį.

Dinaminis dydžio keitimas:

Ši funkcija leidžia maišos lentelę išplėsti arba susitraukti, reaguojant į lentelėje esančių elementų skaičiaus pokyčius. Tai skatina idealų apkrovos koeficientą ir greitą paieškos laiką.

Maišos lentelės įgyvendinimai

Python, Java, C++ ir Ruby yra tik keletas programavimo kalbų, palaikančių maišos lenteles. Jie gali būti naudojami kaip pritaikyta duomenų struktūra, be to, kad dažnai įtraukiami į standartinę biblioteką.

Pavyzdys – suskaičiuokite simbolius String geeksforgeeks.

Šiame pavyzdyje eilutės skaičiui išsaugoti naudojame maišos techniką.

#include  using namespace std; int main() {  //initialize a string  string s='geeksforgeeks';    // Using an array to store the count of each alphabet   // by mapping the character to an index value  int arr[26]={0};    //Storing the count  for(int i=0;i

public class CharacterCount {  public static void main(String[] args) {  // Initialize a string  String s = 'geeksforgeeks';  // Using an array to store the count of each alphabet  // by mapping the character to an index value  int[] arr = new int[26];  // Storing the count  for (int i = 0; i < s.length(); i++) {  arr[s.charAt(i) - 'a']++;  }  // Search the count of the character  char ch = 'e';  // Get count  System.out.println('The count of ' + ch + ' is ' + arr[ch - 'a']);  } }>

# Initialize a string s = 'geeksforgeeks' # Using a list to store the count of each alphabet # by mapping the character to an index value arr = [0] * 26 # Storing the count for i in range(len(s)): arr[ord(s[i]) - ord('a')] += 1 # Search the count of the character ch = 'e' # Get count print('The count of ', ch, ' is ', arr[ord(ch) - ord('a')])>

using System; class Program {  static void Main(string[] args) {  //initialize a string  string s = 'geeksforgeeks';  // Using an array to store the count of each alphabet   // by mapping the character to an index value  int[] arr = new int[26];  //Storing the count  for (int i = 0; i < s.Length; i++) {  arr[s[i] - 'a']++;  }  //Search the count of the character  char ch = 'e';  // get count  Console.WriteLine('The count of ' + ch + ' is ' + arr[ch - 'a']);  } }>

// Initialize a string const s = 'geeksforgeeks'; // Using an array to store the count of each alphabet // by mapping the character to an index value const arr = Array(26).fill(0); // Storing the count for (let i = 0; i < s.length; i++) {  arr[s.charCodeAt(i) - 'a'.charCodeAt(0)]++; } // Search the count of the character const ch = 'e'; // Get count console.log(`The count of ${ch} is ${arr[ch.charCodeAt(0) - 'a'.charCodeAt(0)]}`);>

Išvestis:

The count of e is 4>

Maišos lentelės sudėtingumo analizė:

Atliekant paieškos, įterpimo ir ištrynimo operacijas, maišos lentelių vidutinis atvejo sudėtingumas yra O(1). Tačiau šioms operacijoms blogiausiu atveju gali prireikti O (n) laiko, kur n yra elementų skaičius lentelėje.

Maišos lentelės taikymas:

• Maišos lentelės dažnai naudojamos dideliems duomenų kiekiams indeksuoti ir ieškoti. Paieškos variklis gali naudoti maišos lentelę tinklalapiams, kuriuos ji indeksavo, saugoti.
• Duomenys paprastai talpinami atmintyje per maišos lenteles, leidžiančias greitai pasiekti dažnai naudojamą informaciją.
• Maišos funkcijos dažnai naudojamos kriptografijoje skaitmeniniams parašams kurti, duomenims patvirtinti ir duomenų vientisumui užtikrinti.
• Maišos lentelės gali būti naudojamos duomenų bazės indeksams įdiegti, kad būtų galima greitai pasiekti duomenis, pagrįstus pagrindinėmis reikšmėmis.