Kas ir hash tabula?

Hash tabula ir definēta kā datu struktūra, ko izmanto, lai ātri ievietotu, meklētu un noņemtu atslēgu un vērtību pārus. Tas darbojas uz jaukšanas jēdziens , kur katra atslēga ar jaucējfunkciju tiek pārvērsta atsevišķā masīva indeksā. Indekss darbojas kā atbilstošās vērtības glabāšanas vieta. Vienkāršiem vārdiem sakot, tas kartē atslēgas ar vērtību.

Kas ir slodzes koeficients?

Hash tabulas noslodzes koeficientu nosaka, cik daudz elementu tajā tiek glabāts attiecībā pret tabulas lielumu. Tabula var būt pārblīvēta, un tai var būt ilgāks meklēšanas laiks un sadursmes, ja slodzes koeficients ir augsts. Ideālu slodzes koeficientu var uzturēt, izmantojot labu jaucējfunkciju un pareizu tabulas izmēru maiņu.

foreach cilpas mašīnraksts

Kas ir Hash funkcija?

Funkciju, kas pārvērš atslēgas masīva indeksos, sauc par jaucējfunkciju. Atslēgām jābūt vienmērīgi sadalītām pa masīvu, izmantojot pienācīgu jaucējfunkciju, lai samazinātu sadursmes un nodrošinātu ātru meklēšanas ātrumu.

• Visuma pieņēmums par veseliem skaitļiem: Tiek pieņemts, ka atslēgas ir veseli skaitļi noteiktā diapazonā saskaņā ar veselu skaitļu visuma pieņēmumu. Tas ļauj izmantot pamata jaukšanas darbības, piemēram, dalīšanas vai reizināšanas jaukšanu.
• Jaukšana pēc dalīšanas: Šī vienkāršā jaukšanas metode izmanto atslēgas atlikušo vērtību pēc tam, kad tā ir sadalīta ar masīva lielumu kā indeksu. Ja masīva lielums ir pirmskaitlis un taustiņi ir vienmērīgi izvietoti, tas darbojas labi.
• Jaukšana, reizinot: Šī vienkāršā jaukšanas darbība reizina atslēgu ar konstanti no 0 līdz 1, pirms tiek ņemta rezultāta daļēja daļa. Pēc tam indeksu nosaka, reizinot frakcionēto komponentu ar masīva lielumu. Turklāt tas darbojas efektīvi, ja taustiņi ir vienādi izkliedēti.

Jaucējfunkcijas izvēle :

Pienācīgas jaucējfunkcijas izvēle ir balstīta uz atslēgu īpašībām un paredzēto hash tabulas funkcionalitāti. Ir ļoti svarīgi izmantot funkciju, kas vienmērīgi sadala taustiņus un samazina sadursmes.

Kritēriji, pamatojoties uz kuriem tiek izvēlēta jaukšanas funkcija:

• Lai nodrošinātu, ka sadursmju skaits tiek samazināts līdz minimumam, labai jaucējfunkcijai ir jāsadala atslēgas visā hash tabulā vienādi. Tas nozīmē, ka visiem atslēgu pāriem varbūtībai, ka divas atslēgas tiks sajauktas vienā un tajā pašā pozīcijā tabulā, ir jābūt diezgan nemainīgai.
• Lai iespējotu ātru jaukšanu un atslēgu izguvi, jaukšanas funkcijai ir jābūt skaitļošanas ziņā efektīvai.
• Būtu grūti izsecināt atslēgu no tās jaucējvērtības. Rezultātā mēģinājumi uzminēt atslēgu, izmantojot jaucējvērtību, ir mazāk ticami veiksmīgi.
• Jaukšanas funkcijai jābūt pietiekami elastīgai, lai to pielāgotu, mainoties datiem, kas tiek sajaukti. Piemēram, jaukšanas funkcijai jāturpina pareizi darboties, ja jaukto taustiņu izmērs vai formāts mainās.

Sadursmju risināšanas metodes :

Sadursmes notiek, ja divas vai vairākas atslēgas norāda uz vienu un to pašu masīva indeksu. Ķēdēšana, atvērta adresēšana un dubultā jaukšana ir dažas sadursmju risināšanas metodes.

• Atvērt adresāciju : sadursmes tiek apstrādātas, tabulā meklējot šādu tukšu vietu. Ja pirmais slots jau ir aizņemts, jaucējfunkcija tiek piemērota nākamajiem slotiem, līdz viena paliek tukša. Ir dažādi veidi, kā izmantot šo pieeju, tostarp dubultā jaukšana, lineārā zondēšana un kvadrātiskā zondēšana.
• Atsevišķa ķēde : Atsevišķā ķēdē ir izveidots saistīts saraksts ar objektiem, kas ir jaucējkrāni katrā hash tabulas slotā. Saistītajā sarakstā ir iekļautas divas atslēgas, ja tās ir saistītas ar vienu un to pašu slotu. Šī metode ir diezgan vienkārši lietojama, un tā var pārvaldīt vairākas sadursmes.
• Robina Huda jaukšana: Lai samazinātu ķēdes garumu, sadursmes Robina Huda jaukšanā tiek novērstas, izslēdzot taustiņus. Algoritms salīdzina attālumu starp slotu un abu atslēgu aizņemto slotu, ja jauna atslēga tiek sajaukta ar jau aizņemtu slotu. Esošā atslēga tiek aizstāta ar jauno, ja tā ir tuvāk ideālajam slotam. Tādējādi esošā atslēga tiek pietuvināta tās ideālajam slotam. Šai metodei ir tendence samazināt sadursmes un vidējo ķēdes garumu.

Dinamiskā izmēra maiņa:

Šī funkcija ļauj hash tabulai paplašināties vai samazināties, reaģējot uz izmaiņām tabulā ietverto elementu skaitā. Tas veicina ideālu slodzes koeficientu un ātru meklēšanas laiku.

c virkne masīvā

Hash tabulas ieviešanas

Python, Java, C++ un Ruby ir tikai dažas no programmēšanas valodām, kas atbalsta hash tabulas. Tos var izmantot kā pielāgotu datu struktūru papildus tam, ka tie bieži tiek iekļauti standarta bibliotēkā.

Piemērs — saskaitiet rakstzīmes virknē geeksforgeeks.

Šajā piemērā mēs izmantojam jaukšanas paņēmienu, lai saglabātu virknes skaitu.

#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)]}`);>

java miegs

Izvade:

The count of e is 4>

Hash tabulas sarežģītības analīze:

Uzmeklēšanas, ievietošanas un dzēšanas operācijām jaucējtabulu vidējā gadījuma laika sarežģītība ir O(1). Tomēr šīm darbībām sliktākajā gadījumā var būt nepieciešams O (n) laiks, kur n ir elementu skaits tabulā.

Hash tabulas pielietojumi:

• Hash tabulas bieži tiek izmantotas, lai indeksētu un meklētu lielu datu apjomu. Meklētājprogramma var izmantot jaucējtabulu, lai saglabātu tās indeksētās tīmekļa lapas.
• Dati parasti tiek saglabāti kešatmiņā, izmantojot hash tabulas, kas ļauj ātri piekļūt bieži izmantotajai informācijai.
• Jaucējfunkcijas bieži tiek izmantotas kriptogrāfijā, lai izveidotu ciparparakstus, apstiprinātu datus un garantētu datu integritāti.
• Hash tabulas var izmantot datu bāzes indeksu ieviešanai, nodrošinot ātru piekļuvi datiem, pamatojoties uz galvenajām vērtībām.